개념

참고블로그

26. 강한 결합 요소(Strongly Connected Component)

**강한 결합 요소(Strongly Connected Component : SCC)**란 그래프 안에서 '강하게 결합된 정접 집합'을 의미한다. 같은 SCC에 속하는 두 정점은 서로 도달 가능하다.

따라서 사이클이 발생하는 경우 SCC에 해당된다. SCC는 Directed Graph일 때만 고려한다. 무향 그래프일떄는 그래프의 전체가 SCC이기 때문에 따로 고려하지 않는다.

SCC를 추출하는 알고리즘에는 대표적으로 2가지가 있다.

• 코사라주 알고리즘(Kosaraju's Algorithm)
• 타잔 알고리즘(Tarjan's Algorithm)

이 페이지에서는 타잔 알고리즘에 대해 다룬다.

수행 과정

타잔 알고리즘은 모든 정점에 대해 DFS를 수행하며 SCC를 찾는다.

DFS는 함수 안에서 계산된 최소 parent를 return한다.

아래는 DFS함수의 수행과정이다.

1. 처음엔 현재노드를 부모노드라고 가정한다. 현재 노드를 Stack에 넣는다.
2. 현재 노드와 인접한 노드에 대하여..
   • DFS가 한번도 실행되지 않은 노드는 DFS를 실행한다. 그러면 그 인접노드의 인접노드를 계속 따라서 나온 최소 parent가 출력될 것이다. 그것을 현재 parent와 비교하여 최솟값으로 저장한다. 어떤 SCC가 있을 때 SCC를 구성하는 노드중 가장 index가 작은 값을 최소 parent로 두기 때문에 최소 parent를 구하는 것이다.
   • DFS가 한번 이상 방문한 노드이더라도 SCC로 묶이지 않은 노드가 있을 수 있다. 그 노드 역시 DFS실행하여 최소 parent를 리턴받은 다음 현재 parent와 비교하여 최솟값으로 저장한다. 이미 DFS로 방문한 노드를 또 방문할 수 있어야 하는 이유가 이것이다. DFS로 SCC의 최소 parent까지 찾아가야 한다.
3. 현재 노드에서 구할 수 있는 최소 parent가 결정되었다.

   • 만약 현재노드가 최소 parent일경우 SCC가 있다는 뜻이다!

     그 SCC를 구성하는 노드들은 Stack에 있다. Stack에서 현재노드가 나올 때 까지 노드를 하나씩 뽑는다. 뽑힌 노드들은 Finished로 지정해준다. 이 노드들은 이미 어떤 SCC로 묶였있다는 뜻이다. 따라서 나중에 DFS로 방문하지 않는다. 이로서 SCC가 하나 생성되었다!

   • 만약 현재 노드가 최소노드가 아니라면 현재 노드의 DFS를 호출한 노드에게 최소 parent정보를 반환해야한다. 최소 parent를 리턴하고 함수를 종료한다.

위의 DFS를 모든 정점에 대해 실행한다. 단, visit된 노드는 이미 SCC처리가 된 상태이므로 방문하지 않는다.

C++