위상 정렬(Topological Sort)

위상 정렬(Topological Sort)

 

위상 정렬이란?

 

 - 정점의 순서가 주어졌을 때 역행하지 않고 정상적으로 정렬하는 방법.

 

 - 방향이 존재하는 간선들이 주어졌을 때 역행하지 않고 정렬 하는 방법.

 

 - 시간 복잡도 : O(V+E)

 

---

위상 정렬 방법

 

 - 0. indegree[i] : i번째 정점으로 들어오는 간선의 개수

      result : 위상 정렬의 결과 값

 

 - 1. 가장 먼저 올 수 있는 정점들을 먼저 선택하여 queue에 넣는다.

      위상 정렬에서 가장 먼저 올 수 있는 정점은 들어오는 간선이 없는 정점이다.

 

 - 2. queue에 있는 정점들을 탐색하면서 해당 정점들과 연결된 정점들의 indegree값을 하나씩 감소시킨 후

      위상 정렬 결과 값인 result에 넣어준다.

 

 - 3. queue에 값이 존재하면 1번으로 돌아가 반복하고, queue에 값이 없는 경우 탐색한 경우 종료한다.

 

 

 

1. 위상 정렬 초기 상태

 

2. indgree가 0인 1과 2를 queue에 넣는다.

 

 

3. queue의 가장 앞에 존재하는 1을 선택하여 result에 넣고, 1과 연결된 노드의 indgree들을 하나씩 줄인 후 0이 되는 노드의 값을 queue에 넣는다.

 

 

4. queue의 가장 앞에 존재하는 2를 선택하여 result에 넣고, 2과 연결된 노드의 indgree들을 하나씩 줄인 후 0이 되는 노드의 값을 queue에 넣는다.

 

 

5. queue의 가장 앞에 존재하는 3을 선택하여 result에 넣고, 3과 연결된 노드의 indgree들을 하나씩 줄인 후 0이 되는 노드의 값을 queue에 넣는다.

 

 

 

6. queue의 가장 앞에 존재하는 5를 선택하여 result에 넣고, 5와 연결된 노드의 indgree들을 하나씩 줄인 후 0이 되는 노드의 값을 queue에 넣는다.

 

7. queue의 가장 앞에 존재하는 6을 선택하여 result에 넣고, 6과 연결된 노드의 indgree들을 하나씩 줄인 후 0이 되는 노드의 값을 queue에 넣는다.

 

7. queue의 가장 앞에 존재하는 4를 선택하여 result에 넣고, 4와 연결된 노드의 indgree들을 하나씩 줄인 후 0이 되는 노드의 값을 queue에 넣는다.

 

7. queue의 가장 앞에 존재하는 7를 선택하여 result에 넣고, 7와 연결된 노드의 indgree들을 하나씩 줄인 후 0이 되는 노드의 값을 queue에 넣는다.

 

 

---

 

위상 정렬 코드

 

#include <bits/stdc++.h>

using namespace std;
int indegree[101];

// N은 노드의 개수
// v[i]의 값들은 i에서 갈 수 있는 노드를 표현한다.
// ex) v[1][0]의 값이 3이면 1->3으로 갈 수 있는 간선이 존재한다는 것이다.
vector<int> topological(int N, vector<vector<int>> v) {

	queue<int> q;

	vector<int> result;

	
	for (int i = 1; i <= N; i++) {
		for (int now : v[i]) {
			indegree[now]++;
		}
	}

	// 들어오는 간선의 개수가 0인 노드 탐색
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) {
			q.push(i);
		}
	}

	while (!q.empty()) {

		int nowNode = q.front();
		q.pop();

		result.push_back(nowNode);

		for (int nextNode : v[nowNode]) {
			indegree[nextNode]--;
			
			if (indegree[nextNode] == 0) {
				q.push(nextNode);
			}
		}

	}

	return result;

}


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

	int N = 7;
	vector<vector<int>> v(8);

	v[1].push_back(3);
	v[2].push_back(5);
	v[3].push_back(6);
	v[4].push_back(7);
	v[5].push_back(4);
	v[6].push_back(4);

	vector<int> result = topological(N, v);

	cout<<"위상 정렬 결과 : "
	for (auto n : result) {
		cout << n << " ";
	}
	cout << endl;


	return 0;
}

 

---

위상 정렬 문제

 

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

14567번: 선수과목 (Prerequisite)

 

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

2252번: 줄 세우기