[알고리즘] 강한 연결 요소 Strongly Connected Component | 코사라주 알고리즘, 타잔 알고리즘

 

강한 결합 

방향 그래프의 모든 노드에서 다른 모든 노드로 가는 경로가 있는 경우, 이 그래프가 강하게 연결되어 있다고 한다.

[1,2,5], [3,4,8], [6,7]이 강하게 결합된 컴포넌트(이하 SCC)이다.
 
1에서 출발해 2, 5에 도달할 수 있고, 2에서 출발해도 1, 5에 도착할 수 있고, 5에서 출발해도 1, 2에 도달할 수 있다.
하지만 강결합되지 않은 1과 3을 보자. 1에서 출발하면 3에 도달할 수 있다. 하지만 3에서 출발하면 1에 갈 수 없다.
 
 

SCC를 찾는 알고리즘

SCC를 구하는 알고리즘은 크게 두 가지가 있다.
 

• 코사라주 알고리즘

강결합 컴포넌트를 찾는 유용한 방법이다.이 알고리즘에선 두 번의 DFS를 거친다. 첫 번째 탐색에서 그래프에 따라 노드 리스트를 만들고, 두 번째 탐색에서 강결합 컴포넌트를 찾는다. 

1. DFS를 처리하는 순서대로 노드 리스트를 만드는 단계이다. 노드의 처리가 끝나면 그 노드를 리스트에 추가한다.
 

[4,5,2,1,6,7,3] 라는 노드 리스트를 얻었다.
 
2. DFS를 하기 전 먼저 모든 간선의 방향을 뒤집는다.

그리고 첫 번째 탐색에서 만들어진 노드 리스트의 반대 순서대로 노드를 살펴본다. 모든 간선이 반대이기 때문에 컴포넌트에 속한 노드가 컴포넌트 바깥의 노드로 흐르지 않는다.(?)
 

2023.06.04 - [컴퓨터공학/Problem Solving] - [백준] 2150번: Strongly Connected Component (코사라주 알고리즘) | C++

[백준] 2150번: Strongly Connected Component (코사라주 알고리즘) | C++

 

 

• 타잔 알고리즘

코사라주 알고리즘보다 구현이 어렵지만 활용도가 높다. 무려 한 번의 DFS를 사용해 SCC를 구할 수 있다!
 
타잔 알고리즘은 방문한 노드를 스택에 넣어 관리한다. 이미 강결합이 형성된 노드거나, 이미 방문한 노드(스택에 존재)거나 간선이 없는 경우 pop하며 강결합 컴포넌트를 찾는 방법이다.
방문한 노드엔 방문 id를 부여하고, 
 
1. 임의의 노드에서 DFS를 수행하며 스택에 push한다.

 1번부터 탐색을 시작하여 4번까지 탐색을 진행한 상황이다.
 
 
2. 4번에서 더 이상 간선이 없으므로 스택에서 4번이 나올 때까지 pop한다.

 
5번도 마찬가지로 pop한다.

이제 2번으로 되돌아가 1번으로 향하는 간선을 살펴본다.

 
하지만 1번은 이미 탐색한 노드고, 강결합 컴포넌트에 해당되지 않는 노드이다. 2번은 자신의 id를 1번의 id로 변경하고 스택에서 id가 1인 노드가 나올 때까지 pop한다.
 
 

아직 방문하지 않은 노드가 있기 때문에! 3번부터 다시 탐색을 시작한다. 2번은 이미 SCC가 형성된 노드이므로 탐색하지 않는다.
 

 
6번까지 탐색 후 2번 때와 똑같은 방식으로 SCC를 찾자.
 

 

2023.06.04 - [컴퓨터공학/Problem Solving] - [백준] 2150번: Strongly Connected Component (타잔 알고리즘) | C++

[백준] 2150번: Strongly Connected Component (타잔 알고리즘) | C++

 

 

 

다음은

이렇게 타잔 알고리즘으로 SCC를 찾는 방법을 알아봤다. 다음은 SCC를 이용하여 SAT-2 논리 문제를 해결하는 방법을 알아보겠다. 아 SCC 구현 코드도 올리고!