[Algorithm] 위상 정렬(Topological Sort)

위상 정렬(Topological Sort)?

위상 정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘으로, 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것이다.

 

실생활을 예로 들면,

인터넷 검색을 하기 위해선 다음과 같은 순서로 행동해야한다.

컴퓨터 전원 키기 -> 브라우저 키기 -> 검색 엔진 포털 진입 -> 검색

위 순서가 바뀐다면 검색을 할 수 없을 것이다.

 

위상 정렬은 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬이 된다.

그래프가 DAG가 아닌 경우 그래프에 대한 위상 정렬은 불가능하다.

 

BFS 예시 코드 수행 시

DFS 예시 코드 수행 시

여기서 주의할 점은 E가 수행되기 위해선 B와 D가 모두 수행되어야 한다는 점이다.

 

비순환 방향 그래프 (DAG: Directed Acyclic Graph)?

비순환 방향 그래프(DAG)는 사이클이 없는 방향 그래프이다.

DAG는 이벤트 간의 우선순위를 나타내기 위해 주로 사용된다.

 

 

구현

위상 정렬은 BFS, DFS 두 가지 방식으로 구현할 수 있다.

 

BFS로 구현

1. 모든 정점의 진입 차수(inDegree)를 설정한다.
2. 진입차수가 0인 정점을 방문한 것으로 표시하고 해당 정점을 Queue에 추가한다.
3. Queue에서 요소를 꺼내 인접한 정점 중 방문하지 않은 정점들의 진입차수를 하나씩 감소시킨다.
4. 진입차수가 0이된 정점은 Queue에 추가한다.
5. Queue가 비어있을 때까지 순회하며 2 ~ 4 과정을 반복한다.

import java.util.*;

public class TopologicalSortByBFS {

    private static int[][] graph = {{},
            {2, 4},
            {3, 5},
            {},
            {5},
            {6},
            {}};
    private static int[] inDegree;
    public static void main(String[] args) {
        inDegree = new int[graph.length];

        setInDegree();
        search();
    }

    public static void setInDegree() {
        for (int i = 1; i < graph.length; i++) {
            for (int next : graph[i]) {
                inDegree[next]++;
            }
        }
    }

    public static void search() {
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 1; i < graph.length; i++) {
            if (inDegree[i] == 0) {
                dq.offerLast(i);
            }
        }

        for (int i = 1; i < graph.length; i++) {
            if (dq.isEmpty()) {
                return;
            }
            
            int cur = dq.poll();
            System.out.print(cur + " ");

            for (int next : graph[cur]) {
                if (--inDegree[next] == 0) {
                    dq.offer(next);
                }
            }
        }
    }
}

 

DFS로 구현

1. 임의의 정점에서 다음과 같이 DFS를 수행한다.
2. 방문 표시를 하면서 간선을 따라 다음 정점으로 방문한다.
3. 더 이상 방문할 간선이 없으면 정점을 Queue 또는 Stack 첫번째에 추가한다.
4. 모든 정점을 탐색할 때 까지 2 ~ 3을 반복 수행한다.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class TopologicalSortByDFS {

    private static int[][] graph = {{},
            {2, 4},
            {3, 5},
            {},
            {5},
            {6},
            {}};
    private static Deque<Integer> vertexes;
    private static boolean[] visited;
    public static void main(String[] args) {
        vertexes = new ArrayDeque<>();
        visited = new boolean[graph.length];

        for (int i = 1; i < graph.length; i++) {
            if (visited[i]) {
                continue;
            }
            search(i);
        }

        System.out.println(vertexes);
    }

    public static void search(int cur) {
    	visited[cur] = true;
        for (int next : graph[cur]) {
            if (visited[next]) {
                continue;
            }
            search(next);
        }

        vertexes.addFirst(cur);
    }
}