Breadth First Search or BFS for a Graph

Posted by on Mar 31, 2024

Given a directed graph in the form of an adjacency list, adj[][] and the count of vertex "v".

The task is to perform a breadth-first traversal (BFS) on this graph starting from "0".


Solutions

Method 1: BFS of Graph

Initialize a queue "q" and an array "visited[]" of length "v".

Initially, add the 0-th element of the input list to the queue and keep doing the following until the queue is not empty.

1) Poll the 'top' element from the queue.
2) If the element is already visited, "continue" the loop.
3) Else, if the element is not visited already, add this to the "ans" list and mark it as visited in the "visited[]" array.
4) If the current node has any adjecent elements, add them to the queue.

Complexity

The time complexity of this solution is O(v+e) and space complexity is O(v).

Related


Detect cycle in an undirected graph

Bellman-Ford Algorithm - Shortest Distance with Negative Edge

Check whether a given graph is Bipartite or not

Minimum Spanning Tree (Prim's and Kruskal's algorithm)

Detect Cycle in a Directed Graph (Using BFS or DFS)

Topological Sorting (Using BFS or DFS)

Dijkstra's Single Source Shortest Path Algorithm

Graph representation in Java (Matrix and List)

Depth-First Traversal (DFS) for a graph

Shortest path in Undirected Graph with unit weights