[알고리즘] 위상 정렬(Topological Sorting)

위상 정렬(Topological Sorting)이란?

출처: https://leetcode.com/discuss/general-discussion/1078072/introduction-to-topological-sort

 

위상 정렬(Topological Sorting)은 방향 그래프(Directed Graph)의 모든 정점을 간선의 방향을 거스르지 않도록 일렬로 정렬하는 방법이다. 방향성 있는 비순환 그래프(DAG, Directed Acyclic Graph)에서 사용할 수 있으며, 정렬 기준은 선행 정점이 후행 정점보다 먼저 나오는 순서를 따른다. 예를 들어, A 작업을 먼저 끝낸 후에 B 작업을 수행해야 하는 경우, A가 B보다 먼저 나오도록 정렬한다. 위상 정렬은 부분 순서들을 만족하는 전체 순서를 구하는 문제에서 활용되며, 문제 유형은 과목 수강 순서나 프로젝트 작업 순서 등이 있다.

 

동작방식

(아래 동작방식의 예는 BFS를 기반으로 설명한다. DFS로 구현하는 방법이 궁금하다면 여기를 참고하면 된다.)

예제로 사용할 그래프

 

1. 초기화

각 정점의 indegree를 저장하고 있는 배열을 생성한다. 또한, indegree가 0인 정점들을 저장할 큐를 생성하고 indegree가 0인 정점들을 저장한다.

 

 

2. 정점 선택

큐에서 indegree가 0인 정점을 추출한다. 해당 작업은 정점을 선택하는 단계로, indegree가 0인 정점들의 우선순위는 없으므로 큐 맨 앞에 있는 정점을 선택해도 무방하다.

 

 

3. 간선 제거

정점을 선택했다는 것은 "해당 정점이 먼저 나와야 한다"는 제약이 걸린 후행 정점들의 제약이 제거되었다는 의미를 가지므로, 선택한 정점의 outdegree 간선을 제거한다. 만약 간선을 지워서 indegree가 0이 된 후행 정점이 있다면, 해당 정점을 큐에 저장한다.

 

 

4. 반복

큐가 빌 때까지 2~3 과정을 반복한다.

 

5. 사이클 검출(주어진 그래프가 DAG라 보장할 수 없는 경우에 추가)

반복이 종료되었음에도 정렬되지 않은 정점이 존재한다면 해당 그래프는 사이클이 존재한다는 의미가 된다. 따라서 정렬된 결과물의 정점 개수가 전체 정점 개수가 아니라면, 정렬을 실패했다는 의미(사이클이 검출되었다)로 false를 반환한다.

 

6. 최종 결과

사이클이 검출되지 않았다면 위상 정렬이 적용된 결과를 얻을 수 있다.

 

구현 코드

BFS가 기반인 알고리즘인 만큼 시간복잡도 또한 BFS를 따라가므로 시간복잡도는 O(V+E)이다.

int V;                      // 정점 개수
vector<vector<int>> graph;  // 그래프
vector<int> indeg;          // 각 정점의 indegree값이 저장된 배열

// 시간복잡도 O(V+E)
bool topologicalSorting(vector<int>& result){

    queue<int> q;
    
    // indeg가 0인 정점들을 큐에 추가
    for(int i = 1; i <= V; i++){
        if(indeg[i] == 0){
            q.push(i);
        } 
    }

    // indeg가 0인 정점이 큐에 존재하지 않을 때까지 반복
    while(!q.empty()){
        int vtx1 = q.front(); q.pop();
        result.push_back(vtx1);

        for(int vtx2 : graph[vtx1]){
            indeg[vtx2]--;

            if(indeg[vtx2] == 0){     
                q.push(vtx2);
            } 
        }
    }

    // 사이클이 발생했다면 false 반환.
    if(result.size() != V) return false;

    return true;
}

 

 

짚고 넘어가야 할 점

위상 정렬이 실행되는 동안 모든 정점들이 indegree가 0인 경우가 항상 존재할까?

위상 정렬은 DAG 그래프 위에서 작동한다. 따라서, 사이클이 존재하지 않으므로 초기 그래프에 indegree가 0인 정점이 적어도 하나 이상 존재해야 한다. 해당 정점이 선택되고 간선을 지웠을 때도 동일하다. 변경된 그래프는 초기 그래프의 부분집합이므로, 변경된 그래프 또한 DAG이다. 따라서 변경된 그래프에도 사이클이 존재하지 않으므로 indegree가 0인 정점이 적어도 하나 이상 존재해야 한다.

 

해당 과정은 정렬이 끝날 때까지 반복되므로, 위상 정렬은 매 반복마다 indegree가 0인 정점이 항상 존재한다.

 

사이클을 검출하는 원리도 여기서 온다. 만약 사이클이 단 하나라도 존재할 경우 사이클에 포함된 정점들의 선행 조건이 꼬리의 꼬리를 물고 있어 포함된 정점들은 indegree가 0이 될 수 없다. 결국 모든 정점을 정렬하기 전에 반복이 끝나게 되고, 이를 통해 사이클을 검출할 수 있다. 

 

위상 정렬된 결과물은 여러 개일 수 있다.

위상 정렬된 결과물은 하나가 아니다. 간단하게 BFS와 DFS의 순회 방법이 다름에도 각각을 사용한 위상 정렬 방법이 있듯 그 결과물 또한 다를 수 있다는 것이다. 

참고자료

https://www.youtube.com/watch?v=Th-gLZUrd04

https://leetcode.com/discuss/general-discussion/1078072/introduction-to-topological-sort

https://cp-algorithms.com/graph/topological-sort.html

https://en.wikipedia.org/wiki/Topological_sorting