1 · DFS, edge types, topological sort, SCCs
DPV Ch 31 exam problem Exam 1 Q7 was DPV 3.3 word for word. The likeliest Ch 3 problem is another DPV 3.x hand trace (3.1, 3.2, 3.4) with the "alphabetically first" rule, or a short design question from HW3.
| Question says | Do this |
|---|---|
| "Perform DFS … pick the alphabetically first … give pre and post numbers" | Run the stack-of-calls method below. Clock starts at 1 and ticks on every pre and every post. |
| "Classify each edge" | Undirected: tree or back. Directed: tree / forward / back / cross from the pre/post intervals. |
| "Does it have a cycle?" / "Is it a DAG?" | Cycle exists iff DFS found a back edge. |
| "What topological order is found?" | List vertices by decreasing post. |
| "Sources and sinks?" | Source: no incoming edges. Sink: no outgoing edges. Read them off the graph. |
| "How many topological orderings?" | Find the forced chain, multiply the number of ways to order each free group (Exam 1: \(2\times2\times2 = 8\)). |
| "Run the SCC algorithm" | DFS on \(G^R\) (alphabetical), list decreasing post, then explore \(G\) in that order. Each new explore = one SCC. |
| "Minimum edges to make it strongly connected" | \(\max(\#\text{source SCCs}, \#\text{sink SCCs})\) if more than one SCC, else 0. |
1. DFS with a clock
DPV's procedure. explore(v) visits everything reachable from \(v\). dfs calls explore from every vertex not yet visited, so it covers the whole graph.
procedure explore(G, v)
visited(v) = true
previsit(v) // pre(v) = clock; clock = clock + 1
for each edge (v, u) in E:
if not visited(u): explore(G, u)
postvisit(v) // post(v) = clock; clock = clock + 1
procedure dfs(G)
for all v in V: visited(v) = false
clock = 1
for all v in V: // in alphabetical order on the exam
if not visited(v): explore(G, v)- Every vertex gets a pre and a post. With \(n\) vertices the clock runs 1 to \(2n\). Check this at the end: the largest number must be \(2n\).
- Running time \(O(|V|+|E|)\) with adjacency lists (each vertex explored once, each edge looked at once directed, twice undirected). With an adjacency matrix it is \(O(|V|^2)\).
- \([\text{pre}(u), \text{post}(u)]\) is the time \(u\) sits on the call stack. Two intervals are always nested or disjoint, never partially overlapping. Nested means ancestor/descendant.
2. Tracing DFS by hand (alphabetical tie-break)
Do it with a call stack, not by staring at the picture. This is where points are lost.
- Write the adjacency list of every vertex with neighbours sorted alphabetically. For a directed graph list only out-neighbours.
- Start at the alphabetically first vertex. Push it, write its pre = current clock, add 1.
- Look at the top of the stack. Scan its list from where you left off. The first unvisited neighbour: push it, give it a pre. Every visited neighbour you pass: note the edge for classification later.
- If the top vertex has no unvisited neighbours left: pop it, write its post = clock, add 1.
- When the stack empties, the outer loop picks the alphabetically first unvisited vertex and you continue. The clock does not reset.
Worked: DPV 3.3 (Exam 1 Q7)
Adjacency lists: A: C · B: C · C: D, E · D: F · E: F · F: G, H · G: none · H: none.
| clock | event | stack after | why |
|---|---|---|---|
| 1 | pre A | A | A is alphabetically first |
| 2 | pre C | A C | A's only neighbour |
| 3 | pre D | A C D | C's list is D, E: take D |
| 4 | pre F | A C D F | D's only neighbour |
| 5 | pre G | A C D F G | F's list is G, H: take G |
| 6 | post G | A C D F | G has no out-edges |
| 7 | pre H | A C D F H | F's next neighbour |
| 8 | post H | A C D F | H has no out-edges |
| 9 | post F | A C D | F's list done |
| 10 | post D | A C | D's list done |
| 11 | pre E | A C E | C's next neighbour |
| 12 | post E | A C | E → F: F already visited (cross edge) |
| 13 | post C | A | |
| 14 | post A | (empty) | |
| 15 | pre B | B | outer loop: B is the first unvisited vertex |
| 16 | post B | (empty) | B → C: C already finished (cross edge) |
| A | B | C | D | E | F | G | H | |
|---|---|---|---|---|---|---|---|---|
| pre/post | 1/14 | 15/16 | 2/13 | 3/10 | 11/12 | 4/9 | 5/6 | 7/8 |
- (b) Sources: A, B. Sinks: G, H.
- (c) Topological order (decreasing post): B, A, C, E, D, F, H, G.
- (d) Every order must be {A, B} then C then {D, E} then F then {G, H}. Each pair can go either way: \(2\times2\times2 = \mathbf{8}\).
3. Edge types
Undirected graphs: only tree and back edges
A tree edge is one that explore used to discover a new vertex. Every other edge is a back edge (to an ancestor). There are no cross edges: if \(\{u,v\}\) is an edge and \(u\) is explored first, \(u\) must reach \(v\) before \(u\) finishes, so \(v\) becomes a descendant of \(u\). Each undirected edge is classified once (the first time it is looked at).
Directed graphs: tree, forward, back, cross
| Edge \(u \to v\) | Meaning | Interval rule |
|---|---|---|
| Tree | explore(u) called explore(v) | \(\text{pre}(u) < \text{pre}(v) < \text{post}(v) < \text{post}(u)\) \([_u\,[_v\,]_v\,]_u\) |
| Forward | \(u\) to a non-child descendant | |
| Back | \(u\) to an ancestor (still on the stack) | \(\text{pre}(v) < \text{pre}(u) < \text{post}(u) < \text{post}(v)\) \([_v\,[_u\,]_u\,]_v\) |
| Cross | to an already finished vertex that is neither ancestor nor descendant | \(\text{post}(v) < \text{pre}(u)\) \([_v\,]_v\,[_u\,]_u\) |
- Tree vs forward cannot be told apart from the numbers alone. It depends on whether this edge discovered \(v\). In your trace, the edge you pushed along is tree; an edge to a vertex that is already finished and inside \(u\)'s interval is forward.
- A cross edge always points backward in time. The pattern \([_u\,]_u\,[_v\,]_v\) (\(\text{post}(u) < \text{pre}(v)\)) is impossible for an edge \(u\to v\): \(v\) was unvisited while \(u\) was open, so \(v\) would have become \(u\)'s descendant.
- During the trace: neighbour on the stack → back; neighbour finished and inside \(u\)'s interval → forward; neighbour finished before \(u\) started → cross.
4. Cycles, DAGs, topological order
- A directed graph has a cycle iff DFS finds a back edge. (Back edge \(u\to v\) plus the tree path \(v \leadsto u\) is a cycle. Conversely, on a cycle the first vertex \(v_i\) discovered reaches all the others, so its predecessor \(v_{i-1}\) on the cycle is a descendant, and \(v_{i-1}\to v_i\) is a back edge.)
- In a DAG, every edge \(u\to v\) has \(\text{post}(u) > \text{post}(v)\). So decreasing post is a topological order, found in linear time.
- Highest post is a source. Lowest post is a sink. Every DAG has at least one source and at least one sink.
- Alternative linearization: repeatedly output a source and delete it (DPV 3.14, also linear time with in-degree counts).
Counting topological orders
Break the DAG into groups that must come in a fixed sequence, count the orderings inside each group that respect its own edges, multiply. If the groups are not that clean, count by cases: choose which source goes first, delete it, recurse. Exam 1 Q7 (DPV 3.3): \(\{A,B\}\to C\to\{D,E\}\to F\to\{G,H\}\) gives 8.
5. Connected components (undirected)
Each call of explore from the outer loop of dfs finds one connected component. Keep a counter cc, increment it before each such call, and set ccnum(v) = cc in previsit. Linear time. The number of outer-loop calls is the number of components (DPV 3.1 below has 2).
6. Strongly connected components
\(u\) and \(v\) are strongly connected if there is a path \(u\leadsto v\) and a path \(v\leadsto u\). An SCC is a maximal set of mutually connected vertices. Shrinking each SCC to one node gives the metagraph, which is always a DAG (a cycle among SCCs would merge them into one SCC). Every directed graph is a DAG of its SCCs.
SCC(G):
run dfs on G^R, recording post numbers (alphabetical tie-break on G^R)
for v in V in decreasing post order (from G^R):
if not visited(v): (fresh visited marks)
cc = cc + 1; explore(G, v) (everything newly reached = one SCC)
total time O(|V| + |E|)Why it works (the proof the prof gives)
explorefrom a vertex in a sink SCC visits exactly that SCC, because nothing leads out of it.- If there is an edge from SCC \(C\) to SCC \(C'\), the largest post in \(C\) is bigger than the largest post in \(C'\). So the vertex with the highest post lies in a source SCC.
- The lowest post is not guaranteed to be in a sink SCC. So we can find a source SCC but we need a sink.
- \(G^R\) has the same SCCs as \(G\), and its source SCCs are the sink SCCs of \(G\). So the highest post in a DFS of \(G^R\) is in a sink SCC of \(G\). Explore it in \(G\), remove it, and the next highest remaining post is again in a sink SCC of what's left.
Consequence: SCCs come out sink first, i.e. in reverse topological order of the metagraph.
Source/sink SCCs and making a graph strongly connected
- Source SCC: no incoming metagraph edges. Sink SCC: no outgoing. An SCC with no metagraph edges at all is both.
- Minimum number of edges to add to make \(G\) strongly connected: 0 if \(G\) already has one SCC, otherwise \(\max(\#\text{sources}, \#\text{sinks})\).
- Why at least that many: every source SCC needs a new incoming edge and every sink SCC needs a new outgoing edge, and one new edge gives at most one of each. Why that many suffice is a known theorem (Eswaran–Tarjan). On the exam, give the number and a concrete set of edges, usually from sink SCCs to source SCCs.
7. BFS vs DFS
| BFS | DFS | |
|---|---|---|
| Container | FIFO queue | stack (recursion) |
| Explores | layer by layer (distance 0, 1, 2, …) | as deep as possible, then backs up |
| Gives you | shortest paths in edge count (unit lengths), BFS tree | pre/post numbers, edge types, cycles, topological order, SCCs |
| Time | \(O(|V|+|E|)\) | \(O(|V|+|E|)\) |
| Trap | does not give pre/post or detect back edges directly | DFS depth is not distance from \(s\) |
8. Worked DPV exercises
Try each one on paper first. Numbers checked by code.
DPV 3.1 (undirected): DFS, classify edges, pre/post
Answer
Lists: A: B, E · B: A, C, E · C: B, F · D: G, H · E: A, B, F · F: C, E, I · G: D, H · H: D, G · I: F.
A → B → C → F → E. At E, neighbours A and B are on the stack: back edges E–A, E–B. E finishes (5/6). F → I (7/8). Unwind F, C, B, A. Outer loop restarts at D: D → G → H; H–D is a back edge.
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| pre/post | 1/12 | 2/11 | 3/10 | 13/18 | 5/6 | 4/9 | 14/17 | 15/16 | 7/8 |
Tree edges: A–B, B–C, C–F, F–E, F–I, D–G, G–H. Back edges: E–A, E–B, H–D. Two connected components.
DPV 3.2(a): directed, classify all edges
Answer
Out-lists: A: B, F · B: C, E · C: D · D: B, H · E: D, G · F: E, G · G: F · H: G.
A → B → C → D. D → B: B on the stack (back). D → H → G → F → E. E → D and E → G: on the stack (back). E done 8/9. F → G: on the stack (back). F, G, H, D, C done. Back at B: B → E, E finished inside B's interval (forward). Back at A: A → F, finished inside A's interval (forward).
| A | B | C | D | E | F | G | H | |
|---|---|---|---|---|---|---|---|---|
| pre/post | 1/16 | 2/15 | 3/14 | 4/13 | 8/9 | 7/10 | 6/11 | 5/12 |
Tree: A→B, B→C, C→D, D→H, H→G, G→F, F→E. Forward: B→E, A→F. Back: D→B, E→D, E→G, F→G. Cross: none. (Back edges exist, so it has cycles.)
DPV 3.2(b): directed, classify all edges
Answer
Out-lists: A: B, H · B: F · C: B · D: C, E · E: none · F: C, D, E · G: A, B, F · H: G.
A → B → F → C. C → B: on the stack (back). C done 4/5. F → D. D → C: C finished before D started (cross). D → E, E done 7/8, D done 6/9. F → E: finished inside F's interval (forward). F 3/10, B 2/11. A → H → G. G → A: on the stack (back). G → B and G → F: finished before G started (cross).
| A | B | C | D | E | F | G | H | |
|---|---|---|---|---|---|---|---|---|
| pre/post | 1/16 | 2/11 | 4/5 | 6/9 | 7/8 | 3/10 | 13/14 | 12/15 |
Tree: A→B, B→F, F→C, F→D, D→E, A→H, H→G. Forward: F→E. Back: C→B, G→A. Cross: D→C, G→B, G→F.
DPV 3.4(i): SCC algorithm
Questions: (a) order SCCs are found, (b) source and sink SCCs, (c) metagraph, (d) minimum edges to add to make it strongly connected. DFS on \(G^R\) is alphabetical.
Answer
Step 1: DFS on \(G^R\). Reverse every edge. Out-lists in \(G^R\) (= in-lists in \(G\)): A: B, E · B: none · C: A, J · D: C · E: none · F: D, H · G: B, H · H: A, I · I: E, G · J: F.
From A: A → B (2/3), A → E (4/5), A done 1/6. From C: C → J → F → D (D → C on stack) D 10/11; F → H → I → G (G's B, H visited) G 14/15, I 13/16, H 12/17, F 9/18, J 8/19, C 7/20.
| \(G^R\) | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| pre/post | 1/6 | 2/3 | 7/20 | 10/11 | 4/5 | 9/18 | 14/15 | 12/17 | 13/16 | 8/19 |
Decreasing post in \(G^R\): C J F H I G D A E B.
Step 2: explore \(G\) in that order. C reaches D, F, J: {C, D, F, J}. J, F already done. H reaches G, I (F is taken): {G, H, I}. I, G, D done. A: {A}. E: {E}. B: {B}.
- (a) Order found: {C,D,F,J}, {G,H,I}, {A}, {E}, {B}.
- (b) Source SCCs: {B}, {E}. Sink SCC: {C,D,F,J}.
- (c) Metagraph edges: {G,H,I}→{C,D,F,J}; {A}→{C,D,F,J}; {A}→{G,H,I}; {E}→{G,H,I}; {E}→{A}; {B}→{G,H,I}; {B}→{A}.
- (d) 2 sources, 1 sink → \(\max(2,1) = \mathbf{2}\) edges. For example C→B and C→E (checked: the result is strongly connected).
DPV 3.4(ii): SCC algorithm
Answer
Step 1: DFS on \(G^R\). Out-lists in \(G^R\): A: E · B: A · C: B · D: A, G · E: B · F: C, H · G: H · H: D, E, I · I: F, H.
From A: A → E → B (B → A on stack) B 3/4, E 2/5, A 1/6. From C: C → B done, C 7/8. From D: D → G → H → I → F (F's C, H visited) F 13/14, I 12/15, H 11/16, G 10/17, D 9/18.
| \(G^R\) | A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|---|
| pre/post | 1/6 | 3/4 | 7/8 | 9/18 | 2/5 | 13/14 | 10/17 | 11/16 | 12/15 |
Decreasing post in \(G^R\): D G H I F C A E B.
Step 2: explore \(G\). D → H → F → I, H → G: {D,F,G,H,I}. C: only F, taken: {C}. A → B, B → E: {A,B,E}.
- (a) Order found: {D,F,G,H,I}, {C}, {A,B,E}.
- (b) Source SCC: {A,B,E}. Sink SCC: {D,F,G,H,I}.
- (c) Metagraph: {C}→{D,F,G,H,I}; {A,B,E}→{D,F,G,H,I}; {A,B,E}→{C}.
- (d) 1 source, 1 sink → 1 edge, from the sink SCC to the source SCC, e.g. D→A (checked).
9. Design problems (HW3 style)
For each: state the graph, the algorithm in one or two lines, why it is correct, and the running time. That is what full credit looks like.
DPV 3.15 Computopia (HW3 P3, also in HW3 solutions)
(a) Intersections = vertices, one-way streets = directed edges. The mayor claims \(G\) is strongly connected. Pick any \(s\). Explore from \(s\) in \(G\) (does \(s\) reach everyone?) and explore from \(s\) in \(G^R\) (does everyone reach \(s\)?). Both reach all vertices ⟺ strongly connected, since any \(u\leadsto s\leadsto v\). Two explores plus building \(G^R\): \(O(|V|+|E|)\). (Or: run the SCC algorithm and check there is exactly one SCC.)
(b) Let \(t\) = town hall. Claim: every vertex reachable from \(t\) can reach \(t\). That means \(t\)'s SCC is a sink SCC: if some edge left \(t\)'s SCC to \(w\), then \(w\) is reachable from \(t\) but cannot get back. Check: compute the SCCs (linear), then check no edge leaves \(t\)'s SCC. Or: \(R\) = explore from \(t\) in \(G\), \(R'\) = explore from \(t\) in \(G^R\), answer yes iff \(R\subseteq R'\). Linear.
DPV 3.16 Minimum semesters (HW3 P4, also in HW3 solutions)
The prerequisite graph is a DAG. The answer is the number of vertices on the longest path. Topologically sort by DFS (decreasing post). Set \(\text{sem}(v) = 1\) for all \(v\); for each \(u\) in topological order and each edge \(u\to w\): \(\text{sem}(w) = \max(\text{sem}(w), \text{sem}(u)+1)\). Output \(\max_v \text{sem}(v)\). Correct because when \(u\) is processed all its prerequisites are already final. \(O(|V|+|E|)\).
DPV 3.22 A vertex that reaches all others
Run DFS on \(G\). Let \(s\) be the vertex with the highest post. Explore from \(s\) again with fresh marks. If it reaches every vertex, answer yes (\(s\)); otherwise no. Why: a vertex that reaches all must be in the unique source SCC, and the highest post always lies in a source SCC. If there are two source SCCs, nobody reaches everything and the test from \(s\) fails, correctly. \(O(|V|+|E|)\).
DPV 3.23 Count paths from s to t in a DAG
Topologically sort. \(\text{paths}(s)=1\), all others 0. For each \(u\) in topological order, for each edge \(u\to v\): \(\text{paths}(v) \mathrel{+}= \text{paths}(u)\). Output \(\text{paths}(t)\). Each path into \(v\) ends with exactly one edge \(u\to v\), and \(u\) is final before \(v\) is used. \(O(|V|+|E|)\). (Use integers; the count can be exponential.)
DPV 3.11 Cycle through a given edge e (undirected)
Let \(e=\{u,v\}\). Remove \(e\), explore from \(u\). There is a cycle through \(e\) iff \(v\) is still reachable (that path plus \(e\) is the cycle). Linear time.
DPV 3.12 Prove or disprove: edge {u,v} and post(u) < post(v) ⟹ v is an ancestor of u
True. Undirected DFS has only tree and back edges, so one endpoint is an ancestor of the other. A descendant finishes before its ancestor. post(u) < post(v) means \(u\) finished first, so \(u\) is the descendant and \(v\) the ancestor.
HW3 P1 counterexamples (also in HW3 solutions)
(a) "Path \(u\leadsto v\) and pre(u) < pre(v) ⟹ \(v\) is a descendant of \(u\)." Edges A→B, B→A, A→C. DFS from A: B 2/3, C 4/5, A 1/6. Path B→A→C exists and pre(B)=2 < pre(C)=4, but C is a sibling of B, not a descendant.
(b) "If \(u\) has incoming and outgoing edges, its DFS tree has at least two vertices." Edges B→A, C→B. DFS alphabetical: A alone (1/2), B alone (3/4, its out-neighbour A is finished), C alone (5/6). B has an in-edge and an out-edge but its tree is just {B}.
HW3 P2 (stations within 5 links) and HW3 P5 = DPV 3.20 (ancestor labels): one-line ideas
P2. From each station \(s\), run a depth-limited search that stops at depth 5. Plain DFS with visited marks can wrongly block a vertex first reached by a long path, so store the smallest depth seen and re-explore a vertex when it is reached with a smaller depth (or use BFS truncated at depth 5, which gets depths right directly). Collect everything reached.
P5. DFS from the root, keeping the current root-to-node path in an array indexed by depth. At node \(v\) at depth \(d\), its \(k\)th ancestor is path[d − k] (the root if \(d-k \le 0\)), so \(l_{\text{new}}(v) = l(\texttt{path}[\max(0, d-l(v))])\) in \(O(1)\). Read old labels only (write new ones to a separate array). Linear.
10. Self-check
1. Directed DFS gives u = [3, 4] and v = [1, 8]. What kind of edge is u → v?
Back edge: \(\text{pre}(v) < \text{pre}(u) < \text{post}(u) < \text{post}(v)\), so \(v\) is an ancestor of \(u\).
2. Directed DFS gives u = [2, 5] and v = [7, 8]. Can u → v be an edge?
No. \(v\) was unvisited while \(u\) was open, so DFS would have explored \(v\) from \(u\), making it a descendant. (v → u would be a cross edge.)
3. After DFS on a DAG, which vertex is guaranteed to be a sink? A source?
Lowest post is a sink. Highest post is a source.
4. A DAG has edges A→C, B→C, C→D, C→E. How many topological orders?
\(\{A,B\}\) in either order, then C, then \(\{D,E\}\) in either order: \(2\times 2 = 4\).
5. A metagraph has 3 source SCCs and 2 sink SCCs. Minimum edges to add to make the graph strongly connected?
\(\max(3,2) = 3\).
6. Why does the SCC algorithm run DFS on \(G^R\) instead of starting from the highest post in \(G\)?
The highest post in \(G\) is in a source SCC; exploring from there spills into every SCC downstream. The highest post in \(G^R\) is in a source SCC of \(G^R\), which is a sink SCC of \(G\), and exploring \(G\) from a sink SCC finds exactly that SCC.