위상정렬(Topological Sort)

위상정렬(Topological Sort)이란?

• 유향 비순환 그래프(DAG, Directed Acyclic Graph)에서 정점을 간선의 방향을 거스르지 않도록 나열하는 알고리즘이다.
  • 다음 라면 끓이기 예제를 보자

우리는 라면을 끓일 때 냄비에 물을 먼저 부어도 되고 라면 봉지를 먼저 뜯어도 되지만 계란은 맨 마지막에 풀어야 한다.

이러한 방향은 있지만 사이클은 없는 그래프를 간선의 방향을 거스르지 않고 한 줄로 정렬시키는 것이 위상정렬이라고 보면 될 것 같다.

위상정렬 알고리즘(1)

• 진입 간선이 없는 정점을 연결리스트 R의 맨 뒤에 연결하고 해당 정점과 그 정점의 진출 간선을 제거하는 과정을 반복한다.
• 의사 코드는 다음과 같으며 위의 예시를 구하는 과정은 그 다음 그림과 같다.

topological_sort1(G) {
    for i ← 1 to n {
    	/* 진입 간선이 없는 정점 u 선택 */
        /* 연결리스트 R의 맨 뒤에 u 삽입 */
        /* 정점 u와 u의 진출 간선 제거 */
    }
}

위상정렬 알고리즘(2)

• 깊이 우선 탐색을 기반으로 탐색중인 정점을 순서대로 연결리스트 R의 맨 앞에 연결하는 과정을 반복한다.
• 의사 코드는 다음과 같으며 위의 예시를 구하는 과정은 그 다음 그림과 같다.

topological_sort2(G, V) {
    for each v ∈ V {
    	visited[v] ← false;
    }
    for each v ∈ V {
        if visited[v] = false
            then dfs_tf(v);
    }
}
dfs_ts(v) {
    visited[v] = true;
    for each x ∈ adj[v] {
        if visited[x] = false
            then dfs_ts(x);
    }
    /* 연결리스트 R의 맨 앞에 v 삽입 */
}

이해를 돕기 위해 백준 문제를 첨부한다.

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

위상정렬 알고리즘(1)을 이용한 풀이

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

public class Main {

    static int[] inDegree;
    static ArrayList<Integer>[] edges;

    public static String topologySort() {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < inDegree.length; i++) {
            int p = queue.poll();
            sb.append(p).append(" ");
            for (int e : edges[p]) {
                if (--inDegree[e] == 0) {
                    queue.offer(e);
                }
            }
        }
        return sb.toString();
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        edges = new ArrayList[n + 1];
        inDegree = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            edges[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(b);
            inDegree[b]++;
        }
        System.out.println(topologySort());
    }
}

위상정렬 알고리즘(2)를 이용한 풀이

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class Main {

    static Stack<Integer> stack = new Stack<>();
    static ArrayList<Integer>[] edges;
    static boolean[] visited;

    public static String topologySort(int n) {
        Arrays.fill(visited, false);
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                dfs_ts(i);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop()).append(" ");
        }
        return sb.toString();
    }

    public static void dfs_ts(int v) {
        visited[v] = true;
        for (int x : edges[v]) {
            if (!visited[x]) {
                dfs_ts(x);
            }
        }
        stack.push(v);
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        edges = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            edges[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(b);
        }
        System.out.println(topologySort(n));
    }
}