In this post, 20 Algorithm lecture is introuduced.

CLRS chater 22.3 ~ 22.5의 내용을 다룬다.

22.4 Topological Sort

이전 강의 참고.

22.5 Stronly connected components

Direct graph G에 대해서, strongly connected component $C$는 $C \subseteq V$ 이며, $C$에 있는 모든 pair $(u, v)$ 에 대해 $u$에서 $v$로의 path와 $v$에서 $u$로의 path가 모두 존재하는 maximal set of vertices이다.

Strongly connected component를 구하기 위해서 $G^T = (V, E^T)$ 를 만들어야 하며 이 시간은 $O(V+E)$ 이다. $G, G^T$는 같은 stronlgly connected components를 가진다.

다음은 strongly connected components를 구하는 pseudocode이다.

STRONGLY-CONNECTED-COMPONENTS(G)
1 call DFS(G) to compute u.f for each vertex
2 compute G^T
3 call DFS(G^T), but in the main loop of DFS, consider the vertices in order of decreasing u.f
4 output the vertices of each tree in the depth-first foreset formed in line 3 as a separate strongly connected component

Lemma 22.13

Lemma 22.14

Corollary 22.15

Theorem 22.16

STRONGLY-CONNECTED-COMPONENTS 프로시저는 directed graph G에 대해 정확히 strongly connecte components를 구한다.