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)
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.
BFS traversal of given graph is: 1 | 2, 3, 4, 5 | 6, 7 | 8
