Idriss Rami — Notes

Breadth-first search

3 min read

Breadth-first search (BFS) explores a Graph level by level: visit all vertices one edge away from the start, then all vertices two edges away, then three, and so on. Uses a Queue to track vertices to visit next.

BFS is the natural choice when you want shortest path in an unweighted graph — the level at which you reach a vertex is exactly its distance from the start in number of edges.

Algorithm

  1. Start from a chosen source vertex. Mark it as visited and enqueue it.
  2. While the queue isn’t empty:
    • Dequeue a vertex.
    • Process it (print, record, etc.).
    • Enqueue each unvisited neighbor and mark them visited.
  3. Continue until the queue is empty.

Marking visited prevents cycles from causing infinite loops.

void BFS(int v) {
    queue[++rear] = v;
    state[v] = waiting;
    
    while (!isEmpty_queue()) {
        v = queue[front++];
        printf("%d ", v);
        state[v] = visited;
        
        for (int i = 0; i < n; i++) {
            if (adj[v][i] == 1 && state[i] != visited) {
                queue[++rear] = i;
                state[i] = waiting;
            }
        }
    }
}

A state[] array tracks each vertex as initial, waiting (in queue), or visited. This prevents adding the same vertex to the queue multiple times.

Why a queue

The queue’s FIFO property is what gives BFS its level-by-level behavior:

  • All level-1 vertices get enqueued before any level-2 vertex is added.
  • When you dequeue, you always process the oldest waiting vertex.
  • So all level-1 vertices are processed before any level-2 vertex is processed.

Inductively, this gives breadth-first ordering.

Big O

  • With adjacency matrix: . For each vertex visited, scan all possible neighbors to find adjacency (which is comparisons). Total: vertices × scans.
  • With adjacency list: . Each vertex is dequeued once ( work). Each edge is traversed once when scanning a vertex’s neighbor list ( work).

For sparse graphs (small ), the adjacency list version is dramatically faster.

Use cases

  • Shortest path in unweighted graphs. The first time you visit a vertex, you’ve reached it via the shortest path (fewest edges).
  • Connectivity check. Run BFS from one vertex; if every vertex is visited, the graph is connected.
  • Bipartite check. A graph is bipartite iff you can 2-color it with BFS layers.
  • Web crawling. Treat URLs as vertices, hyperlinks as edges; BFS visits pages in order of click-distance from the start page.
  • Social network “degrees of separation”. BFS from a person finds people at distance 1, 2, 3…

For longest-paths, deepest-traversal, or memory-tight scenarios, Depth-first search is the alternative — same coverage, different order.

BFS for trees

A tree is a special case of a graph (connected, acyclic, edges). Running BFS on a tree gives level-order traversal — see Binary tree traversal. The queue-based level-order algorithm there is essentially BFS.

For weighted shortest paths (where edge costs vary), BFS doesn’t work directly — you need Dijkstra’s algorithm instead. BFS only finds shortest paths when all edges have the same weight.

Graph View

Backlinks