Graph traversals. (OR) Depth first and Breadth First Search methods.:

There are mainly two methods for traversing in a graph, Depth first and Breadth first traversals.

1. Depth First Search (DFS): It uses a STACK to hold the nodes that are waiting to be processed. First we examine the starting node ‘A’. Then we examine each node along a path ‘P’, which begins at A. i.e. we process one of the neighbors of ‘A’ and continue along the path. After coming to the end of ‘P’, we back track on ‘P’ until we can continue along another path.

Algorithm:

1. Initialize all nodes to ready state.

2. Start with a node and push the node ‘A’ in the stack.

3. POP the top node ‘X’ from the stack. Print X.

4. Push all its neighbors omitting the processed ones in to the Stack.

5. Repeat the above two steps till all the elements of graph are visited.

6. Pop all the elements of the stack and print them to complte DFS.

Pseudo code to implement DFS (Depth First Search)

void DepthFirst(Graph G)

{

boolean visited[MAX];

int v;

for(all v in G)

visited[v]=FALSE;

for(all v in G)

if(!visited[v])

traverse(v);

}

void traverse(int v)

{

int w;

visited[v]=TRUE;

visit(v);

for( all w adjacent to v)

if(!visited[w])

traverse(w);

}

2. Breadth First Search (BFS): It uses QUEUE to hold nodes that are waiting to be processed. First we examine the starting node A. Then we examine all the neighbors of A. And, we continue with the other nodes in the same manner. No node is processed more the once.

Algorithm:

1. Initialize all nodes to ready state.

2. Start with a node and place it in the Queue.

3. remove an element ‘X’ from queue and Print X.

4. Place all its neighbors omitting the processed ones in the Queue

5. Repeat the above two steps till all the elements of graph are visited.

6. Delete all the elements of the queue and print them to complte BFS.

Pseudo code to implement BFS (Breadth First Search):

void BreadthFirst(Graph G)

{

Queue q;

boolean visited[MAX];

int v,w;

for(all v in G)

visited[v]=FALSE;

initialize(q);

for(all v in G)

{

if(!visited[v])

{

addQueue(v,q);

do

{

deleteQueue(v,q);

visited[v]=TRUE;

visit(v);

for( all w adjacent to v)

if(!visited[w])

addQueue(w);

}while(!empty(q));

}

}

}