Graph Traversal in Data Structure

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

Breadth-First Search (BFS):

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.

Breadth-First Search Algorithm:

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 an 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 an 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(n²).

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