7. DFS and Topological Sorting

Visit(E, u):
	pre[u] <- T; T <- T+1
	visited[u] <- True
	FOR v in edges[u]:
		IF not visited[v]:
			Visit(v)
	post[u] <- T; T <- T+1
	
DFS(G):
	T <- 1  # Counter
	visited <- [False] * |V|
	FOR u in V:
		IF not visited[u]:
			Visit(u)

pre: when entered nodes post: when left nodes

Example pre- and post-order intervals:

Reverse post ordering is topological sort since all the nodes it depends on have been called before.

Note: If we’re only interested in the topological sort, we don’t have to track pre- and post-orderings. We can simply append the node to the topological sort at the point where we set the post order and then reverse the array at the very end.

Edge Types

Given an edge $(u,v)$, there are 4 different types of edges:

Type	Pre/Post	Description
Tree edge	$\begin{array}{c}\stackrel{v}{⟷}\\ \stackrel{u}{⟵⟶}\end{array}$	Edge traversed by DFS
Forward edge	$\begin{array}{c}⋮\\ \stackrel{v}{⟷}\\ \stackrel{u}{⟵⟶}\end{array}$	$v$ is a descendant of $u$, but it was already visited through an intermediary descendent of $u$
Back edge	$\begin{array}{c}⋮\\ \stackrel{u}{⟷}\\ \stackrel{v}{⟵⟶}\end{array}$	$u$ is a descendant of $v$, and the edge $(u,v)$ goes back to an ancestor $⟹$ cycle b/c we can travel from $v$ to $u$ and back again.
Cross edge	$\stackrel{v}{⟷}\stackrel{u}{⟷}$	$v$ already visited in different DFS subtree.

$\left[\stackrel{u}{⟷}\stackrel{v}{⟷}\right]$ is impossible b/c $v$ would already be visited in $u$‘s recursive call. Overlapping but not nested intervals are impossible due to the recursive nature of DFS.