Breadth First Search (BFS)

Finished :sunglasses:

What is BFS :thinking:

Breadth‑First Search (BFS) is a graph‑traversal algorithm that explores a graph level by level. Starting from a source vertex, it first visits all immediate neighbours (distance 1), then all vertices at distance 2, and so on until every reachable vertex has been discovered.

Algorithm (pseudocode) :grin:

So the key idea is First in first out (FIFO)


BFS(G, s):
    create an empty queue Q
    mark s as visited and enqueue s  ➜  Q ← [s]
    while Q is not empty:
        u ← dequeue(Q)
        for each neighbour v of u in G:
            if v is unvisited:
                mark v as visited
                enqueue v  ➜  Q ← Q ∪ {v}

Time complexity: \(\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)\) Space complexity: \(\mathcal{O}(|\mathcal{V}|)\) (It uses a queue to keep track of the vertices that need to be visited.) Usage - shortest path in unweighted graphs, connectivity checks, level ordering, bipartite testing, etc.

Visualization :look:

The animation below is generated with Manim. It shows BFS expanding a queue and colouring vertices/edges in the order they are discovered.

BFS Example

Check Source Code for Visualization