Search

Wednesday, September 24, 2014
0 comments

Breadth First Traversal in Graph

11:35 PMWednesday, September 24, 2014

Graph Traversals

Traversing a graph is nothing but to visit or process all the nodes of the graph once and only once. two techniques are popular to traverse the graph. They are Breadth first traversal and depth first traversal. In both the traversal techniques the traversing starts from one of the nodes of the graph and from that starting node all other node are explored. In case of Breadth first traversal from the starting node all the adjacent nodes of that node are explored and the process of exploring is continued. In case of Depth first traversal only one adjacent node (from the adjacent nodes) is explored and the process of exploring continues. Understanding adjacent node is important in both the techniques of graph traversal.

Breadth First Traversal:

As the name of the traversal techniques suggests the traversal explores the nodes of graph by breadth. It means all the adjacent nodes of one selected node are explored first. From the start node all the adjacent nodes of that node are explored. From the list of explored nodes one of the node is selected as the next start node and the unexplored adjacent nodes of that node are explored. Then from the first list of explored nodes the second node is selected as the next start node and the unexplored adjacent nodes of that node are explored. The process continues till the exploration of all the nodes of the graph. The data structure QUEUE finds its application in this traversal. Consider the following graph:
Breadth First Traversal in Graph

The adjacent nodes of the node

A     :     B     C     E
B     :     A     D
C     :     A     D
D     :     B     C     E
E     :     A     D 
The breadth first traversal of the above graph, assuming node 'A' as start node is:
A     B     C     E     D
You can observe from the traversal result that the first node visited is the starting node. Then the next nodes visited are the adjacent nodes of the start node 'A'. In the last 'D' is visited because it is the only unexplored adjacent node of 'B' the exploring of nodes may be in any order. So, the traversal may also be like:

A     C     B     E     D     OR
A     E     B     C     D.
If the start node is 'C' then the BFT (Breadth First Traversal) is:
C     A     D     B     E

The formal algorithm for the BFT is :

GRAPHBFT
[TA is the one dimensional array of size n where n is the number of nodes in the given graph]
Mark the start node and insert it in the QUEUE
Repeat while QUEUE is not empty
Delete QUEUE.
Add delete node to TA at the next position.
Mark the unmarked adjacent nodes of the deleted node.
Insert the marked nodes (if any) of the deleted node in the QUEUE.
[End of while]
Print TA from the first position as traversal.
Exit.

The above algorithm works in the following manner:

Consider the following graph

Breadth First Traversal in Graph

Let us assume the start node as node 'A'. Let us insert node 'A' in the QUEUE. So, the QUEUE is:
Breadth First Traversal in Graph

When QUEUE is deleted, the node obtained is 'A'. It is added to the traversed array. So, the traversed array is:
Breadth First Graph example

The marked adjacent nodes of deleted node 'A' are, B, C and E. Insert the nodes B, C and E in the QUEUE(in any order) So, the QUEUE is:

Breadth First Traversal in Graph

QUEUE is not Empty the process is repeated.
when QUEUE is deleted, the node obtained is 'B'. It is added to the traversed array. So, the traversed array is:
Breadth First Traversal in Graph

The marked adjacent nodes of deleted node 'B' is D. Insert the node D in the QUEUE so, the QUEUE is:
Breadth First Traversal in Graph


QUEUE is not empty the process is repeated.
When QUEUE is deleted, the node obtained is 'C'. It is added to the traversed array. So, the traversed array is:
Breadth First Traversal in Graph

The marked adjacent node of deleted node 'C' are none. So the QUEUE is:
Breadth First Traversal in Graph

QUEUE is not empty the process is repeated.
When QUEUE is deleted, the node obtained is 'E'. It is added to the traversed array. So, the traversed array is:
Breadth First Traversal in Graph

The marked adjacent node of deleted node 'E' are none. So, the QUEUE is:
Breadth First Traversal in Graph

QUEUE is not empty the process is repeated.
When QUEUE is deleted, the node obtained is 'D'. It is added to the traversed array. So, the traversed array is:
Breadth First Traversal in Graph

The marked adjacent nodes of deleted node 'E' are none. So, the QUEUE is:
Breadth First Traversal in Graph

The QUEUE is empty, stop the process.
When the array is printed we get the Breadth First Traversal as:
A     B     C     E     D
Protected by Copyscape Online Copyright Protection Software

0 comments :

Post a Comment

 
Toggle Footer
Top