Skip to main content

C Language: Depth First Traversal in Graph

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:

Comments

Popular posts from this blog

difference between structure and union in C Language

In c language article we will see the difference between union and structure. Both are the user define datatype in c language. See the table which is mentioned below: ASP.NET Video Tutorial Series Structure Union1.The keywordstruct is used to define a structure 1. The keyword union is used to define a union. 2. When a variable is associated with a structure, the compiler allocates the memory for each member. The size of structure is greater than or equal to the sum ofsizes of its members. The smaller members may end with unused slack bytes. 2. When a variable is associated with a union, thecompiler allocates thememory by considering the size of the largest memory. So, size of union is equal to the size of largest member. 3. Each member within a structure is assigned unique storage area of location. 3. Memory allocated is shared by individual members of union. 4. The address of each member will be in ascending order This indicates that memory for each member will start at different offset v…

Difference between Linear search and Binary Search in c language

SQL Video Channel : Download all SQL Video



Binary Search Linear Search Works only on sorted items. such as  1,2,3,4,5,6  etc
Works on sorted as well as unsorted items. 12,4,5,3,2,1 etc Very efficient if the items are sorted Very efficient if the items are less and present in the beginning of the list. such as Suppose your list items are : 12,3,4,5,1 and you want to search 12 number then you get beginning in the list. Works well with arrays and not on linked lists. Works with arrays and linked lists.
Number of comparisons are less More number of comparisons are required if the items are present in the later part of the array or its elements are more.

Memory representation of Linked List Data Structures in C Language

Memory representation of Linked List

             In memory the linked list is stored in scattered cells (locations).The memory for each node is allocated dynamically means as and when required. So the Linked List can increase as per the user wish and the size is not fixed, it can vary.

               Suppose first node of linked list is allocated with an address 1008. Its graphical representation looks like the figure shown below:


      Suppose next node is allocated at an address 506, so the list becomes,



  Suppose next node is allocated with an address with an address 10,s the list become,


The other way to represent the linked list is as shown below:




 In the above representation the data stored in the linked list is “INDIA”, the information part of each node contains one character. The external pointer root points to first node’s address 1005. The link part of the node containing information I contains 1007, the address of next node. The last node …