위상 정렬(Topological Sort) - Kahn’s Algorithm

Kahn’s Algorithm이란?

Kahn's algorithm은 위상 정렬(Topological Sorting)을 수행하는 대표적인 방법 중 하나로, 진입 차수(In-degree) 를 활용하여 방향 비순환 그래프(DAG, Directed Acyclic Graph)의 위상 정렬을 구하는 방식입니다.

작동 방식

1. 모든 정점의 진입 차수(in-degree)를 계산
   • 진입 차수(in-degree): 해당 정점으로 들어오는 간선의 개수
2. 진입 차수(in-degree)가 0인 정점을 큐에 삽입
3. 큐에서 정점을 하나씩 꺼내면서 연결된 간선 제거
   • 연결된 정점들의 진입 차수를 감소시키고,
   • 감소 후 진입 차수가 0이 되면 큐에 삽입
4. 모든 정점을 방문할 때까지 반복

✅ 시간 복잡도: $O(V + E)$ → 모든 간선과 정점을 한 번씩 처리

진행 과정

in-degree가 0인 정점을 찾아서 queue에 넣는다.

queue의 front가 1이니까 1을 빼고 1과 연결된 간선을 제거한다.

따라서 1과 연결되어있던 9의 indegree가 1 감소해서 2가 된다. 이를 2와 8도 빼면서 진행한다.

8의 간선(8→9)와 (8→6)을 제거하면 9와 6의 indegree가 0이 된다. 따라서 9와 6을 queue에 넣는다.

queue의 front를 빼면 9이고 9와 연결된 간선은 없으니 그냥 넘어가고 다음은 6을 뺀다.

6과 연결된 간선을 제거하고 나면

7의 indegree가 0이 되고 queue에 넣게된다.

queue에서 7을 빼서 7과 연결된 간선을 제거하고 나면

indegree가 0이 된 5를 queue에 넣고

queue의 front인 5를 빼서 5와 연결된 간선들을 지워주자.

최종적으로 3과 4까지 queue에 들어가고 제거되게 된다.

위상정렬의 값은 queue에 들어간 순서가 된다. 따라서 1 → 2 → 8 → 9 → 6 → 7 → 5 → 3 → 4가 된다.

Code

#include <iostream>
#include <queue>

using namespace std;

vector<int> adj[1001];
int indegree[1001];

// V: 정점의 개수, E: 간선의 개수
int V, E;

int main()
{
	cin >> V >> E;

	// u -> v 의 형태로 간선이 주어진다.
	// v보다 u가 먼저 수행되어야 한다는 의미
	int u, v;
	for (int i = 0; i < E; i++)
	{
		cin >> u >> v;

		// u를 수행하고 v로 가야하기 때문에 u에서 v로 가는 간선 추가
		adj[u].push_back(v);

		// v로 들어오는 간선이 늘어나기 때문에 in-degree를 1 증가시켜 준다.
		indegree[v]++;
	}

	queue<int> q;
	for (int i = 1; i <= V; i++)
	{
		// in-degree가 0인 정점을 queue에 넣는다.
		if (indegree[i] == 0)
			q.push(i);
	}
	int cur;
	while (!q.empty())
	{
		cur = q.front();
		cout << cur << " ";
		q.pop();
		for (int nxt : adj[cur])
		{
			// cur과 연결된 간선을 제거하면 해당 간선으로 연결된 nxt의 in-degree가 1 감소한다.
			// 이때 감소시킨 정점 nxt의 in-degree가 0이되면 queue에 넣어준다.
			if (--indegree[nxt] == 0)
				q.push(nxt);
		}
	}

	return 0;
}

// 위의 예시 실행 결과
9 9
1 9
2 9
8 9
8 6
6 5
6 7
7 5
5 3
5 4
1 2 8 9 6 7 5 3 4