Topology Sort

Topolgy Sort(위상 정렬)는 유향그래프에서 정점들의 순서를 정할 때 사용하는 알고리즘이다. 유향그래프에서 진입차수를 기준으로 쉽게 구현할 수 있다.

 

1) 위상 정렬의 동작

위상정렬은 다음과 같이 동작한다.

1) 진입차수가 0인 노드 선택한다.
2) 1)의 노드와 연결된 모든 노드들의 진입차수를 1씩 뺀다.
3) 1)의 과정을 반복한다.

 

2) 위상 정렬의 구현

 진입 차수가 0인 노드들을 queue에 넣음으로써 구현한다. 

void topology(){
    queue<int> q;
    for(int i=1;i<=N;i++){
        if(inDegree[i]==0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int x = q.top();
        result.push_back(x);
        q.pop();
        for(int i=0;i<graph[x].size();i++){
            int nx = graph[x][i];
            inDegree[nx] --;
            if(inDegree[nx] == 0) q.push(nx);
        }
    }
}

 여기서 $inDegree$ 배열은 각 노드들의 진입차수를 저장하는 배열이고, result는 위상정렬 결과 노드들의 순서를 저장하는 벡터이다.