위상정렬

1. 개념

---

방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬을 말한다.

• 예를 들어, 교과 이수 제도가 있다.
• 특정 과목을 듣기 위해서 선수과목이 있는 그런 형태를 말한다.

주의할 점

• 같은 그래프에서 여러 가지의 위상 정렬이 있을 수는 있다.
• 단, 그래프의 순환이 있는 경우는 위상정렬이 될 수 없다. 
• 위상 정렬은 사이클이 없는 방향 그래프(DAG) 에서만 정의된다.

 

 

2. 구현

---

참고

• indegree : 자신에게 들어오는 간선의 수

동작 방식

• 모든 간선을 순환하여 indegree 테이블 채우기
• indegree가 0인 정점들을 queue에 넣기
• queue에서 pop을 통해 위상 정렬 결과에 추가
• 해당 정점으로부터 연결된 모든 정점의 indegree값을 1감소, 만약 이 때 indegree가 0이라면 정점을 queue에 추가
• queue가 빌 때 까지 반복

그림

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<int> adj[10];
int indegree[10];
int n;

int main()
{
	queue<int> q;
	vector<int> result;

	for (int i = 1; i <= n; ++i)
	{
		if (indegree[i] == 0)
			q.push(i);
	}
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		result.push_back(cur);
		
		for (int nxt : adj[cur])
		{
			indegree[nxt]--;
			if (indegree[nxt] == 0)
				q.push(nxt);
		}
	}
	if (result.size() != n)
		cout << "cycle";
	else
	{
		for (const auto& r : result)
		{
			cout << r << " ";
		}
	}
}

 

 

3. 문제

---

boj 2252 : 기본 위상정렬

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int n, m;
vector<int> adj[32'002];
int deg[32'002];
vector<int> answer;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;


	while (m--)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b); //a가 b앞
		deg[b]++; //b는 a가 필요해
	}
	queue<int>q;
	for (int i = 1; i <= n; ++i)
	{
		if (deg[i] == 0)
			q.push(i);
	}

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		answer.push_back(cur);

		for (int nxt : adj[cur])
		{
			deg[nxt]--;
			if (deg[nxt] == 0)
				q.push(nxt);
		}
	}

	for (const auto& a : answer)
	{
		cout << a << " ";
	}
}

boj 1005 : 위상정렬 + DP

#include <iostream>
#include <queue>
#include <vector>
#include <set>
using namespace std;

int t, n, k, w;
vector<int> adj[1002];
int deg[1002];
int D[1002];
int dp[1002];
set<int> ans;
int answer = 0;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> t;

	while (t--)
	{
		for (int i = 0; i < 1002; ++i)
			adj[i].clear();
		fill(D, D + 1002, 0);
		fill(deg, deg + 1002, 0);
		fill(dp, dp + 1002, 0);
		answer = 0;

		cin >> n >> k;
		
		for (int i = 1; i <= n; ++i)
		{
			cin >> D[i];
		}

		for (int i = 0; i < k; ++i)
		{
			int x, y;
			cin >> x >> y;
			adj[x].push_back(y);
			deg[y]++;
		}
		cin >> w;

		queue<int> q;

		for (int i = 1; i <= n; ++i)
		{
			if (deg[i] == 0)
			{
				q.push(i);
				dp[i] = D[i];
			}
		}

		while (!q.empty())
		{
			int cur = q.front();
			q.pop();

			for (int nxt : adj[cur])
			{
				dp[nxt] = max(dp[nxt], dp[cur] + D[nxt]);
				deg[nxt]--;
				if (deg[nxt] == 0)
					q.push(nxt);
			}
		}

		cout << dp[w] << "\n";
	}
}

 

---

참고)

https://blog.encrypted.gg/1020

[실전 알고리즘] 0x1A강 - 위상 정렬