Explain with example DFS and BFS traversal of graph.
- Most graph problems involve traversal of a graph. Traversal of a graph means visit each node exactly once.
- Two commonly used graphs traversal techniques are
- Depth First Search (DFS)
- Breadth First Search (BFS)
Depth First Search (DFS)
- It is like preorder traversal of tree.
- Traversal can start from any vertex vi.
- Vi is visited and then all vertices adjacent to vi are traversed recursively using DFS.
- Since graph can have cycles, we must avoid re-visiting a node. To do this when we visit a vertex V, we marks it visited as visited should not be selected for traversal.
Breadth First Search (BFS)
- This methods starts from vertex V0.
- V0 is marked as visited. All vertices adjacent to V0 are visited next.
- Let vertices adjacent to V0 are V1, V2, V3, V4.
- V1, V2, V3 and V4 are marked visited.
- All unvisited vertices adjacent to V1, V2, V3, V4 are visited next.
- The method continuous until all vertices are visited.
- The algorithm for BFS has to maintain a list of vertices which have been visited but not explored for adjacent vertices. The vertices which have been visited but not explored for adjacent vertices can be stored in queue.
- Initially the queue contains the starting vertex.
- In every iteration, a vertex is removed from the queue and its adjacent vertices which are not visited as yet are added to the queue.
- The algorithm terminates when the queue becomes empty.
