위상정렬(topological sorting)

방향이 있는 그래프(directed graph)에서 꼭짓점들이 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.

 

대개 많이 언급되는 예시로 대학 강의에서의 선수과목 체계가 제시된다. 너무 질리니까 여기서는 게임 스킬트리의 일종이라고도 할 수 있는, 스타크래프트의 프로토스 테크트리로 대체해서 설명한다. 다음은 모든 건물들을 제시하고 있지는 않지만, 실제 선결 조건들이 제시되어 있다.

 

 

위상정렬은 위와 같이 비순환 유향 그래프(DAG, directed acyclic graph)의 건물들을 선후 관계에 따라 정렬하고자 할 때 이용되며, 그 결과는 여러가지일 수 있다. 위상정렬을 수행하기 위해서 비순환 그래프이어야 하는 이유, 즉 사이클이 존재하지 않아야 하는 이유는, 사이클이 있으면 시작점을 어느 정점으로 설정하더라도 위배되기 때문이다.

 

위상 정렬의 방법에는 스택을 이용하는 방법과 큐를 이용하는 방법 두 가지가 있다.

편의를 위해 위 그래프를 아래와 같이 표현한다.

 

 

큐를 이용하는 방법

각 정점에 대해 in-degree를 저장해둔다.

 

정점	1	2	3	4	5	6	7	8	9	10
진입 차수	0	1	1	1	1	1	1	1	2	1

 

그리고 2, 3을 반복한다.

1. 진입차수가 0인 정점, 즉 선결조건이 없는 정점들을 큐에 삽입한다.

2. 큐에서 정점을 꺼내서, 해당 정점이 출발점인 간선을 모두 제거한다.

3. 진입차수가 0인 정점을 큐에 삽입한다.

 

모든 원소를 방문하기 전에 큐가 빈다면?

진입차수가 0이 아닌 정점이 남아있다는 것, 즉 선결조건이 완료되지 않은 정점이 남아있다는 것이므로 이는 곧 사이클의 존재를 의미한다.

모든 원소를 방문한다면?

큐에서 꺼낸 순서가 곧 위상정렬의 결과이다.

 

이를 통해 우리가 알 수 있는 것은, 위 알고리즘은 위상정렬의 결과뿐만 아니라, 어떤 그래프가 위상정렬이 가능한 그래프인지 가능하지 않은 그래프인지의 여부에 대해서도 제공한다는 것이다.

 

import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int n; // num of nodes
    static int m; // num of edges
    static List<Integer>[] graph;
    static int[] inDegree;
    static int[] res;

    public static void main(String[] args) {
        // input begins
        n = sc.nextInt();
        m = sc.nextInt();
        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        inDegree = new int[n + 1];
        res = new int[n + 1];
        while (m-- > 0) {
            int dept = sc.nextInt();
            int dest = sc.nextInt();
            graph[dept].add(dest);
            inDegree[dest]++;
        }
        // input ends

        if (topologicalSort()) {
            for (int i = 1; i <= n; i++) {
                System.out.printf("%d ", res[i]);
            }
        } else {
            System.out.println("Cyclic graph");
        }
    }

    static boolean topologicalSort() {
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        for (int i = 1; i <= n; i++) {
            if (queue.isEmpty()) {
                return false;
            }

            int cur = queue.poll();
            res[i] = cur;
            for (int j = 0; j < graph[cur].size(); j++) {
                int con = graph[cur].get(j);
                inDegree[con]--;
                if (inDegree[con] == 0) {
                    queue.offer(con);
                }
            }
        }

        return true;
    }
}

 

 

스택을 이용하는 방법

DFS에서 어떤 정점에서 연결된 모든 정점을 탐색한 후에; 해당 정점을 

 

DFS가 종료되는 순서의 역순이 곧 위상정렬의 결과이다.

DFS는 이름에서도 알 수 있듯, 깊이를 우선으로 하여 가장 끝까지, 즉 더 이상 탐색할 수 있는 연결된 정점이 존재하지 않을 때까지 재귀적으로 함수가 호출된다. 곧 어떤 정점에서 연결된 모든 정점을 모두 탐색했다는 것은, 해당 정점의 degree(indegree 말고)가 0임을 의미하며, 즉 테크트리에서는 최종 테크라고 생각할 수 있다.

 

한편 스택을 이용하는 방법에서도 마찬가지로 위상정렬의 결과뿐만 아니라 해당 정렬의 가능 여부까지도 알 수 있다. 이를 위해서는 아래 코드에서와 같이, finish 배열을 별도로 하나 선언해두어, DFS가 완전히 종료된 정점을 표시해둔다. 그런데 만약에 연결된 정점을 살펴보던 중 visit && !finish인 정점이 있다면 이는 사이클이 존재함을 의미한다.

 

package algorithm.topologicalSortDfs;

import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int n; // num of nodes
    static int m; // num of edges
    static List<Integer>[] graph;
    static boolean[] visit;
    static boolean[] finish;
    static int[] res;
    static int r;
    static boolean cycle = false;

    public static void main(String[] args) {
        // input begins
        n = sc.nextInt();
        m = sc.nextInt();
        graph = new ArrayList[n + 1];
        visit = new boolean[n + 1];
        finish = new boolean[n + 1];
        res = new int[n + 1];
        r = n;
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        while (m-- > 0) {
            int dept = sc.nextInt();
            int dest = sc.nextInt();
            graph[dept].add(dest);
        }
        // input ends

        if (topologicalSort()) {
            for (int i = 1; i <= n; i++) {
                System.out.printf("%d ", res[i]);
            }
        } else {
            System.out.println("Cyclic graph");
        }
    }

    static boolean topologicalSort() {
        for (int i = 1; i <= n; i++) {
            if (!visit[n]) {
                dfs(i);
            }
        }

        if (cycle) {
            return false;
        }

        return true;
    }

    static void dfs(int u) {
        visit[u] = true;

        for (int i = 0; i < graph[u].size(); i++) {
            int con = graph[u].get(i);
            if (!visit[con]) {
                dfs(con);
            } else if (!finish[con]) {
                cycle = true;
            }
        }

        res[r--] = u;
        finish[u] = true;
    }
}