위상정렬

위상정렬은 어떤 일이 선/후 관계가 정해져있을 때 이용가능한 알고리즘이다.

대표적으로 “선수과목”, “업무순서배치” 등에서 사용된다.

이 정렬은 DAG에서만 가능하다.

DAG : 사이클이 없는 방향 그래프

방식

  1. DFS 역순
  2. indegeree(진입차수)

DFS방식

방법

  1. DFS를 실행하면서 DFS가 끝나는 순서대로 Stack에 삽입한다.

  2. stack의 top을 차례대로 추출한다.



#include<cstdio>
#include <stdio.h>
#include<stack>
using namespace std;

vector<vector<int>> vt;
stack<int> st;
int n, m, x, y, visited[32001],finish[32001],cycle;


void dfs(int v) {
	visited[v] = true;
	for (auto i : vt[v]) {
		if (visited[i])
			continue;
		dfs(i);
	}
	st.push(v);
}
int main() {
	scanf_s("%d%d", &n, &m);
	vt.resize(n + 1);
	for (int i = 0; i < m; i++) {
		scanf_s("%d%d", &x, &y);
		vt[x].push_back(y);
	}
	for (int i = 1; i <= n; i++) {
		if (!visited[i])
			dfs(i);
	}
	while (st.size()) {
		printf("%d ", st.top());
		st.pop();
	}

```
return 0;
```

}

위상정렬은 DAG에서만 가능하므로 Cycle의 여부를 확인할 필요가 있다.

cycle 확인 방법

/*   cycle여부판단하는 코드 추가
void dfs(int here)
{
	visited[here] = true;
	for (auto there : vt[here])
	{
		if (!visited[there])
			dfs(there);
		else if (!finish[there]) //visit되어있는데 아직 끝나지 않은 정점을 dfs호출도중 보게 되면 역방향 간선
			cycle = 1;
	}
	finish[here] = true;
	st.push(here);
}
*/

Indegree방식

indegree란 한 정점에서 자신에게 들어오는 방향인 간선의 수

예시

1번 정점 : 0

2번 정점 : 1

3번 정점 : 0

4번 정점 : 3

방법

(큐가 빌때까지 반복)

  1. 모든 정점의 indegree의 개수를 세준 후 queue에 indegree가 0인 정점을 삽입
  2. 큐에서 노드를 추출(indegree가 0이면 정렬이 완료)
  3. 뽑은 노드와 연결된 노드의 진입차수들을 -1
  • 사용하는자료구조

    큐를 사용하지만 min heap을 사용하면 동시에 여러 원소가 있을 때 큐가 작은 원소를 먼저 내보낸다!


#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
int n, m, a, b, in[32001];
vector<vector<int>> vt;
priority_queue<int> pq;
int main() {
	scanf_s("%d%d", &n, &m);

	vt.resize(n + 1);
	for (int i = 0; i < m; i++) {
		scanf_s("%d%d", &a, &b);
		vt[a].push_back(b);
		in[b]++;
	}
	for (int i = 1; i <= n; i++)
	{
		if (in[i] == 0)
			pq.push(-i);
	}
	while (pq.size())
	{
		int tp = -pq.top();
		printf("%d\n", tp);
		pq.pop();
		for (int there : vt[tp])
		{
			in[there]--;
			if (in[there] == 0)
				pq.push(-there);	
		}
		n--; //cycle판단
	}
	if (n > 0)
		printf("cycle");
	return 0;
}

cycle 확인방법

정점의 횟수 만큼 반복문을 돌리다가 큐의 크기가 먼저 0이 된다면 cycle이 존재한다는것을 알 수 있다.

(사이클에 속하는 정점들이 존재하면 그 정점들은 모두 indegree가 1이상이라 큐에 들어가지 않기 때문!)

참고 : https://jason9319.tistory.com/93