[알고리즘] 위상 정렬 (Topology Sort)

[개념]

 

위상 정렬이란 ? 

 

위상 정렬(Topology Sort) 알고리즘이란 순서가 정해진 작업을 차례대로 수행해야 할 때, 순서를 결정하기 위해 사용하는 알고리즘이다.

 

 

하나의 노드에 들어오기 위해 필요한 노드의 개수를 '진입차수'라고 한다.

위의 예제에서 보면 2번 노드의 진입차수는 13,7에 의해 2가 된다.

 

위상 정렬은 방향 그래프에서 진입차수가 0인 노드가 하나 존재해야 된다. 그리고 해당 노드가 위상 정렬의 시작 노드가 된다.

위상 정렬은 진입차수가 0인 노드를 시작으로 순서대로 queue에 넣어준다. 

 

하나의 방향 그래프에서 여러 가지의 위상 정렬이 가능하다.

 

1. 진입차수가 0인 노드를 큐에 넣는다.

2. 큐에서 꺼내고 해당 노드에 부속된 간선 삭제

1,2번을 계속 반복해가면서 모든 노드가 선택되면 종료된다.

 

첫번째로 진입 차수가 0인 노드 5,7을 큐에 넣는다.

 

 

큐에서 노드를 꺼내고 해당 노드와 연결된 간선을 삭제해준 뒤 큐에 넣는다.

 

 

마찬가지로 큐에서 노드를 꺼내고 해당 노드의 간선을 삭제해준 뒤 연결된 노드를 큐에 넣어준다.

 

 

위와 같은 방법으로 계속해서 반복한다.

 

 

 

 

더이상 큐에 넣을 노드가 없으므로 위상 정렬이 끝나고 아래와 같이 순서가 정렬된 것을 확인할 수 있다.

 

[코드]

 

백준에서 위상 정렬 관려 코드로

아래와 같이 위상 정렬을 구현할 수 있다.

(www.acmicpc.net/problem/2252)

 

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

#define MAX 32001

using namespace std;

int N,M;
int Degree[MAX]={0,};

vector <int> v[MAX];


int main(void)
{
    queue <int> q;
    
    scanf("%d %d",&N,&M);
    for(int i=0;i<M;i++)
    {
        int x1,x2;
        scanf("%d %d",&x1,&x2);
        
        Degree[x2]++;
        v[x1].push_back(x2);
    }
    
    for(int i=1;i<=N;i++)    if(Degree[i]==0)    q.push(i);
    
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        
        printf("%d ",x);
        
        for(int i=0;i<v[x].size();i++){
            int tmp = v[x][i];
            Degree[tmp]--;
            if(Degree[tmp]==0)  q.push(tmp);
        }
    }
    return 0;
}