CODEWITHSUNDEEP
algorithmgraphtheory
Alex Park
Alex Park

Reputation: 91

In a directed graph, why are finish times used instead of discovery time to determine Strongly Connected Components?

In finding strongly connected components for a directed graph, we use the finish times in the reverse graph for the order. Why can we not use the discovery times in decreasing order? To me, they seem very similar and both could be used. However, in all the logic I found, they only use finish times.

Is there any example that shows that it does not work using discovery time?

Upvotes: 1

Views: 196

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

Per Wikipedia, the key invariant is "if there is a forward path from u to v then u will appear before v". This suggests that we look for a graph where the discovery time violates this. For example, in the graph

  _________
 /        _\|
a---->b---->c

we might visit a then c then b, even though there is a path from b to c. Then we traverse the transpose graph and find the "strongly connected components" {a} and then {c, b} because there's an arc from c to b.

Upvotes: 1

Related Questions