Graph traversals

ACompressed recap

🧾

BFS: queue, mark on enqueue, levels give fewest-edge distances, BFS tree V − 1 edges, Θ(V + E). DFS: d/f times 1 … 2V, parenthesis theorem, tree/back/forward/cross; directed cycle ⇔ back edge; undirected only tree/back. Topological sort: decreasing finish or Kahn; components: one start each; SCCs by Kosaraju.

BMerged rule card

6.1.1 Breadth-first search: levels and unweighted shortest paths

• 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.

6.1.2 Depth-first search: discovery and finish times, edge classification

• DFS: d[u] on discovery, f[u] on finish; times 1 … 2V; Θ(V + E).
• Parenthesis: intervals nested or disjoint; descendant ⇔ d[u] < d[v] < f[v] < f[u].
• Tree (white), back (grey), forward (black descendant), cross (black, d[v] < d[u]).
• Directed cycle ⇔ back edge. Undirected: only tree and back.

6.1.3 Topological sort, cycle detection, connected and strongly connected components

• Topological order (DAG only): decreasing finish time, or Kahn (in-degree 0); Θ(V + E).
• Cycle: back edge (directed), visited non-parent (undirected), Kahn stalls.
• Components: one BFS/DFS start per component; forest has V − E.
• SCCs (Kosaraju): DFS, reverse edges, DFS by decreasing finish; condensation is a DAG.

CInterleaved GATE-style questions

Q1NAT1 markBFS

BFS from D on the six-town graph: distance to A?

Numerical answer: ________

Q2MCQ1 markBFS order

BFS from F on the six-town graph with alphabetical neighbours visits the vertices in which order?

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

Q3NAT2 marksBFS tree

A connected graph has 18 vertices and 30 edges. How many non-tree edges does its BFS leave?

Numerical answer: ________

Q4NAT1 markDFS times

In the six-town DFS from A (alphabetical), what is f[D]?

Numerical answer: ________

Q5MCQ1 markEdge type

In a DFS of a directed graph, edge p → q is found with q already black and d[q] < d[p]. It is a:

• (A) tree edge
• (B) back edge
• (C) forward edge
• (D) cross edge

Q6NAT2 marksTopological orders

DAG: p → q, p → r, q → s, r → s. Number of topological orders?

Numerical answer: ________

Q7NAT2 marksComponents

An undirected forest with 15 vertices has 4 connected components. How many edges?

Numerical answer: ________

Q8MSQ2 marksFacts

Which are true?

• (A) A topological order is unique for any DAG.
• (B) Every DAG has at least one topological order.
• (C) Condensing the SCCs of any directed graph gives a DAG.
• (D) Kahn's algorithm can detect a cycle.

DAnswer Vault