# Graph Traversal in Data Structure

There are two standard ways to traverse a graph.
2. Depth-First Search (DFS)

In this traversal technique, at first select a vertex S to start the traversal. Initially set the colour of all the vertices to WHITE. Insert S into the queue and change its colour to BLACK as now S is a visited vertex. Now delete the front node N from the queue. Visit all the adjacent vertices of N and insert to queue those neighbours of N that have the colour WHITE. Change their colours to BLACK. Continue this procedure until the queue is empty.

```Algorithm fnBFS(S)
{
for(all the vertices j of the graph)
color[j]=WHITE;
fnInsert(S);
Color[S]=BLACK;
while(queue is not empty)
{
N=fnDelete();
for(each adjacent vertex j of N)
if(Color[j]==WHITE)
{
fnInsert(j);
Color[j]=BLACK;
}
}
}  // End of Algorithm
```

#### Time Complexity of Breadth-First Search Algorithm:

If we represent the graph using adjacency list, then we have to traverse each edge at most twice(for an undirected graph). Hence time complexity is O(e) where e is the total number of edges.
If we represent the graph using adjacency matrix, then we have to check n entries in the matrix for each vertex to find its adjacent vertices. As there are total n vertices, so time complexity is O(n2).

## Depth-First Search (DFS):

In this traversal technique, we use a stack instead of queue. Like the BFS traversal, initially set the colour of all the vertices to WHITE. Insert starting vertex S into the stack and change its colour to BLACK. Now delete the top node N from the stack. Visit all the adjacent vertices of N and insert to stack those neighbours of N that have the colour WHITE. Change their colours to BLACK. Continue this procedure until the stack is empty.

### Depth-First Search Algorithm:

```Algorithm fnDFS(S)
{
for(all the vertices j of the graph)
Color[j]=WHITE;
fnPush(S);
Color[S]=BLACK;
while(stack is not empty)
{
N=fnPop();
for(each adjacent vertex j of N)
if(Color[j]==WHITE)
{
fnPush(j);
Color[j]=BLACK;
}
}
}  // End of Algorithm
```