[알고리즘] 위상 정렬을 이해해보자.

* 이 글은 알고리즘에 관해 학습하며 정리한 글입니다. 틀린 점이나, 고쳐야 할 부분이 있으면 알려주세요..!

 

 

 

위상 정렬이란?

 

• 위상 정렬이란(Topological Sort) : 사이클이 없는 방향 그래프(Directed Acyclic Graph, DAG)에서 정점을 선형순서로 나열하는 것이다.

 

이때 DAG, 즉 사이클이 없는 방향 그래프란 주로 노드들 간에 우선순위를 나타내기 위해서 사용한다. 만약 노드들간에 사이클이 존재한다면, DAG라고 볼 수 없다.

 

즉, 우선 순위가 존재하는 노드들 간에 순서를 나타낸 것인데, 만약 우선순위가 동일하다면 그 중 임의의 하나를 선택한다. 그래서 위상 정렬은 여러 값이 나올 수 있다.

 

일반적으로 위상 정렬을 사용하는 때는 의존 관계가 존재할 때, 수행 가능한 작업 순서를 도식화하기 위해 사용한다. 의존 관계가 바로 노드와 노드 사이의 간선과 그 방향이 되기 때문이다.

 

 

 

 

위상 정렬의 구현을 위해 알아야 하는 것

 

개념은 알았으니, 위상 정렬을 수행하기 위해서는 어떤 단계를 거쳐야 하는 지 파악해야 한다.

이를 위해 기본적인 차수의 개념을 숙지할 필요가 있다.

 

차수는 정점에 인접한 정점의 수를 말한다. 정점은 노드라고 보아도 좋다. 결국 하나의 정점 근처에 있는 정점들을 보는 것인데, 이 정점들간에도 서로 방향이 존재하는 그래프도 있다. 그래서, 정점들간의 방향에 따라 차수를 부르는 말도 나뉜다.

 

먼저, 인접한 정점에서 주 정점으로 들어오는 것의 수을 진입 차수(In-degree)라고 하고, 주 정점에서 인접한 정점으로 나가는 것의 수를 진출 차수(out-degree)라고 한다.

 

예를 들어, 아래의 그림과 같은 그래프가 있다면, a의 진출 차수는 2이고 진입 차수는 1이라고 볼 수 있다.

 

 

 

 

다음으로 알아야 할 것은 DFS 개념이다. 물론, 위상 정렬은 BFS와 DFS로 모두 구현할 수 있지만, 이번 위상 정렬에서는  DFS를 사용하여 구현할 것이다.

 

간단하게 DFS를 설명하자면, DFS는 임의의 정점에서 시작하여 이웃하는 하나의 정점을 방문하고, 그 정점의 이웃정점을 방문하며, 모두 방문하면 다시 되돌아가 탐색을 수행하는 방식이다.

 

느낌만으로 보면, 꼬리에 꼬리를 무는 식으로 방금 방문한 이웃의 이웃을 재귀적으로 탐색하는 것과 같다. 실제로도 재귀함수를 통해 구현하는 편이다.

 

DFS에 대한 더욱 자세한 설명은 다른 포스팅에서 참고하길 바라며, 이제 위상 정렬을 직접 구현해 볼 차례이다.

 

 

 

 

위상 정렬의 구현

 

일반적으로 두 가지 방법이 있다.

 

1. 그래프에서 진입 차수가 0인 정점 v로부터 시작하여 v를 출력하고 v를 그래프에서 제거하는 과정을 반복하는 순방향 방법.

 

2. 진출차수가 0인 정점 v를 출력하고 v를 그래프에서 제거하는 과정을 반복하여 얻은 출력 리스트를 역순으로 만들어 결과를 얻는 방법.

 

 

우리는 이 역방향 방법을 DFS와 함께 사용하여 쉽게 구현할 것이다. 핵심 아이디어는 DFS이다. 그 개념을 다시 한번 떠올리면, 이웃의 이웃의 이웃의... 느낌으로 계속 파고 든다. 이는 제일 처음의 정점이 추가되기 이전에 그 이웃들을 모두 추가할 수 있다는 뜻이 된다. 이런 방식을 적용한 리스트를 역순으로 뒤집기만 하면 제일 처음의 정점이 첫 번째 위치에 오게 되어 위상 정렬을 만들 수 있다.

 

 

아래 자바 언어로 구현된 위상 정렬 코드를 보면, 무슨 말인 지 쉽게 알 수 있을 것이다.

 

 

 

class TopologicalSort {
    int N;
    // 방문한 배열에 대해 표시
    boolean[] visited;
    // 인접 리스트(정점에 대한 인접 정점들 리스트)
    List<Integer>[] adjList;
    // 위상정렬 결과 리스트
    List<Integer> sequence;
    // 초기화
    public TopologicalSort(List<Integer>[] graph) {
        N = graph.length;
        visited = new boolean[N];
        adjList = graph;
        sequence = new ArrayList<>();
    }
    
    // 위상 정렬 수행
    public List<Integer> tsort() {
        for(int i=0; i<N; i++) if (!visited[i]) dfs(i);
        // 정답 리스트 역순으로 뒤집음
        Collections.reverse(sequence);
        return sequence;
    }
    // dfs: 방문한 배열을 true로 설정해주고, 인접리스트에 방문
    public void dfs(int i) {
        visited[i] = true;
        for(int v: adjList[i]) {
            if (!visited[v]) dfs(v);
        }
        // 여기가 제일 중요. 이 구간에 위치하면, 가장 마지막으로 방문하는 정점이 먼저 추가된다.
        sequence.add(i);
    }
}

 

 

이에 대한 main 함수 구현 예제이다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int N = 9;
        List<Integer>[] adjList = new List[N];
        for (int i = 0; i < N; i++) {
            adjList[i] = new ArrayList<>();
        }
        adjList[2].add(0);     adjList[2].add(1);    adjList[0].add(1);
        adjList[1].add(3);     adjList[1].add(4);    adjList[4].add(5);
        adjList[5].add(3);     adjList[5].add(7);    adjList[3].add(6);
        adjList[6].add(7);     adjList[7].add(8);

        TopologicalSort t = new TopologicalSort(adjList);
        List<Integer> sortedSeq = t.tsort();
        System.out.printf("위상 정렬: ");
        System.out.println(sortedSeq);
    }
}

 

 

결과 값은 아래와 같다.

 

 

위상 정렬의 수행 시간

 

위상 정렬은 실제로 DFS를 수행하는 시간과 동일하게 O(n+m)만큼 소요된다.

동일한 이유는 실질적으로 정점을 정답 리스트에 추가하는 시간과 리스트를 역순으로 만드는 시간이 O(n)이기 때문이다.

O(n+m) = O(n+m) + O(n) 이 성립하기에 위상 정렬의 수행 시간은 O(n+m)이다.