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
\(\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 \rightsquigarrow v\) and \(v \rightsquigarrow 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\)