[Algorithm/Graph] 강한 연결 요소와 코사라주 알고리즘(Kosaraju's algorithm)

강한 연결 요소

동영상 서비스 사이트에서 다양한 채널 구독자 간의 공통점에 대한 통계를 작성하여, 서로 연관이 있는 구독 정보 그룹으로 나누려고 한다. 이 때 방향 그래프에서 나타나는 공통적인 특징을 이용하여 이러한 복잡한 문제를 해결할 수 있다.

 

방향 그래프에서 에지는 명시적인 "방향" 정보를 가진다. 방향 그래프에서 에지는 한쪽 방향으로만 이동할 수 있기 때문에 그래프의 특정 정점에 도달할 수 있는지 여부는 탐색을 어느 정점에서 시작했는지에 따라 다르게 결정된다.

주어진 그래프를 여러 개의 구역으로 나누되 같은 구역 안의 정점끼리는 서로 이동 가능한 경로를 갖도록 나눌 경우, 각 구역은 해당 그래프의 강한 연결 요소를 나타낸다.

 

방향 그래프와 무방향 그래프에서 연결성

• 무방향 그래프에서 연결 요소(connected component)란 모든 정점이 서로 연결되어 있는 부분 그래프 중에서 최대 크기 부분 그래프 집합을 의미한다.
  • 즉, 하나의 구성 요소에 있는 두 정점은 상호 접근이 가능하다.
    • 모든 정점이 연결되어 있는 그래프라면 어느 정점에서 출발하든 모든 정점에 도달할 수 있으므로 이러한 그래프는 단일 연결 요소로 구성되어 있다고 할 수 있다.
    • 상대적으로 특정 정점에서 다른 정점으로 이동할 수 없는 경우 이러한 그래프는 연결이 끊어졌다고 할 수 있다.
  • 특정 연결 요소 안에 있는 정점에서 다른 연결 요소로는 이동할 수 없다.
  • 무방향 그래프의 연결 요소는 독립적으로 분리된 부분 그래프이며, 이들 부분 그래프의 정점과 에지는 다른 부분 그래프와 완전히 단절되어 있다.
• 이와 달리 "강한" 연결성은 방향 그래프에만 적용되는 특징으로써, 그래프 내에서 다른 부분 그래프와 완전히 단절되어 있을 필요가 없다.
  
  • 즉, 부분 그래프 사이에 경로가 존재할 수 있다. (A -> BCD집합 이동은 가능하지만, BCD집합 -> A 이동은 불가능할 수 있다)
• 네트워크 그래프의 강한 연결 요소는 다양한 채널 그룹 중에서 해당 채널 내부에 있는 모든 채널이 구독 '경로'를 따라가다 보면 모두 만날 수 있는 채널 그룹으로 정의할 수 있다. 
• 이러한 방식으로 방대한 양의 데이터를 분리하면 상호 연관된 그래프 집합을 다른 유사성이 없는 그래프 집합과 분리하는데 도움이 된다

코사라주 알고리즘

• 그래프에서 강한 연결 요소를 찾는 가장 쉽고 널리 사용되는 방법으로는 코사라주 알고리즘이 있다.
• 코사라주 알고리즘은 DFS를 두 번 수행하는 형태로 동작한다.
  • 처음에는 입력 그래프 자체에 DFS를 수행하고, 두 번째에는 입력 그래프를 전치하여 DFS를 수행한다.
  • (물론 BFS를 사용해도 된다)
  • 그래프의 전치는 원본 그래프에서 시작 정점과 목표 정점이 서로 뒤바뀐 형태로, 각각 에지 방향이 반대가 된다.

코사라주 알고리즘 흐름

1. 모든 정점 중에서 아직 방문한 적이 없는 정점에 대해 차례대로 DFS 순회를 수행한다.

• 각 정점에 대해 DFS를 수행할 때 먼저 해당 정점에 대해 방문 기록을 저장하고, 이후 정점과 인접한 정점 중에서 아직 방문하지 않은 정점을 재귀적으로 탐색한다. 
• 인접한 정점을 모두 탐색한 후에는 현재 정점을 스택에 추가한 후 DFS를 종료한다.

2. 1번과 같은 작업을 전치 그래프에 대해 수행한다

• 앞서 구축한 스택에서 정점을 하나씩 꺼내고, 이 정점을 아직 방문하지 않았다면 이 정점을 시작으로 DFS를 수행한다.
• 이 때 각각의 DFS에서 만나는 정점들이 강한 연결 요소를 구성한다.

 

코사라주 알고리즘 구현

FillStack 함수 : DFS를 수행한다

void FillStack(int node, vector<bool>& visited,
	vector<vector<int>>& adj, stack<int>& stack)
{
	visited[node] = true;

	for (auto next : adj[node])
	{
		if (!visited[next])
		{
			FillStack(next, visited, adj, stack);
		}
	}

	stack.push(node);
}

 

• node : 현재 정점 인덱스
• vector<bool>& visited : 기존에 방문한 정점을 기록한 벡터
• vector<vector<int>>& adj : 인접 리스트
• stack : 방문 순서에 따른 정점 인덱스를 기록

 

Transpose 함수 : 인접 리스트로 표현된 그래프를 인자로 받아 전치된 그래프를 반환한다

vector<vector<int>> Transpose(int V, vector<vector<int>> adj)
{
	vector<vector<int>> transpose(V);

	for (int i = 0; i < V; i++)
	{
		for (auto next : adj[i])
		{
			transpose[next].push_back(i);
		}
	}

	return transpose;
}

 

CollectConnectComponents() 함수 : 두 번째 DFS 함수

void CollectConnectedComponents(int node, vector<bool>& visited,
	vector<vector<int>>& adj, vector<int>& component)
{
	visited[node] = true;
	component.push_back(node);

	for (auto next : adj[node])
	{
		if (!visited[next])
		{
			CollectConnectedComponents(next, visited, adj, component);
		}
	}
}

 

• 스택 대신 component 정수 벡터 참조를 선언하여, 이 벡터에 각각의 강한 연결 요소에 속하는 정점 인덱스가 저장된다.

 

Kosaraju() 함수 : 전치 그래프에서의 순회 결과, 즉 강한 연결 요소를 저장한다

vector<vector<int>> Kosaraju(int V, vector<vector<int>> adj)
{
	vector<bool> visited(V, false);
	stack<int> stack;

	for (int i = 0; i < V; i++)
	{
		if (!visited[i])
		{
			FillStack(i, visited, adj, stack);
		}
	}

	vector<vector<int>> transpose = Transpose(V, adj);

	fill(visited.begin(), visited.end(), false);

	vector<vector<int>> connectedComponents;

	while (!stack.empty())
	{
		int node = stack.top();
		stack.pop();

		if (!visited[node])
		{
			vector<int> component;

			CollectConnectedComponents(node, visited, transpose, component);
			connectedComponents.push_back(component);
		}
	}

	return connectedComponents;
}

 

 

시간 복잡도

입력 그래프가 인접 리스트로 표현되어 있을 경우 O(V + E) 형태의 선형 점근적 시간 복잡도를 갖기 때문에 매우 효율적이다.