[C++] 위상 정렬 (Topological Sort)

 

 

 

 

위상 정렬(Topological Sort)은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.

이때 그래프에 사이클이 존재하면 안되며 시간 복잡도는 O(V + E)이다.

 

위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다는 특징이 있다.

 

 

 

 

 

위상 정렬 자료구조

가장 먼저 위상 정렬을 위한 자료구조를 생성한다.

그래프를 나타내는 인접 리스트 자료구조를 사용한다.

 

 

 

 

이째, 위상 정렬을 위해선 진입 차수 배열이 하나 필요하다.

진입 차수 배열 초기값은 모두 0으로 설정한 뒤,

인접 리스트를 수행하면서 해당하는 노드의 값을 1씩 증가시킨다.

 

 

 

 

그리고 위상 정렬을 결과를 저장할 배열을 하나 선언한다.

또한 진입 차수가 0인 노드를 선택해야 하기 때문에,

위 노드들을 저장할 큐가 필요하다

 

 

따라서 필요한 자료구조는 다음과 같다.

• 인접 리스트: 그래프 표현
• 진입 차수 배열: 각 노드에 연결된 Edge 개수
• 위상 정렬 배열: 결과를 저장한 배열
• 큐: 진입 차수 0 노드를 저장할 큐

 

 

 

 

 

위상 정렬 원리

 

위상 정렬의 원리는 다음 순서를 거친다.

1. 진입 차수 배열에서 값이 0인 노드(N)를 선택한다.
2. N과 연결된 노드들의 진입 차수를 각각 1씩 감소시킨다.
3. 위상 정렬 배열에 N을 추가한다.
4. 정렬이 완료됐으면 종료하고 아니면 1번으로 돌아가 다시 수행한다.

 

 

 

 

 

 

 

 

위상 정렬 코드 (백준 2252번. 줄 세우기)

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
	ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);

	int N, M, i;
	cin >> N >> M;
	vector<vector<int>> graph(N + 1);
	vector<int> degree(N + 1, 0);
	vector<int> result;
	queue<int> q;

	for (i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		graph[a].emplace_back(b);
		degree[b]++;
	}

	for (i = 1; i <= N; i++)
	{
		if (degree[i] == 0)
			q.push(i);
	}

	while (!q.empty())
	{
		int now = q.front();
		q.pop();
		result.emplace_back(now);

		for (auto node : graph[now])
		{
			degree[node]--;
			if (degree[node] == 0)
				q.push(node);
		}
	}

	for (auto node : result)
		cout << node << ' ';

	return 0;
}