Day 62 — BFS & DFS

Day 62 — BFS & DFS

Stage VI · concept day
Goal: Hand-simulate BFS and DFS on small graphs; understand BFS levels and unweighted shortest paths; DFS discovery/finish times; edge type awareness (tree/back/forward/cross)—tables, not code labs.

Why this matters

BFS and DFS are the two foundational graph traversals. Shortest paths in unweighted graphs, connectivity, cycle detection, topological sort (Day 63), and many compilers/networks algorithms are BFS/DFS wrappers. Hand simulation builds the mental model that coding without understanding lacks.

Theory

Graph exploration

From a start vertex \(s\), traverse means visit vertices (and edges) in a systematic order until a component (or reachable set) is exhausted.
Maintain visited marks so each vertex is processed once (in the basic versions).

Breadth-first search (BFS)

Idea: explore in layers of increasing distance from \(s\).

Queue discipline: FIFO.

High-level:

1. Set \(\mathrm{dist}(s)=0\), parent\((s)=\mathrm{null}\); enqueue \(s\); mark visited.
   
2. While queue nonempty: dequeue \(u\); for each neighbor \(v\) (in agreed order): if not visited, set parent\((v)=u\), \(\mathrm{dist}(v)=\mathrm{dist}(u)+1\), mark visited, enqueue \(v\).

BFS tree: edges \(\{u,v\}\) where parent\((v)=u\).
Levels: vertices with equal \(\mathrm{dist}\).

BFS and shortest paths (unweighted)

Theorem. In an unweighted undirected (or unweighted directed) graph, when BFS from \(s\) finishes, \(\mathrm{dist}(v)\) equals the length of a shortest \(s\)–\(v\) path (∞ if unreachable). Parent pointers reconstruct a shortest path.

Why (invariant sketch). Vertices are first found in nondecreasing distance order; when \(v\) is first reached from \(u\), all shorter paths would have found \(v\) earlier—standard queue invariant.

Does not work with general positive weights—need Dijkstra (Day 64).

Depth-first search (DFS)

Idea: go deep along a path; backtrack when stuck.

Stack discipline: LIFO (recursion stack).

Timestamps: \(\mathrm{disc}(v)\) when first seen; \(\mathrm{fin}(v)\) when adjacency fully processed.

High-level recursive:

time ← 0
DFS-visit(u):
  time ← time+1; disc(u) ← time; color u gray
  for each neighbor v (fixed order):
    if v white: parent(v)←u; DFS-visit(v)
  time ← time+1; fin(u) ← time; color u black

Forest: restart on unvisited vertices for full graph DFS.

Edge types in DFS (directed graphs)—awareness

During DFS on a digraph, classify edge \(u\to v\):

Type	When
Tree	\(v\) first discovered from \(u\)
Back	\(v\) is ancestor of \(u\) (gray) — cycle indicator
Forward	\(v\) is descendant, already finished, not tree edge
Cross	all other (to other branch / finished non-descendant)

Undirected: only tree and back edges (forward/cross coincide with back in undirected classification).
Cycle detection undirected: back edge to visited non-parent.
Cycle detection directed: back edge to gray vertex.

Parenthesis theorem (lite)

Discovery/finish intervals nest or are disjoint—like matched parentheses. Descendants have intervals inside ancestors.

Neighbor order

Always specify: alphabetical, numerical, given adjacency list order. Different orders ⇒ different trees/forests, same distances for BFS.

Complexity culture

Adjacency list: \(O(|V|+|E|)\) time for BFS or DFS.

Worked examples

Graph G1 (running):
Vertices \(S,A,B,C,T\).
Edges undirected: \(S{-}A,S{-}B,A{-}B,A{-}C,B{-}C,B{-}T,C{-}T\).
Neighbor order: alphabetical.

Example 1 — BFS from \(S\)

Queue trace:

Step	Dequeue	Enqueue	dist updates
0	—	\(S\)	\(d(S)=0\)
1	\(S\)	\(A,B\)	\(d(A)=d(B)=1\)
2	\(A\)	\(C\)	\(d(C)=2\)
3	\(B\)	\(T\)	\(d(T)=2\)
4	\(C\)	—
5	\(T\)	—

Parents: \(A\leftarrow S\), \(B\leftarrow S\), \(C\leftarrow A\), \(T\leftarrow B\) (if \(B\) before \(C\) processes \(T\)—when \(B\) dequeued, \(C\) already visited from \(A\), so \(T\) from \(B\)).
Discovery order: \(S,A,B,C,T\).
Shortest \(S\)–\(T\): length 2, e.g. \(S{-}B{-}T\).

