[알고리즘] 위상 정렬(Topological Sort) - 코딩밥상

위상 정렬(Topological Sort)이란?

'위상'이란 '어떤 정점이 다른 정점과의 관계 속에서 가지는 위치'라는 의미입니다. 이는 그래프 내 서로 인접한 정점 사이의 관계에 '위치'라는 속성이 존재한다는 뜻입니다. 이 위치는 간선 방향에 의해 결정됩니다. 간선을 뻗어내는 정점이 앞이 되고, 간선을 받는 정점이 뒤가 됩니다. 이 앞/뒤 또는 위/아래 관계를 차근차근 정렬하는 작업이 바로 위상 정렬입니다.

 

그런데 모든 그래프에 대해 위상 정렬을 할 수 있는 것은 아닙니다. 위상 정렬을 하기 위해선 몇가지 조건이 있습니다. 

첫째로 그래프에 방향성이 있어야 하고, 둘째로 그래프 내에 사이클이 없어야 합니다. 이러한 조건을 만족하는 그래프를 DAG(Directed Acyclic Graph)라고 합니다. 

 

정점으로 들어가는 간선을 진입 간선(Incoming Edge), 정점에서 나가는 간선을 진출 간선(Outgoing Edge)라고 할 때,

위상 정렬의 동작 방식을 정리하면,

1. 진입 간선이 없는 정점을 리스트에 추가하고 해당 정점 자신과 진출 간선을 제거합니다.
2. 모든 정점에 대해 전 단계 수행을 반복하고 그래프 내에 정점이 남아 있지 않으면 정렬을 종료합니다.
3. 종료 후 리스트에 위상 정렬된 그래프가 저장됩니다.

 

다음 과정을 통해 위상 정렬을 완벽하게 수행할 수 있지만, 앞서 배운 깊이 우선 탐색을 이용하여 위상 정렬을 할 수도 있습니다.

우선 진입 간선이 없는 정점을 시작점으로 깊이 우선 탐색을 통해 가장 깊이 탐색하고 만약 해당 노드가 더 이상 방문할 노드가 없다면 리스트의 헤드로 삽입합니다. 이 과정을 돌아 오는 노드마다 각각 수행합니다. 

정리하자면,

1. 진입 간선이 없는 정점에 대해 깊이 우선 탐색을 시행하고, 탐색 중에 더 이상 옮겨갈 수 있는 인접 정점이 없는 정점을 만나면 해당 정점을 리스트의 새로운 헤드로 삽압합니다.
2. 전 단계를 반복하다가 더 이상 방문할 정점이 없으면 깊이 우선 탐색을 종료합니다.
3. 종료 후 리스트에 위상 정렬된 그래프가 저장됩니다.

---

코드 구현

void TopologicalSort(Vertex* V, Node** List){
    while(V != NULL && V->Visited == NotVisited){
        TS_DFS(V,List);
        
        V = V->Next;
    }
}

void TS_DFS(Vertex* V, Node** List){
    Node* NewHead = NULL;
    Edge* E = NULL;
    
    V->Visited = Visited;
    
    E = V->AdjacencyList;
    
    while(E != NULL){	//DFS로 끝단까지 탐색
        if(E->Target != NULL && E->Target->Visited == NotVisited) TS_DFS(E->Target,List);
        
        E = E->Next;
    }
    
    cout<<V->Data<<' ';
    
    NewHead = SLL_CreateNode(V);	//노드가 진출 간선이 없다면, 즉 더 이상 이동할 노드가 없다면 리스트의 헤드로 추가
    SLL_InsertNewHead(List, NewHead);
}