위상 정렬

위상 정렬

---

개념

선행 조건이 있는 작업을 차례로 수행해야 할 때, 이를 결정하기 위해 사용하는 알고리즘. 사이클이 존재하지 않는 방향 그래프, DAG_(Directed Acyclic Graph)_에만 적용 가능하다.

1. 진입 차수가 0인 정점을 큐에 삽입
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거
3. 수행 후 진입 차수가 0이 된 정점을 큐에 삽입
4. 큐가 빌 때까지 2~3을 반복. 이 떄 모든 원소를 방문하기 전 큐가 빈다면 사이클이 존재하는 것이다.

시간 복잡도 O(V + E)

구현

#include<iostream>
#include<vector>
#include<queue>
#define MAX 10

using namespace std;

int n, inDegree[MAX];
vector<int> a[MAX];

void topologySort() {
	int res[MAX];
    queue<int> q;
    
    for(int i=1; i<=n; i++) {
		if(inDegree[i] == 0)
        	q.push(i);
    }
    
    for(int i=1; i<=n; i++) {
    	if(q.empty()) {
			return;		// 사이클이 존재
        }    

        int x = q.front();
        q.pop();
        res[i] = x;
    
        for(int i=0; i<a[x].size(); i++) {
            int y = a[x][i];
            inDegree[y]--;
            if(inDegree[y] == 0)
                q.push(y);
        }
    }
    
    for(int i=1; i<=n; i++) {
		cout << res[i] << " ";
    }
}

int main(void) {
	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();
}

참고: https://m.blog.naver.com/ndb796/221236874984