위상정렬이란? |
Topology Sort
순서가 정해져 있는 작업을 차례대로 수행해야 할 때 그 순서를 정렬하기 위해 사용
순서만 맞으면 되기때문에 정답이 두 개 이상일 수 있다.
Queue를 사용해서 구현한다.
위상정렬이 가능하려면 DAG여야 한다.
DAG : Directed Acyclic Graph, 즉 비순환 단방향 그래프이다.
사이클이 있다면 위상정렬을 사용할 수 없다.
시간복잡도 O(V + E)
구현방법 |
정점으로 들어오는 간선의 갯수(진입차수)를 카운트해준다.
int start, end;
cin >> start >> end;
inDegree[end]++;그 후 진입차수가 0인 정점들을 Queue에 넣는다.
위상정렬을 진행할때 Queue에서 하나씩 꺼내서 해당 정점들을 방문한다.
방문하고 해당 정점에서 이어진 간선들을 끊어준다.
즉 인접한 정점들의 진입 차수를 1씩 깎는다.
진입차수가 0이 되었다면 Queue에 넣는다.
반복하다가 모든 정점을 방문하기 전에 Queue가 빈다면 사이클이 존재한다는 뜻이다.
모든 정점을 방문했다면 Queue에서 꺼낸 순서가 위상정렬의 결과이다.
자세한 설명 |
위와 같은 상태에서 시작한다.
진입차수가 0인 노드는 0번노드밖에 없으므로 queue에 0번노드를 삽입한다.
그 후 0번노드에서 인접한 노드들과의 연결을 끊는다.
구현상으로는 인접한 노드들의 진입차수를 -1한다.
그러고 나서 인접한 노드들의 진입차수가 0이 되었다면 해당 노드들도 queue에 넣는다.
위 과정을 거치면 이 사진과 같아진다.
그럼 이번엔 queue에서 1번을 꺼내고 1번노드에 방문해서 인접노드들의 진입차수를 -1한다.
그럼 2번노드도 진입차수가 0이되니 queue에 2번을 넣는다.
그 다음은 4번차례이다.
4번노드를 방문해서 인접한 노드인 5번의 진입차수를 -1한다.
근데 이번엔 5의 진입차수가 0이 되지 않았으므로 5를 queue에 넣지 않는다.
이 과정을 계속 반복하면 결국 최종적으로 아래와 같은 모습이 된다.
모든 노드를 방문했으니 사이클이 없음이 증명되었고, 위상정렬의 결과는 0 -> 1 -> 4 -> 2 -> 3 -> 5 -> 6이 되었다.
물론 1보다 4를 먼저 방문해도 위상정렬임은 마찬가지이다. 정답이 여러가지일수 있다.
예시코드 |
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL);
int N, M;
cin >> N >> M;
vector<vector<int>> graph(N + 1); // 노드를 1번부터 쓰므로 N + 1
vector<int> inDegree(N + 1, 0);
int u, v;
for (int i = 0; i < M; i++) {
cin >> u >> v;
graph[u].push_back(v);
inDegree[v]++;
}
queue<int> q;
for (int i = 1; i <= N; i++) {
if (inDegree[i] == 0) q.push(i);
}
for (int i = 0; i < N; i++) { // 1번부터 N번노드까지 N회반복
if (q.empty()) {
cout << "cycle 발생\n";
return;
}
int node = q.front();
q.pop();
cout << node << ' ';
for (int adj : graph[node]) {
inDegree[adj]--;
if (inDegree[adj] == 0) q.push(adj);
}
}
return 0;
}
※ 참고 문헌