Topology sort (위상 정렬)

위상 정렬

    - 순서가 있는 일을 순서대로 나열하는 정렬

 

    - 의미 변환

        * 그래프 이론에서, 순서 : 방향 그래프

        * 그래프 이론에서, 일 : 노드

        * 그래프 이론에서, 순서대로 나열 : 간선의 방향을 거스르지 않게 노드 나열

 

    - 예시

        * 대학교 강의에서 선행 과목을 고려해서 강의를 수강

        * 스타크래프트 게임에서 높은 테크 건물을 짓기 위해서는 하위 테크 건물을 먼저 건설

 

https://www.techiedelight.com/topological-sorting-dag/

 

동작

    - 진입 차수가 0인 정점들을 선택하여 스택/큐에 삽입

    - 스택/큐에서 정점을 하나 꺼내어 꺼낸 정점과 연결된 간선 제거(간선 수 감소)

    - 꺼낸 정점은 차례대로 나열

    - 위 과정 반복

    - 모든 정점이 선택/삭제되면 종료 

 

    - 예시 : 영상 ( 1:30부터 )

 

    - 예시 : 전체 과정

 

 

구현

#include <vector>
#include <queue>
#include <iostreram>
 
using namespace std;
 
int n = 6;
int inDegree[10]; // 진입 차수 기록  
int result[7]
 
vector<int> g[10]; // 인접 리스트로 그래프 구현  
 
 
void topologySort(){
    
    queue<int> q;
    
    // 초기에 진입 차수 0인 노드를 큐에 삽입  
    for(int i=1; i<=n; i++)
        if(inDegree[i] == 0)
            q.push(i);
            
    for(int i=1; i<=n; i++){
        
        // n개의 정점을 모두 나열하기 전에
        // 큐가 비어버리면, 진입 차수 = 0인 노드가 없다는 뜻
        // 즉, 사이클이다. 
        if(q.empty()) return;
        
        // queue에서 정점 꺼내기  
        int node = q.front();
        result[i] = node;
        q.pop();
        
        // 꺼낸 정점과 연결된 간선 찾아서 제거  
        for(int j=0; j<g[node].size(); j++){
            int next_node = g[node][j];
            
            // 간선이 제거된 다음 노드의 진입 차수가 0이면, 큐에 삽입  
            if(--inDegree[next_node] == 0)
                q.push(next_node);
        }
        
    }
    
}
 
 
int main(void){
    
    g[1].push_back(6);
    inDegree[6]++;
    
    g[2].push_back(1);
    inDegree[1]++;
    
    g[4].push_back(2);
    inDegree[2]++;
    g[4].push_back(3);
    inDegree[3]++;
    
    g[5].push_back(3);
    inDegree[3]++;
    g[5].push_back(6);
    inDegree[6]++;
    
    topologySort();
    
}

 

 

 

특징

    - 하나의 방향 그래프에서 여러 위상 정렬 가능

    - DAG(Directed Acyclic Graph)에서 만 가능

        * 사이클이 발생할 경우, 잔여 정점은 있지만 진입 차수가 0이 되어 선택할 수 없음

    - 시간 복잡도 : O(V + E)

 

 

 

참조

    - 블로그 1

    - 블로그 2

    - 유튜브

    - 위키피디아