[그래프 알고리즘]kosaraju 알고리즘(SCC)

Strongly Connected Component

SCC는 강한연결요소라고 합니다.

SCC는 방향그래프에서의 노드들의 부분집합으로, 한 SCC에 속하는 노드들끼리는 사이클이 존재합니다.

한 SCC에 속하는 임의의 두 노드 u, v에 대해 u에서 v로의 경로와, v에서 u로의 경로가 존재합니다.

모든 노드는 최소한 자기자신이 SCC에 속합니다.

stack으로 위상정렬

그래프를 DFS 하면서 현재 노드에서 연결된 모든 노드를 방문한 후 마지막에 현재 노드를 스택에 저장하면,

스택에는 그래프의 위상정렬의 역순으로 저장되어 있습니다.

역방향 그래프

원래 그래프의 모든 엣지의 방향을 반대로 한 그래프를 역방향 그래프라고 합니다.

원 그래프의 위상정렬의 역순으로 역방향 그래프를 방문하면 SCC의 원소들을 방문하게 됩니다.

구현

	#include <iostream>
	#include <vector>
	#include <stack>
	#include <algorithm>
	using namespace std;
	#define N_NODE 11
	#define INF 9999999
	// 그래프와 역방향 그래프
	vector<int> adjList[N_NODE], transList[N_NODE];
	void addEdge(int u, int v){
	adjList[u].push_back(v);
	transList[v].push_back(u);
	}
	// 스택
	stack<int> st;
	// 방문여부
	vector<bool> visited(N_NODE, false);
	// SCC 번호
	vector<int> sccId(N_NODE);
	// SCC 카운터
	int sccCnt = 0;
	// DFS 하면서 마지막에 stack에 추가한다.
	// stack에는 위상정렬의 역순으로 저장된다.
	void dfs(int here){
	visited[here] = true;
	for(int there : adjList[here]){
	if(!visited[there]) dfs(there);
	}
	st.push(here);
	}
	// 역방향 그래프를 방문하면서 SCC 번호를 부여한다.
	void setSCC(int here){
	sccId[here] = sccCnt;
	visited[here] = true;
	for(int there : transList[here]){
	if(!visited[there]) setSCC(there);
	}
	}
	void kosaraju(){
	// 스택 채우기
	fill(visited.begin(), visited.end(), false);
	for(int i=0;i<N_NODE;i++) if(!visited[i]) dfs(i);
	// 원 그래프의 위상정렬의 역순으로
	// 역방향 그래프를 방문하며 SCC 번호를 부여한다.
	fill(visited.begin(), visited.end(), false);
	while(!st.empty()) {
	int here = st.top();
	st.pop();
	if(!visited[here]){
	setSCC(here);
	sccCnt++;
	}
	}
	}
	int main(){
	// 그래프 생성
	addEdge(1, 0);
	addEdge(0, 2);
	addEdge(2, 1);
	addEdge(1, 4);
	addEdge(4, 7);
	addEdge(4, 5);
	addEdge(5, 8);
	addEdge(8, 4);
	addEdge(0, 3);
	addEdge(3, 6);
	addEdge(3, 9);
	addEdge(6, 9);
	addEdge(9, 10);
	addEdge(10, 6);
	addEdge(6, 7);
	kosaraju();
	for(int i=0;i<N_NODE;i++){
	cout << i << ", scc id : " << sccId[i] << "\n";
	}
	return 0;
	}

view raw kosaraju_scc_algorithm.cpp hosted with ❤ by GitHub