Topology Sort [c++]

 위상정렬(Topolgy sort)는 순서가 정해져있는 작업을 차례로 수행 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘이다. 위상 정렬은 DAG(Directed Acyclic Graph == 사이클이 발생하지 않는 방향 그래프)에서만 사용가능하다. 여기서는 큐(Queue)를 이용하여 구현할 것이다.

 

Ⅰ. 진입차수(화살표 받는 개수)가 0인 정점을 큐에 삽입한다.

Ⅱ. 큐에서 원소를 꺼내 연결된 모든 간선을 제거.

Ⅲ. 간선 제거 후 진입차수가 0이 된 정점을 큐에 삽입, 위 과정을 반복.

 

-> 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이다 (위상정렬 불가능) 

    모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다.

 

DAG의 예시

 

#include <iostream>
#include <vector>
#include <queue>

#define MAX 10

using namespace std;

int n, inDegree[MAX]; // n은 정점의 개수, inDegree는 진입차수
vector<int> a[MAX]; // DAG


void topologySort() {
int result[MAX]; // 결과를 저장할 배열
queue<int> q;
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) q.push(i); // 진입차수가 0인 노드를 큐에 삽입
}

for (int i = 1; i <= n; i++) {
if (q.empty()) { // 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하므로 조건 부합x
cout << "사이클이 존재합니다. Directed Acyclic Graph 가 아닙니다.";
return;
}
int x = q.front(); // 큐에서 원소를 꺼낸다.
q.pop();
result[i] = x; // 결과 저장

for (int i = 0; i < a[x].size(); i++) { // push_back은 0번 index 부터 삽입이라 0부터 해야됨
int y = a[x][i]; // x에 연결되어 있던 노드들 중 x의 간선 제거로 인해 진입차수가 0이 된 노드가 있다면
inDegree[y]--; // 간선제거로 인해 x에 연결되어 있던 노드의 진입차수를 1씩 낮춤
if (inDegree[y] == 0) q.push(y); // 큐에 넣는다
}

}

for (int i = 1; i <= n; i++) { // 결과 출력
cout << result[i] << ' ';
}
}

int main() {

n = 7;
a[1].push_back(2);
inDegree[2]++;
a[2].push_back(3);
inDegree[3]++;
a[3].push_back(4);
inDegree[4]++;
a[4].push_back(6);
inDegree[6]++;
a[1].push_back(5);
inDegree[5]++;
a[5].push_back(6);
inDegree[6]++;
a[6].push_back(7);
inDegree[7]++;

topologySort();

return 0;
}

// 시간 복잡도 O(V + E) (정점개수 + 간선개수)