C++UCS301
Graphs & ApplicationsC++17

Breadth-First Search

BFS explores vertices by increasing unweighted distance using a queue and produces shortest paths in edge count.

Open this in the visual lab

What to understand

  • Queue frontier
  • Visited marking
  • Distance and parent arrays
  • Connected components

Remember this

  1. 1Mark visited when enqueuing
  2. 2BFS finds shortest unweighted paths
  3. 3Run from every unvisited vertex for a disconnected graph

Detailed notes

BFS expands a frontier in layers. When a vertex is first discovered from distance d, it receives distance d+1, and no later unweighted route can be shorter because all earlier layers have already been processed.

The queue preserves discovery order. Marking visited at enqueue time prevents the same vertex from entering the queue repeatedly through multiple parents.

How it works

  1. 1Initialise distances to an unvisited sentinel.
  2. 2Mark and enqueue the source.
  3. 3Dequeue one vertex and discover each unvisited neighbour.
  4. 4Store parent links for path reconstruction.

Worked trace

Layered traversal from A

A connects to B,C; B to D,E; C to F
  1. 1Queue [A]; visit A and enqueue B,C.
  2. 2Queue [B,C]; visit B and enqueue D,E.
  3. 3Queue [C,D,E]; visit C and enqueue F.
  4. 4Visit D,E,F in queue order.
Result: Visit order A,B,C,D,E,F; distances are 0,1,1,2,2,2

Where it is used

  • Shortest paths in unweighted graphs
  • Social-distance and network-layer queries
  • Connected components and bipartite checking

Common mistakes

  • Marking visited only on dequeue
  • Using BFS for arbitrary weighted shortest paths
  • Traversing only the component containing vertex zero

Complexity analysis

OperationBestAverageWorstExtra space
TraversalO(V+E)O(V+E)O(V+E)O(V)

C++ implementation

C++17 reference
main.cpp

BFS with distance and parent

Parents reconstruct a shortest unweighted path after traversal.

void bfs(const vector<vector<int>>& graph, int source) {
    vector<int> distance(graph.size(), -1), parent(graph.size(), -1);
    queue<int> pending;
    distance[source] = 0;
    pending.push(source);

    while (!pending.empty()) {
        int current = pending.front(); pending.pop();
        for (int next : graph[current]) {
            if (distance[next] != -1) continue;
            distance[next] = distance[current] + 1;
            parent[next] = current;
            pending.push(next);
        }
    }
}
16 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.