강한 연결 요소(Strongly Connected Components)란 무엇인가? 방향 그래프에서, 임의의 두 정점을 선택했을 때 경로가 존재하며, 서로 반사관계(reflexible)라면, Strong Connected 되었다고 한다. Strongly Connected Components란, 어떤 그래프 G에서 Strongly Connected 되어 있는 그래프의 부분집합을 말한다.
방향 그래프 G = (V, E)의 강한 연결 요소는 정점의 집합 C ⊆ V인데, C에 있는 정점들 u와 v의 모든 쌍에 대해 u → v와 v → u 둘 다 존재하는, 다시 말해서 정점 u와 v는 서로 도달 가능하다.
그래프 G = (V, E)의 강한 연결 요소를 찾는 알고리즘은 G의 전치 그래프를 사용하는데, 여기서 G의 전치 그래프 E(T) = { (u, v) : (u, v) ∈ E }인 그래프 G(T) = (V, E(T))이다. 즉, E(T)는 거꾸로 된 방향을 가진 G의 간선들로 구성된다. G의 인접 리스트 표현이 주어지면, G(T)를 생성하는 시간은 Ο(V + E)이다.
강한 연결 요소를 구하는 알고리즘은 다음과 같다.
1. 각 정점 u에 대해 종료 시간 f(u)를 계산하기 위해 DFS(G)를 호출한다.
2. 전치 행렬 G(T)를 계산한다.
3. DFS(G(T))를 호출한다. f(u)가 가장 높은 정점부터 시작한다.
여기에서, f(u)가 가장 높다는 것은, DFS(G)의 계산 결과 얻어진 종료된 정점들을 스택에 넣어서 꺼낸다는 말과 같은 의미가 된다.
방향 그래프 G = (V, E)의 강한 연결 요소는 정점의 집합 C ⊆ V인데, C에 있는 정점들 u와 v의 모든 쌍에 대해 u → v와 v → u 둘 다 존재하는, 다시 말해서 정점 u와 v는 서로 도달 가능하다.
그래프 G = (V, E)의 강한 연결 요소를 찾는 알고리즘은 G의 전치 그래프를 사용하는데, 여기서 G의 전치 그래프 E(T) = { (u, v) : (u, v) ∈ E }인 그래프 G(T) = (V, E(T))이다. 즉, E(T)는 거꾸로 된 방향을 가진 G의 간선들로 구성된다. G의 인접 리스트 표현이 주어지면, G(T)를 생성하는 시간은 Ο(V + E)이다.
강한 연결 요소를 구하는 알고리즘은 다음과 같다.
1. 각 정점 u에 대해 종료 시간 f(u)를 계산하기 위해 DFS(G)를 호출한다.
2. 전치 행렬 G(T)를 계산한다.
3. DFS(G(T))를 호출한다. f(u)가 가장 높은 정점부터 시작한다.
여기에서, f(u)가 가장 높다는 것은, DFS(G)의 계산 결과 얻어진 종료된 정점들을 스택에 넣어서 꺼낸다는 말과 같은 의미가 된다.