[Study] SCC (강한 연결 요소)

SCC (Strongly Connected Component)란?

- 어떤 두 정점을 잡든 서로 도달할 수 있는 경로가 있는 부분 방향 그래프

- 유향 그래프 (방향이 있는 그래프)만 SCC를 가진다.

- 한 그래프 내에 여러 개의 SCC가 존재할 수 있다.

- 같은 SCC 모음 내의 노드는 어떤 경로를 통하더라도 다른 노드를 향해 갈 수 있어야 한다.

   즉, 같은 강한 연결 요소에 속하는 정점들은 서로 이동할 수 있는 방향 경로가 반드시 존재한다.

- 시간복잡도 O(V+E)를 가진다.

 

 

 

SCC 알고리즘 구현 방법

코사라주 알고리즘

- 주어진 방향 그래프의 역방향 그래프와 스택을 사용하여 SCC를 구하는 알고리즘.

- 방향 그래프와 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용함.

알고리즘

1. 주어진 방향그래프의 역방향 그래프를 만들어 방향 그래프의 임의의 정점부터 DFS를 수행
2. DFS가 끝나는 순서대로 스택에 삽입함.
3. 아직 방문하지 않은 정점에 대해 다시 DFS를 수행
4. 모든 정점이 스택에 담긴 후에는 스택을 pop하여 나오는 정점부터 역방향 그래프에서 DFS를 수행함. 이미 방문한 정점은 pop만 시행
5. 이때 탐색되는 모든 정점을 SCC로 묶음
6. 스택이 빌 때까지 진행.

 

타잔 알고리즘

- 모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘.

- 코사라주 알고리즘에 비해 적용이 쉽다.

- 방향경로의 시작점으로 다시 돌아갈 수 있어야 같은 SCC에 속하는 것이라는 점을 이용함.

- 같은 SCC에 속하는 노드들은 같은 부모를 갖는다고 보고, 그 SCC에 속한 노드들 중에서 가장 id값이 작은 것을 부모로 지정한다. id값은 DFS를 시작할 때 부여한다.

 

알고리즘

1.  인접 정점에 방문하며 자기 자신을 스택에 넣고, DFS를 재귀적으로 수행. 
2. 인접 정점에 방문하였으니 아직 처리중인 상태일 경우  더 작은 값으로 부모값을 갱신.
3. 부모 노드의 DFS가 끝난 경우에는, 자신의 id값이 스택에서 나올 때까지 스택에 있는 노드들을 pop하고 scc 배열에 추가함.
4. 그렇게 만들어진 하나의 scc를 전체 SCC 배열에 추가함.

 

 

궁금증

그렇다면 강한 연결 요소와 그래프의 사이클은 다른 개념일까?

 

SCC는 여러 사이클을 포함할 수 있으므로 사이클보다 더 넓은 개념임을 알 수 있었다.