Graph Traversal In Data Structure

  ⇰ GRAPH TRAVERSAL :- 

Sometimes it is required to examine all the vertex in a graph in some systematic order, as in the case of binary tree traversal , where we use preorder, postorder or inorder to examine the vertices. For that we use graph traversal. Graph traversal is a technique used to search vertex in a graph to perform any operation there. The graph traversal is also used to conclude the order of vertices visited in the searching process. A graph traversal finds the edges without creating loops. That means using graph traversal techniques we can visit all the vertices of the graph without any looping path.

   ⇰ TYPE OF GRAPH TRAVERSAL :- 

There are following two types of graph traversal techniques :- 

 i > Depth First Search (DFS).

 ii > Breadth First Search (BFS).

 i > Depth First Search (DFS) :- Depth first search of graph traversal is similar to depth first search of tree traversal. This algorithm traverses a graph in a depthward motion and uses a stack. The stack is used to get the next vertex to start a search, when a dead end occurs in any iteration during traversing.

ALGORITHM :-
During execution of algorithm, each node N of graph G will be in one of three states called status of N.

status = 1 (ready state)

status = 2 (waiting state)

status = 3 (processed state)

                       taking this graph

Stack

Step 1:- Initialize all nodes to ready state (state=1).

 Step 2:- Push the starting node A onto stack and chnge its state to waiting state (state=2). 

Step 3:- Repeat step 4 and step 5 untill stack is empty.

Step 4:- Pop the top node N of stack.Process N and change its status to state=3.

Step 5:- Push onto stack all nighbours of N that are still in the ready state, and change their status to waiting state (staus=2). see in above figure.

hence we can see depth wise search here

AFTER PROCESS :- A C E F D B

 ii > Breadth First Search (BFS) :- Breadth first search of graph is similar as breadth first search of tree traversal. Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion and uses a queue. The queue is used  to remember  getting the next vertex to start a search, when a dead end occurs in any iteration during traversing.

ALGORITHM :-

During execution of algorithm, each node N of graph G will be in one of three states called status of N.

status = 1 (ready state)

status = 2 (waiting state)

status = 3 (processed state)

taking this graph

Queue

Step1 :- Initialize all nodes to the ready state (status=1).

Step2 :- Put the starting node A in queue and change its status to the waiting state (status=2).

        

                                          

Step3 :- Repeat step 4 and step 5 untill queue is empty.

Step4 :- Remove the front node N of to the processes state (status=3).

Step5 :- Add to the rear of queue all neighbours of N that are in the ready state (status=1), and change their status to the waiting state (status=2).

Hence we can see bredth wise search

AFTER PROCESS :- A B C E D F

click here for graph in data structure

Share, Follow and please comment if you find anything incorrect, or to share more information about the topic discussed above.