강한 결합 요소란?
SCC라고도 부르며, 그래프 안에서 강하게 결합된 정점 집합을 뜻한다.
같은 SCC에 속하는 두 정점은 서로 도달이 가능하다.
싸이클이 발생하는 경우 SCC이다. 즉, 방향 그래프일 때만 의미가 있다. 무향 그래프인 경우 그래프 전체가 SCC이기 때문에 의미가 없다.
SCC를 추출하는 알고리즘은 2가지가 있다.
- 코사라주 알고리즘: 구현이 쉬움
- 타잔 알고리즘: 적용이 쉬움
타잔 알고리즘
모든 정점에 대해서 DFS를 수행해서 SCC를 찾는다.
부모에서 출발하여, 자식을 거친 후 다시 부모로 돌아올 수 있는 경로가 있어야 SCC가 성립된다.
부모에서 자식으로 나아가는 알고리즘으로 DFS 알고리즘이 적용된다.
-
부모 값을 자기자신으로 표시하고, 시작점을 스택에 넣는다.
-
자식(인접노드)으로 나아가, 부모 값을 자기자신으로 표기한 후 스택에 넣는다.
-
2번을 반복하다가, DFS가 끝나지 않았는데, 스택에 있는 값이 인접노드인 경우, 자신의 부모값을 해당 인접노드의 값으로 바꿔준다.
-
거꾸로 가면서 부모값을 갱신하고, 스택에서 자기자신의 값을 꺼낼 때 까지 진행한다. 자기 자신 값을 만나면 그때까지 뽑아진 것들의 집합이 하나의 SCC집합이다.
구현
시간복잡도: O(V+E)
#include <iostream>
#include <vector>
#include <stack>
#define MAX 10001 // 가능한 총 노드 수
using namespace std;
int id; // 각 노드마다 고유한 번호를 할당하기 위함
int d[MAX]; // 각 노드의 방문 여부
bool finished[MAX]; // 특정 노드의 DFS가 끝났는지 확인
vector <int> a[MAX]; // 실질적으로 노드를 담는 배열
vector <vector <int> > SCC; // 한 그래프에서 여러개가 나올 수 있기 때문에 2차원 벡터
stack<int> s;
// DFS는 총 정점의 갯수만큼 실행
int dfs(int x) {
d[x] = ++id; // 노드마다 고유한 번호 할당(맨 처음에 부모로 설정되는 값)
s.push(x); // 스택에 자기자신 삽입
int parent = d[x]; // 자신의 부모 값
// 인접한 노드를 하나씩 확인
for(int i=0;i<a[x].size();i++) {
int y = a[x][i]; // 인접한 노드 가리킴
// 방문한 적이 없다면
if(d[y]==0) {
parent = min(parent, dfs(y)); // 해당 노드로 dfs하여 더 작은 값으로 부모
} else if(!finished[y]) { // 방문은 했지만, 아직 처리가 안된 노드(현재 DFS를 수행하고 있는 노드)
parent = min(parent, d[y]); // 처리되고 있는 값의 부모와 비교
}
}
// 부모 노드가 자기자신인 경우
if(parent==d[x]) {
vector <int> scc;
// 자기 자신이 나올 때 까지 스택에서 꺼냄
while(1) {
int t = s.top();
s.pop();
scc.push_back(t);
finished[t] = true;
if(t==x) break;
}
SCC.push_back(scc);
}
return parent; // 자신의 부모 값 반환
}
int main(void) {
int v = 11; // 노드 수
a[1].push_back(2);
a[2].push_back(3);
a[3].push_back(1);
a[4].push_back(2);
a[4].push_back(5);
a[5].push_back(7);
a[6].push_back(5);
a[7].push_back(6);
a[8].push_back(5);
a[8].push_back(9);
a[9].push_back(10);
a[10].push_back(11);
a[11].push_back(3);
a[11].push_back(8);
for(int i=1;i<=v;i++) {
if(d[i]==0) dfs(i);
}
printf("SCC의 갯수: %lu\n", SCC.size());
for(int i=0;i<SCC.size();i++) {
printf("%d번째 SCC: ", i+1);
for(int j=0;j<SCC[i].size();j++) {
printf("%d ", SCC[i][j]);
}
printf("\n");
}
return 0;
}
위상정렬과 함께 사용하는 알고리즘이다. 각 SCC그룹을 정점으로 삼아서 전체그룹을 구성했을 때, 싸이클이 발생하지 않는 방향그래프가 된다.
reference: https://www.youtube.com/watch?v=H_Cg3-rv7RU&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=28