Example 2 — DFS from \(S\) (alphabetical)

\(S\) disc=1; visit \(A\) disc=2; from \(A\) visit \(B\) disc=3; from \(B\) visit \(C\) disc=4; from \(C\) visit \(T\) disc=5; \(T\) fin=6; \(C\) fin=7; \(B\) fin=8; \(A\) fin=9; \(S\) fin=10.
(Exact numbers depend on when neighbors already visited—work carefully on paper.)

Example 3 — BFS distances as levels

Level 0: \(\{S\}\); level 1: \(\{A,B\}\); level 2: \(\{C,T\}\).

Example 4 — Unreachable

Add isolated \(X\): BFS from \(S\) never visits \(X\); need multi-source or restart for full cover.

Example 5 — Directed DFS edge types

Arcs: \(1\to2,2\to3,3\to1,1\to4\).
DFS from 1: tree edges \(1\to2\to3\); \(3\to1\) back; \(1\to4\) tree. Cycle detected via back edge.

Example 6 — Undirected cycle

\(C_3\): DFS finds back edge to ancestor.

Example 7 — BFS not for weights

Edges weights 1 on long path and 100 on short edge—BFS by hops ≠ min weight.

Example 8 — Path reconstruction

Follow parents from \(T\) to \(S\): \(T\leftarrow B\leftarrow S\).

Example 9 — DFS forest

Two components: two DFS trees in the forest.

Example 10 — Finish order

In a DAG, reverse finish order is a topological order (Day 63).

Example 11 — Hand table template

Vertex	parent	dist / disc	fin	color timeline

Fill while simulating—do not skip.

Example 12 — Same BFS distances, different trees

Neighbor order \(S\): \(B\) before \(A\) ⇒ parents swap for some nodes; distances unchanged.

Example 13 — Bipartite test via BFS

Color levels alternating; odd cycle ⇒ conflict (Day 65).

Example 14 — Layer counts

Number of vertices at dist \(k\) from \(s\) in a tree equals size of level \(k\).

Example 15 — Call stack depth

DFS depth can be \(\Theta(n)\) on a path—recursion limits culture in implementation (awareness).

Exercises

1. Run BFS on G1 from \(A\); report dist and parents (alpha neighbors).
   
2. Run DFS on G1 from \(A\); report disc/fin (approximate carefully).
   
3. Prove: BFS finds shortest hop paths (write invariant in your words).
   
4. Draw BFS tree and DFS tree of G1 from \(S\).
   
5. Directed: vertices \(1,2,3\), arcs \(1\to2,1\to3,2\to3\). DFS from 1: classify \(2\to3\).
   
6. Detect cycle in undirected G1 via DFS—where is back edge?
   
7. Graph \(P_5\): BFS from end vs middle—distances.
   
8. When is BFS tree a path?
   
9. Multi-source BFS idea (super-source)—one sentence.
   
10. Complete BFS table for \(K_4\) from one vertex.
    
11. CS: web crawler closer to BFS or DFS?
    
12. Why adjacency matrix BFS is \(O(n^2)\) typically.
    
13. Give a graph where DFS tree depth ≫ BFS tree depth.
    
14. Parenthesis: check intervals nest for a DFS you ran.
    
15. Hand-sim Kruskal? (wrong day)—instead: hand-sim BFS levels for star \(K_{1,5}\).
    
16. Digraph with a cross edge: invent 4 vertices.
    
17. Reconstruct path \(S\) to \(T\) in Example 1.
    
18. True/false: DFS always finds shortest paths.
    
19. Connected components via multi-start BFS.
    
20. Color-coding visualization of gray/black in DFS.
    
21. Challenge: diameter via multi BFS twice on trees.
    
22. Edge classification undirected: only tree/back—explain.
    
23. G1: is dist\((S,T)=2\) unique path?
    
24. Write pseudocode BFS and DFS from memory.
    
25. Portfolio: full tables for BFS+DFS on a 6-vertex graph of your design.

CS connection

• Shortest routes unweighted (hops in networks).
  
• Garbage collectors / crawlers.
  
• Cycle detection in undirected/directed graphs.
  
• Topological sort via DFS finish times.
  
• Bipartite check, connected components, SCC algorithms (Kosaraju/Tarjan culture).

Common pitfalls

Pitfall	What to do instead
Forgetting visited mark	Mark when enqueued (BFS) / discovered (DFS)
BFS for weighted graphs	Dijkstra/Bellman-Ford
Ambiguous neighbor order	Fix order before sim
DFS “shortest” claim	False in general
Mixing disc and fin	Two timestamps

