Topological Sort & SCC

Summarized notes on Introduction to Algorithms, Chapter 22

---

Topological Sort

• DFS can be used to perform topological sort on directed acyclic graph, or DAG
• topological sort is a linear ordering of all vertices such that is $G$ contains edge $(u,v)$ then $u$ appears before $v$ in ordering → sort by highest to smallest finish time
• the result of topological sort is a linked list of vertices
• result can be visualized as ordering of vertices along a horizontal line so that all directed edges go from left to right
• linear sort is possible only if there are no cycles
  • → DFS cannot yield any back edges; otherwise there is a cycle

Complexity

Running Time
$\mathrm{\Theta }(V+E)$	Topological sort including DFS

Strongly Connected Components

• finding strongly connected components is an application of DFS
• strongly connected component is maximal set of vertices $C\subseteq V$ such that for every vertex $u$ and $v$ in $C$, both $u⇝v$ and $v⇝u$
• given algorithm:
  1. run DFS on $G$ to compute finish time for each vertex
  2. computes transpose $G^T$ where edge directions are reversed
  3. run DFS on $G^T$ in order of decreasing finish times
  4. output vertices of each tree in depth-first forest; these are the strongly connected components
• the component graph is a DAG

Complexity

Running Time
$O(V+E)$	Compute transpose $G^T$