위상 정렬 Topological Sort

위상 정렬

위상을 기준으로 정렬하는 알고리즘  (위상 : incoming edge)

일의 순서를 정할 필요가 있을때 많이 쓰인다.

 

 

 

위상 정렬 알고리즘 특징 

1. DAG(direct acycle graph)에서 가능한 정렬 방법이다.
2. 사이클이 발생하는 경우 위상 정렬 수행 할 수 없다.
3. 의존성이 없는 노드부터 하나씩 차례대로 처리하여 의존성 높은 순으로 처리한다. 

 

* 시간 복잡도 O(V+E)

 

위상 정렬 알고리즘 순서

1. 각 vertex의 위상(incoming edge수)를 저장한다.
2. 위상이 0인 노드들에 대해 모두 queue에 넣는다.
3. queue에서 node를 꺼내 위상 정렬에 넣어준다.
4. 위상 정보를 하나 낮추고 엣지를 없앤다.
5. 위상이 0이 된 노드들을 큐에 저장한다.
6. 반복

 

---

 

알고리즘 예시

위상 그래프가 이렇게 되어 있고 각 노드의 위상 정보가 표와 같이 되어있다고 보자!!

 

우선 위상이 0인 노드들을 queue에 모두 넣는다.

 

1) 

위상이 0인 노드가 1뿐이므로 queue에 1을 넣고

 

2)

sort로 옮겨준다

 

3)

1이 가지고 있는 노드의 위상을 하나씩 낮춘다. 

    1. 먼저 2의 위상을 하나 낮춰준 뒤 위상이 0이 되었을 때 queue에 push 해준다.

    2. 다음 1이 가진 노드 4의 위상을 하나 낮춰주고 위상이 0일 시 queue에 push 해준다.

 

4)

다음 queue에서 2를 sort에 넣는다.

2가 가진 위상 노드 5의 위상을 하나 낮추고 0이 되었다면 

 

 

5) 

queue에 다음 노드 5를 넣어준다.

 

6) 

다음 queue에 있는 4를 sort에 넣어준다.

 

4가 가진 노드 3의 위상을 하나 낮춘다. 이번에는 3의 위상이 1이 되어 아직 queue에 들어갈 수 없다.

 

 

7)

queue에 있던 5를 sort에 넣는다.

5가 가진 노드 3의 위상을 하나 감소 시킨 뒤 3의 위상이 0이 되었으므로 

 

8) 

queue에 넣어준다.

 

9) queue에 있던 3을 sort에 넣어준다. 

더이상 queue에 노드가 없으므로 종료한다. 끝이다 !! 

 

 

이를 코드로 나타내면 아래와 같다. 

 

백준의 줄세우기 문제가 위상정렬의 대표적인 문제라고 할 수 있다. 풀어보는것을 추천한다!!

 

 

---

c++ 코드 :

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

using namespace std;

int* in;
queue<int> q;

int main(){
    int N, M, v1, v2;
    scanf("%d %d", &N, &M);
    vector<vector<int> > v;
    for(int i = 0; i < N + 1; i++)v.push_back(vector<int>());
    in = new int[N+1];
    for(int i = 0; i < N + 1; i++)in[i] = 0;
    for(int i = 0 ; i < M; i++){
        scanf("%d %d", &v1, &v2);
        v[v1].push_back(v2);
        in[v2] ++;
    }
    for(int i = 1; i <N+1; i++){
        if(in[i] == 0) q.push(i);
    }

    while(!q.empty()){
        int temp = q.front();
        printf("%d ", temp);
        q.pop();
        for(int i = 0; i < v[temp].size(); i++){
            if(--in[v[temp][i]] == 0)q.push(v[temp][i]);
        }
    }    
}

 

 

참고 블로그 :

https://zoomkoding.github.io/algorithm/2019/07/02/Topological-Sort-1.html