Graph Traversals - BFS

BFS (Breadth First Search)

BFS traversal of a graph, produces a spanning tree as final result. Spanning Tree is a graph without any loops. We use Queue data structure with maximum size of total number of vertices in the graph to implement BFS traversal of a graph.

We use the following steps to implement BFS traversal...
  • Step 1: Define a Queue of size total number of vertices in the graph.
  • Step 2: Select any vertex as starting point for traversal. Visit that vertex and insert it into the Queue.
  • Step 3: Visit all the adjacent vertices of the vertex which is at front of the Queue which is not visited and insert them into the Queue.
  • Step 4: When there is no new vertex to be visit from the vertex at front of the Queue then delete that vertex from the Queue.
  • Step 5: Repeat step 3 and 4 until queue becomes empty.
  • Step 6: When queue becomes Empty, then produce final spanning tree by removing unused edges from the graph

No comments: