어느 한 정점에서 다른 모든 정점으로 갈 수 있는 방법이 존재하는 정점들의 집합을 말한다.
DFS를 통해 DFS Spanning Tree를 구성하고 상호 연결되어 있지 않은 Sub Tree들을 찾는 것이 핵심.
- Tarjan’s algorithm
- 주어진 방향 그래프의 모든 정점을 방문할 때까지 DFS를 통해 Spanning Tree를 구성한다.
- DFS 트리에서 하나의 강 연결 요소는 첫 시작점이 되는 (서브 트리의 루트가 되는) 정점이 꼭 하나 있다.
- 이 정점을 Leader라고 칭하자.
- 강 연결 요소를 구성하는 정점들은 시작점(Leader)의 후손이라고 할 수 있다. (역은 성립하지 않는다.)
- 리더의 후손 중에 리더보다 더 높은 높이의 정점으로 가는 Back Edge는 없다. (있다면 그 정점이 리더가 될 수 없다.)
- 리더는 자손들의 Back Edge, Forward Edge, Tree Edge들을 모두 포함하고 있다.
- 이러한 성질을 통해 현재 정점이 리더인지를 판별할 수 있다.
- Back Edge를 통해 갈 수 있는 정점을 기록하여 기록된 정점보다 높이가 하나라도 더 높은 정점을 리더로 삼을 수 있다.
- 리더가 다른 강 연결 요소의 리더를 포함하고 있다면 그 두 강 연결 요소는 분리할 수 있다.
- Cross Edge의 경우에는 간선을 통해 이미 강 연결 요소로 구성되어 있는 정점으로 간다면 상관없다.
- 강 연결 요소 구성의 완료 여부는 스택에서 pop되어 있는지 안 되어 있는지를 보면 알 수 있다.
- 하지만 구성되어 있지 않다면 분명히 Cross Edge로 이어진 두 서브 트리를 포함하는 진 조상이 되는 정점이 존재한다. (최소 공통 조상 - LCA : Least Common Ancestor)
- Back Edge와 마찬가지로 갈 수 있는 정점의 번호를 기록해줘야 한다.
- Cross Edge를 통해 연결되는 간선이 생겨 더 큰 규모의 강 연결 요소를 구할 수 있기 때문이다.
- 방문 순서를 저장하는 스택과 위의 리더의 성질을 이용하여 리더의 정점 번호가 나올 때까지 pop 연산을 해서 하나의 강 연결 요소에 대한 정점들을 찾아낼 수 있다.
- 무향 그래프에서는 양방향 간선이라고 볼 수 있기 때문에 Back Edge와 Forward Edge의 구분이 없다.
- 무향 그래프에서는 Cross Edge가 존재할 수 없다.
- Kosaraju’s algorithm
- 주어진 입력에 따라 정방향 그래프와 역방향 그래프 두 가지를 구성한 뒤,
- 정방향으로 모든 정점에 대해 DFS를 진행하며 탐색이 끝나는 순서대로 스택에 push한 뒤,
- 스택이 빌 때까지 정점들을 pop하면서 역방향으로 DFS를 진행하여 pop된 정점을 기준으로 한 번의 dfs에 하나의 강 연결 요소를 구할 수 있다.