Graph Algorithms (DFS & BFS) Explained

Depth-First Search (DFS)

Depth-First search traverse through a graph in a depth-ward motion. In DFS, it uses a stack to store vertexes.  It uses that stack to remember the next vertex to search when it done all the iterations in the previous vertex.

How to traverse in DFS

  • First take a vertex to start the traverse.
  • Then result it’s value.
  • Add it to the stack.
  • Move to the one of the next vertexes which is connected with.
  •   Then result it’s vale.
  •  Add it to the stack.
  •  Do it until, there is no connected vertex to the current vertex.
  •  Then, remove the current vertex from the stack and search there is a connected another non-visited vertex to the next element which is in the stack.
  •  If not remove that and go to the next element of the stack.
  •  If there is an non-visited connected vertex traverse through it until it finds a dead end.
  • Continue these steps until the stack is empty.

For further understanding let’s see a example,

Example 01:

Capture (1)

H

G  C D

E  F

Stack – 

Result -A B E G F C H D

Explanation of the process of stack :

  • Add B to the stack                                                                                           – B
  •  Find connected vertex of B. Then add that vertex (E) To the stack     – B E
  •  Add G (same as above step)                                                                         – B E G
  •  There aren’t any non-visited and connected vertexes to G.
  • So remove G.                                                                                                   – B E
  • Remove E                                                                                                         – B
  •   Add F to the stack.(as mentioned above)                                                – B F
  • Add C to the stack(as mentioned above)                                                  – B F C
  • Add H to the stack(as mentioned above)                                                 – B F C H
  • Remove H (no connected vertexes)                                                           – B F C
  •  Remove C (no connected vertexes)                                                           – B F
  • Add D to the stack.(as mentioned above)                                                – B F D
  •  Remove D(no connected vertexes)                                                           – B F
  •  Remove F(no non-visited vertexes)                                                             – B
  • Remove B(no non-visited vertexes)

Breadth-First Search (BFS)

Breadth-First search traverse through a graph in a breadth-ward motion. In BFS, it uses a queue to store vertexes.  It uses that queue to remember the next vertex to search when it done all the iterations in the previous vertex.

How to traverse in BFS

  •  First take a vertex to start the traverse.
  • Then result it’s value.
  • Add it to the stack.
  • Result all the connected vertexes of that vertex.
  • Add all of them according to the order which it’s resulted.
  •  Move to next element which is in the queue.
  • Remove that vertex from the queue.
  • Result all the non-visited, connected vertexes of that vertex.
  • Add all of them according to the order which it’s resulted.
  • Then move to next element which is in the queue.
  • Continue this process until queue is empty or it has visited all the connected vertexes in the graph

For further understanding let’s see a example,

Example 01:

Capture1 (1)

Queue –  B

D

G

E

F

C

D

H

Result – A B D G E F C H

Explanation of the process of queue:

  • Add connected vertexes of A                                            – B D G
  • Go to B. Remove B.                                                            – D G
  • Add all non-visited connected vertexes of B                     – D G E F
  • Go to D. Remove D                                                             – G E F
  • Go to G. Remove G(no non-visited vertexes of D)           –  E F
  • Go to E. Remove E(no non-visited vertexes of G)            –  F
  •  Go to F. Remove F.                                                              –
  • Add all non-visited connected vertexes of F                       – C
  • Go to C. Remove C.                                                               –
  • Add all non-visited connected vertexes of C                       – H
  • Go to H. Remove H.

Hence, this is the explanation for Depth-First Search and Breadth-First Search.

written by Binu Senevirathne

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s