Search

Sunday, February 22, 2015
0 comments

C Language: Depth First Traversal in Graph

6:14 AMSunday, February 22, 2015
This traversal techniques is based on the fact of visiting all the nodes of graph in the depth of it. It means start from the start node of the graph and reach to last node of the graph in its depth (so that no further unexplored adjacent node exist). From the start node explore all the adjacent nodes but visit one of the adjacent nodes. From the visited adjacent node further explore all the adjacent nodes of it and again select one of the adjacent nodes and further explore it. In this way the exploration of the adjacent node carried till to reach the last node. Once the last node is reached then back track from the last node to previous node to visit the next adjacent node of it. The data structure stack is used in this type of traversal. 
Consider the following graph:
Depth First Traversal in Graph
The adjacent nodes of node
The adjacent nodes of node

The depth first traversal of the above graph, assuming node 'A' as start node is:

A     E      D      C     B

You can observe from the traversal result that the first node visited is the starting node. Then the next node visited is 'E' one of the adjacent nodes of the start node 'A'. Then the adjacent nodes of 'E' that are not marked are explored. The only marked node is 'D'. It is visited. There are no further adjacent nodes of 'D'  that are not marked . So, we have reached the other end of the graph. Now backtrack from 'D' to 'E' no adjacent nodes of 'E' are left to be visited. Again backtrack from 'E' to 'A'. There are two adjacent nodes left that are not visited. So, node 'C' is visited next. There are no adjacent nodes of node 'C' that are left for visiting. Again backtrack from 'C' to 'A' and visited the last node 'B' which is adjacent of 'A' all the nodes of the graph are visited and the traversal is complete. 

As we backtrack in the technique of depth first traversal it is necessary to use the last in first out data structure that is stack to store the nodes that are to be backtracked.
You can again remember that the traversal result may be different to the one given above. It differs because the adjacent nodes of a visited node may be pushed on the stack in any order. So, the other result of depth first traversal of the above graph are:

A        B       D       C        E
A        C       D       B        E     etc.

The formal algorithm of DFT(Depth First Search) is : 
GRAPHDFT
[TA is the one dimensional array of size n where n is is the number of nodes in the given graph] 
Mark the start node and push it on to the stack 
Repeat While STACK is not empty
POP STACK 
Add popped node to TA at the next position. 
Mark the unmarked adjacent adjacent nodes of the popped node.
Push the marked nodes of the deleted node (if any) on to the STACK.
[End of While] 
Print TA from the first position as traversal.
Exit.

The above algorithm works in the following manner. 
Consider the following graph
Consider the following graph

Let us assuming the start node as node 'A' let us mark and push the node 'A' on to the stack. So, the stack is:
Depth First Traversal in Graph

when pop stack is executed, the node obtained is 'A'. It is added to the traversed array. So, the traversed array is:
Depth First Traversal in Graph


The marked adjacent nodes to popped node 'A' are, 'B', 'C' and 'E'. Mark and push the nodes 'B', 'C' and 'E' on to the stack (in any order). So, the stack is:
Depth First Traversal in Graph

stack is not empty the processes is repeated.
When pop stack is executed, the node obtained is 'E'. It is added to the traversed array. So the traversed array is:
Depth First Traversal in Graph

The marked adjacent node of popped node 'E' is 'D' mark and push it on to the stack. So, the stack is:
Depth First Traversal in Graph

Stack is not empty the processes is repeated. When pop stack is executed, the node obtained is 'D'. It is added to the traversed array. So, the traversed array is :
Depth First Traversal in Graph

The adjacent nodes of poped node 'D' are 'B' and 'C' but they are already marked node. So, no nodes are pushed. So, the stack is:

Depth First Traversal in Graph

Stack is not empty the proceses is repeated. When pop stack is executed, the node obtained is 'C'. It is added to the traversed array. So, the traversed array is:
Depth First Traversal in Graph

The adjacent node of poped node 'C' are 'A' and 'D' but they are already marked nodes. So, no nodes are pushed. So, the stack is
stack is not empty the processes is repeated. When popped stack is executed, the node obtained is 'B'. It is added to the traversed array. So, the traversed array is 
Depth First Traversal in Graph

the adjacent node of popped node 'B' is 'D' but it is already marked. So, no node are pushed. So, the stack is:
Depth First Traversal in Graph

Stack is empty stop the process. When the TA array is printed we get the Depth first traversal as:

Protected by Copyscape Online Copyright Protection Software

0 comments :

Post a Comment

 
Toggle Footer
Top