알고리즘/실전알고리즘강좌(동빈나)
위상정렬(Topology Sort)
밀루루
2022. 3. 13. 20:13
위상 정렬
위상 정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 정해주는 알고리즘이다. 이때, 위상 정렬은 DAG(Directed Acyclic Graph/사이클이 발생하지 않는 방향 그래프)에만 적용 가능하다. DAG에 대한 예를 들어보면 아래 그림과 같다.
위상 정렬을 수행하는 알고리즘에는 스택을 이용한 방식과 큐를 이용한 방식이 있는데, 큐를 이용하는 방법에 대해 알아보자.
1. 진입차수가 0인 정점을 큐에 삽입한다
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다(기존진입차수-1)
3. 간선 제거 후에 진입차수가 0이 된 정점을 큐에 삽입한다
4. 큐가 빌 때까지 2~3을 반복한다 (이때, 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다)
그럼 이해를 위해 그림으로 살펴보면 아래와 같다.
이를 코드로 작성해보면 아래와 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#include <iostream>
#include <vector>
#include <queue>
#define MAX 10
using namespace std;
int n, inDegree[MAX];
vector<int> a[MAX];
void topologySort() {
int result[MAX];
queue < int> q;
// 진입차수가 0인 노드를 큐에 삽입
for (int i = 1; i <= n;i++)
if (inDegree[i] == 0)
q.push(i);
// 위상 정렬이 완전히 수행되려면 정확히 n개의 노드를 방문
for (int i = 1;i <= n;i++) {
//n개를 방문하기 전에 큐가 빈다면 사이클이 있는 거임
if (q.empty()) {
printf("사이클이 발생했습니다.");
return;
}
int x = q.front();
q.pop();
result[i] = x;
for (int i = 0; i < a[x].size();i++) {
int y = a[x][i];
//새롭게 진입차수가 0이 된 정점을 큐에 삽입
if (--inDegree[y] == 0) {
q.push(y);
}
}
}
for (int i = 1; i <= n; i++)
printf("%d ", result[i]);
}
int main() {
n = 7;
a[1].push_back(2);
inDegree[2]++;
a[1].push_back(5);
inDegree[5]++;
a[2].push_back(3);
inDegree[3]++;
a[3].push_back(4);
inDegree[4]++;
a[4].push_back(6);
inDegree[6]++;
a[5].push_back(6);
inDegree[6]++;
a[6].push_back(7);
inDegree[7]++;
topologySort();
}
|
cs |