Checkpoint

• BFS queue sim with dist/parent table
  
• DFS disc/fin table
  
• Shortest unweighted theorem statement
  
• Edge types awareness (directed)
  
• Cycle detection rules
  
• Exercises 1–15
  
• G1 both algorithms cold

Two personal takeaways:

1. …
   
2. …

Selected mini-solutions

3. Invariant: queue holds vertices of at most two consecutive distances; first time reached is minimal hops.
   
4. When the graph is a path starting at an endpoint (BFS tree unique path).
   
5. Often BFS (politeness layers) or priority—varies.
   
6. False.
   
7. No—\(S{-}A{-}C{-}T\) length 3; \(S{-}B{-}T\) and \(S{-}A{-}B{-}T\) etc.; two hop: \(SBT\), and \(S{-}?\) \(S{-}A{-}C{-}T\) is 3; is \(S{-}B{-}C{-}T\) 3; two-hop paths: \(SBT\) only? Also no \(S{-}A{-}T\) edge. So unique length-2 path \(S{-}B{-}T\) if \(C\) not adjacent \(S\). Yes unique.

Deepening notes

BFS invariant (one more time)

At all times, the queue contains vertices of distance \(k\) and/or \(k+1\) only for some \(k\), and all vertices of distance \(<k\) are settled. First discovery is shortest.

DFS timestamp example table skeleton

\(v\)	disc	fin	parent

Fill for G1 until automatic.

Edge type detection rules (directed)

• Tree: discover white
  
• Back: to gray
  
• Forward/cross: to black (distinguish by interval nest)

Extra drills

D1. BFS from \(T\) on G1.
D2. DFS from \(B\) on G1.
D3. Bipartite test via BFS coloring on G1 (will fail).
D4. Components via multi-source BFS on a disconnected graph.
D5. Directed cycle via gray back edge invent.
D6. Reconstruct three paths using parents.
D7. Compare BFS trees under two neighbor orders.
D8. Diameter of a tree via double BFS method outline.

Flash

BFS queue FIFO → hops; DFS stack LIFO → disc/fin; undirected edges tree/back; \(O(n+m)\) list.

Exam drill block

E1. BFS from a leaf of a path \(P_6\): write dist and parent arrays.
E2. BFS on \(K_{1,4}\) from the center; from a leaf.
E3. Prove: first time BFS reaches \(v\), \(d(v)=\delta(s,v)\) (unweighted).
E4. DFS disc/fin on a rooted binary tree shape (root + two children + one grandchild).
E5. Classify undirected edges as tree/back on a unicyclic graph.
E6. Directed: invent a back edge to gray; state cycle.
E7. Reconstruct shortest path \(s\) to \(t\) from parent pointers.
E8. Multi-source BFS: all vertices distance to nearest hospital (idea).
E9. True/false: (i) DFS always finds shortest hops (ii) BFS tree depends on neighbor order (iii) \(O(n+m)\) with adj lists.
E10. Diameter of a tree via two BFS runs (method outline).

Mini solutions

E1. Distances \(0,1,2,3,4,5\) along the path.
E2. From center all leaves dist 1; from leaf: center 1, other leaves 2.
E9. F; T; T.
E10. BFS from arbitrary \(u\) to farthest \(x\); BFS from \(x\) to farthest \(y\); \(\mathrm{diam}=d(x,y)\).

Complexity and representation

Representation	BFS/DFS time
Adj lists	\(\Theta(n+m)\)
Adj matrix	\(\Theta(n^2)\)

Prefer lists for sparse graphs. Queue (BFS) vs stack/recursion (DFS).

Synthesis

BFS layers = hop distances; DFS timestamps structure the recursion tree and classify edges. Unweighted shortest paths are BFS, not Dijkstra. Undirected: tree + back edges; directed: tree/back/forward/cross. Both are \(O(n+m)\) workhorses for connectivity, bipartiteness (BFS coloring), and cycle detection.

S1. Full BFS table on a 7-vertex graph with a cycle.
S2. Full DFS disc/fin table on the same graph.
S3. Cold: why FIFO ⇒ shortest hops; one sentence each for back edge meanings undirected vs directed.
S4. Bipartite test: BFS 2-color a cycle \(C_5\) (fail) and \(C_6\) (succeed).
S5. Parent-pointer path reconstruction: write the reverse-walk algorithm in three lines.

Tomorrow

Day 63 — DAGs & topological order: equivalent defs; Kahn vs DFS; longest path DP; critical path lite.