Skip to main content

Breadth first traversal for a Graph

Breadth First Traversal (BFS) is a graph traversal algorithm that visits all the vertices of a graph in breadth-first order, i.e., it visits all the vertices at the same level before moving to the vertices at the next level.

Breadth First Traversal for a Graph

The algorithm starts at the root node (or any arbitrary node) of the graph and visits all its adjacent nodes (also called neighbors). Then, it visits all the unvisited nodes at the next level, and so on until all the vertices have been visited.

To keep track of the visited nodes, BFS uses a queue data structure. The algorithm works as follows:

  1. Start by visiting the root node and enqueue it into a queue.
  2. While the queue is not empty, dequeue the next node from the queue.
  3. For each unvisited neighbor of the dequeued node, mark it as visited and enqueue it into the queue.
  4. Repeat steps 2 and 3 until the queue is empty.

The order in which the nodes are visited by BFS forms a breadth-first search tree or level-order tree. BFS can be used to find the shortest path between two nodes in an unweighted graph, as the algorithm always visits the vertices in increasing order of their distance from the root node.

Implementation of BFS using adjacency list. Here given code implementation process.

In above program is capable to deal with directed and undirected graph which is form of adjacency list.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment