DFS produces the correct Topologically ordered sequence

Question

Prove that DFS produces the correct topologically ordered sequence.

I am having a hard time understanding the question itself. Should I prove the correctness of DFS? Should I use the pseudocode?

Answer 1

Before I get to the proof, let me just clarify that the algorithm using DFS would be to process edges in decreasing order of finishing times while running DFS on the input graph.

Now to prove that the above algorithm returns a topological sorting, we can use some lemmas about DFS $-$ namely the Parenthesis Theorem as well as the White Path Theorem. I will not get into the proofs of each lemma but we will use the following:

A corollary of the parenthesis theorem, as follows:

Consider vertices $u$ and $v$ in $G$. Then $v$ is a descendant of $u$ in the DFS forest of $G$, if and only if $d(u)<d(v)<f(v)<f(u)$, where $d(x')$ is the discovery time of vertex $x'$ and $f(x')$ is its finish time.

Also, we will use the white path theorem which states that

Vertext $v$ is a descendant of vertex $u$ in the DFS forest if and only if at time $d(u),$ there exists a white path from $u$ to $v.$

Now let $e = (u,v)$ be an edge in the input graph. We want to prove that in our output, $u$ comes before $v$. We can show that by proving that in our DFS traversal, $f(u) > f(v).$

CASE I: $d(u) < d(v)$

By the White Path Theorem, $v$ is a descendant of $u$. This is because at time $d(u)$, there is a white path in $G$, which must be from $u$ to $v$ as there exists edge $e = (u,v)$. Hence, we can use the corollary of the parenthesis theorem to show that $f(u) > f(v).$

CASE II: $d(v) < d(u)$

At time $d(v)$, there is no white path from $v$ to $u$, as that would imply that $G$ has a cycle (meaning that it is not a DAG), and hence $u$ cannot be a descendant of $v$ in the DFS forest of $G$. So by the parenthesis theorem, we have $d(v) < f(v) < d(u) < f(u)$. Again, we proved that $f(u) > f(v)$.

Hope that helped :)