**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

**Example**

- Graph Representation
- Depth First Search (DFS) - Graph Traversal
- Breadth First Search (BFS) - Graph Traversal

- Kruskal’s Minimum Spanning Tree Algorithm
- Prim’s Minimum Spanning Tree
- Dijkstra’s shortest path algorithm
- Huffman Coding

## No comments:

## Post a Comment