Breadth-first search: levels and unweighted shortest paths

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Adjacency list space for a graph? from Lesson 0.2.3
• Queue order? from Lesson 0.2.1
• Σ degrees in an undirected graph? from Lesson 0.2.3

1 · The Hook

🎣

"Fewest flights from Delhi to anywhere": with every hop counting 1, the answer is found by exploring outward in rings: everything one hop away, then everything two hops away, and so on. That is breadth-first search (BFS). It is the basis of unweighted shortest paths, and GATE asks for BFS orders, levels and BFS-tree properties.

2 · Predict First

🤔

In the six-town graph (ignore the road lengths, count roads), how many roads does the shortest route from A to F use?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

A's neighbours are B and C (1 road); D and E are 2 roads away; F is reached from D or E: 3 roads.

The algorithm

BFS(G, s):
    mark s visited; dist[s] = 0; enqueue(s)
    while queue not empty:
        u = dequeue()
        for each neighbour v of u:            // alphabetical in these notes
            if v not visited:
                mark v visited; dist[v] = dist[u] + 1; parent[v] = u
                enqueue(v)

• A vertex is marked when it is enqueued, so it enters the queue only once.
• Vertices come out of the queue in non-decreasing distance: all of level 0, then all of level 1, then level 2 ….

What BFS gives

• dist[v] = the smallest number of edges from s to v (unweighted shortest path).
• The BFS tree (edges u → v where parent[v] = u) has V − 1 edges if the graph is connected; the path in the tree from s to v is a shortest path.
• In an undirected graph, every non-tree edge joins two vertices whose levels differ by at most 1.

Cost

Each vertex is enqueued and dequeued once; each adjacency list is scanned once: Θ(V + E) with adjacency lists, Θ(V²) with an adjacency matrix.

Valid BFS orders

With any neighbour order allowed, an order is a valid BFS order if, when each vertex u is dequeued, its not-yet-seen neighbours appear next in the order as one block (in any order among themselves).

4 · Visual

BFS from A on the six-town graph. Red: BFS-tree edges. Dashed: non-tree edges (each joins levels that differ by at most 1). Order A, B, C, D, E, F.

5 · Worked Examples

Example 1 Easy

BFS from F on the six-town graph (alphabetical neighbours): order?

Solution

F; then D, E; D adds B, C; E adds nothing new; B adds A: F, D, E, B, C, A.

Example 2 Medium

BFS from D: how many vertices are at level 1?

Solution

D's neighbours B, C, E, F: 4 (A is at level 2).

Example 3 GATE

A connected undirected graph has 30 vertices and 45 edges. How many edges are not in its BFS tree?

Solution

The BFS tree has 29 edges, so 16 are non-tree edges.

6 · GATE Traps

⚠️

• Mark vertices when enqueued, not when dequeued, or they may enter the queue twice.
• BFS gives shortest paths only when every edge counts 1 (unweighted).
• Several BFS orders can be valid when ties in neighbour order are allowed; these notes use alphabetical order.
• Θ(V + E) with lists; Θ(V²) with a matrix.

7 · Memory Hook

🧠

"BFS: a queue, ring by ring, fewest edges first."

8 · Connect the Dots

BFS explores in rings with a queue. The next lesson replaces the queue by a stack (recursion) and goes as deep as possible first: depth-first search, with its discovery and finish times.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markBFS distance

BFS from A on the six-town graph: distance (number of roads) to F?

Numerical answer: ________

Q2NAT1 markLevels

BFS from C on the six-town graph: how many vertices are at level 1?

Numerical answer: ________

Q3MCQ1 markBFS cost

BFS on a graph stored as adjacency lists runs in:

• (A) Θ(E log V)
• (B) Θ(V²)
• (C) Θ(V + E)
• (D) Θ(V)

Q4NAT2 marksBFS tree

A connected undirected graph has 25 vertices and 42 edges. How many edges are not in the BFS tree?

Numerical answer: ________

Q5MSQ2 marksValid BFS orders

Which are valid BFS orders of the six-town graph starting at A (neighbours may be taken in any order)?

• (A) A, B, C, D, E, F
• (B) A, C, B, E, D, F
• (C) A, B, C, E, D, F
• (D) A, B, D, C, E, F

10 · Rule Card

• BFS: queue; mark on enqueue; levels in non-decreasing order.
• dist = fewest edges (unweighted shortest path); BFS tree has V − 1 edges (connected).
• Undirected non-tree edges join levels differing by ≤ 1.
• Θ(V + E) lists, Θ(V²) matrix.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

breadth-first searchqueue-based traversallevelsunweighted shortest pathBFS treevalid BFS orderBFS cost Θ(V + E)

12 · Answer Vault