0
49kviews
Explain DFS and BFS algorithm with example.
6
6.2kviews

Depth First Search:

The general idea behind depth first traversal is that, starting from any random vertex, single path is traversed until a vertex is found whose all the neighbors are already been visited. The search then backtracks on the path until a vertex with unvisited adjacent vertices is found and then begin traversing a new path starting from that vertex, and so on. This process will continue until all the vertices of the graph are visited.

//Algorithm for DFS()

Step1. Initialize all the vertices to ready state (STATUS = 1)

Step2. Put the starting vertex into STACK and change its status to waiting (STATUS = 2)

Step 3: Repeat Step 4 and 5 until STACK is EMPTY

Step 4: POP the top vertex from STACK, Process the vertex, Change its status to processed state (STATUS = 3)

Step 5: PUSH all the neighbors in the ready state (STATUS = 1) to the STACK and change their status to waiting state (STATUS = 2)

Step 6: Exit.

The general idea behind breadth first traversal is that, start at a random vertex, then visit all of its neighbors, the first vertex that we visit, say is at level ‘0’ and the neighbors are at level ‘1’. After visiting all the vertices at level ‘1’ we then pick one of these vertexes at level ‘1’ and visit all its unvisited neighbors, we repeat this procedure for all other vertices at level ‘1’. Say neighbors of level 1 are in level 2, now we will visit the neighbors of all the vertices at level 2, and this procedure will continue.

// algorithm for BFS()

Step1. Initialize all the vertices to ready state (STATUS = 1)

Step2. Put the starting vertex into QUEUE and change its status to waiting (STATUS = 2)

Step 3: Repeat Step 4 and 5 until QUEUE is EMPTY

Step 4: Remove the front vertex from QUEUE, Process the vertex, Change its status to processed state (STATUS = 3)

Step 5: ADD all the neighbors in the ready state (STATUS = 1) to the RARE of the QUEUE and change their status to waiting state (STATUS = 2)

Step 6: Exit.