위상 정렬

위상 정렬은 방향 그래프에서 각 방향 간선 u→v에 대해 정점 u가 정점 v보다 먼저 오도록 정렬하는 알고리즘이다.

다시 말해, 위상 정렬은 방향 비순환 그래프의 정점들을 일렬로 나열하여 모든 방향 간선이 왼쪽에서 오른쪽으로 향하도록 배치한다.

다음 예제 그래프를 살펴보자:

이 그래프에는 두 가지 가능한 위상 정렬이 존재한다:

위상 정렬 결과는 S, V, W, T, X와 S, W, V, T, X이다. 모든 화살표가 왼쪽에서 오른쪽으로 향하는 것을 확인할 수 있다.

다음은 이 그래프에 대한 유효하지 않은 위상 정렬이다. X와 T가 V보다 먼저 올 수 없기 때문이다:

어디에 활용할까?

Swift Algorithm Club의 모든 알고리즘과 자료 구조를 배우고 싶다고 가정해 보자. 처음에는 벅차 보일 수 있지만, 위상 정렬을 사용하면 체계적으로 정리할 수 있다.

위상 정렬을 배우는 과정을 예로 들어 보자. 위상 정렬을 완전히 이해하려면 무엇을 먼저 알아야 할까? 위상 정렬은 깊이 우선 탐색과 스택을 사용한다. 하지만 깊이 우선 탐색 알고리즘을 배우기 전에 그래프가 무엇인지 알아야 하고, 트리에 대한 지식도 도움이 된다. 그래프와 트리는 객체를 연결하는 개념을 사용하므로, 이에 대한 내용도 먼저 공부해야 한다. 이 과정은 계속 이어진다.

이러한 목표를 그래프 형태로 표현하면 다음과 같다:

각 알고리즘을 그래프의 정점으로 생각하면, 그들 간의 의존 관계를 명확히 볼 수 있다. 어떤 것을 배우려면 먼저 다른 것을 알아야 할 때가 있다. 바로 이런 상황에서 위상 정렬이 활용된다. 위상 정렬은 무엇을 먼저 해야 하는지 알려준다.

어떻게 동작하는가?

1단계: 진입 차수가 0인 모든 정점 찾기

정점의 진입 차수는 해당 정점을 가리키는 간선의 수를 의미한다. 들어오는 간선이 없는 정점은 진입 차수가 0이다. 이 정점들은 위상 정렬의 시작점이 된다.

이전 예제를 기준으로, 이러한 시작 정점은 선수 과목이 없는 알고리즘과 자료구조를 나타낸다. 즉, 다른 것을 먼저 배울 필요가 없으므로 정렬은 이 정점들부터 시작한다.

2단계: 깊이 우선 탐색으로 그래프 순회

깊이 우선 탐색은 특정 정점에서 그래프를 순회하기 시작해 각 분기를 최대한 깊이 탐색한 후 돌아오는 알고리즘이다. 깊이 우선 탐색에 대해 더 자세히 알고 싶다면 상세 설명을 참고한다.

진입 차수가 0인 각 정점에 대해 깊이 우선 탐색을 수행한다. 이를 통해 시작 정점들과 연결된 정점들을 확인할 수 있다.

3단계: 방문한 모든 정점 기록

깊이 우선 탐색을 수행하면서 방문한 모든 정점을 리스트로 관리한다. 이는 동일한 정점을 두 번 방문하지 않기 위함이다.

4단계: 결과를 종합하기

정렬의 마지막 단계는 각 깊이 우선 탐색의 결과를 결합해 정점들을 정렬된 리스트로 만드는 것이다.

예제

다음 그래프를 살펴보자:

1단계: 진입 차수가 0인 정점은 3, 7, 5이다. 이 정점들을 시작점으로 설정한다.

2단계: 각 시작 정점에 대해 깊이 우선 탐색(DFS)을 수행한다. 이때 이미 방문한 정점은 기억하지 않는다:

정점 3: 3, 10, 8, 9
정점 7: 7, 11, 2, 8, 9
정점 5: 5, 11, 2, 9, 10

3단계: 이전 탐색에서 이미 방문한 정점을 필터링한다:

정점 3: 3, 10, 8, 9
정점 7: 7, 11, 2
정점 5: 5

4단계: 이 세 번의 깊이 우선 탐색 결과를 결합한다. 최종 정렬 순서는 5, 7, 11, 2, 3, 10, 8, 9이다. (중요: 각 후속 탐색 결과를 정렬된 리스트의 앞쪽에 추가한다.)

위상 정렬의 결과는 다음과 같다:

참고: 이 그래프의 위상 정렬 결과는 유일하지 않다. 예를 들어, 3, 7, 5, 10, 8, 11, 9, 2와 3, 7, 5, 8, 11, 2, 9, 10도 유효한 정렬 결과다. 모든 화살표가 왼쪽에서 오른쪽으로 향하는 순서라면 모두 유효한 정렬 결과이다.

코드

다음은 Swift로 위상 정렬을 구현한 예시이다 (TopologicalSort1.swift 참고):

extension Graph {
  public func topologicalSort() -> [Node] {
    // 1
    let startNodes = calculateInDegreeOfNodes().filter({ _, indegree in
      return indegree == 0
    }).map({ node, indegree in
      return node
    })
    
    // 2
    var visited = [Node : Bool]()
    for (node, _) in adjacencyLists {
      visited[node] = false
    }
    
    // 3
    var result = [Node]()
    for startNode in startNodes {
      result = depthFirstSearch(startNode, visited: &visited) + result
    }

    // 4    
    return result
  }
}

코드에 대한 설명:

각 정점의 진입 차수를 계산하고, 진입 차수가 0인 모든 정점을 startNodes 배열에 추가한다. 이 그래프 구현에서는 정점을 "노드"라고 부른다. 그래프 코드를 작성하는 사람들은 두 용어를 혼용하여 사용한다.
visited 배열은 깊이 우선 탐색 중에 이미 방문한 정점을 추적한다. 초기에는 모든 요소를 false로 설정한다.
startNodes 배열에 있는 각 정점에 대해 깊이 우선 탐색을 수행한다. 이 탐색은 정렬된 Node 객체 배열을 반환한다. 이 배열을 result 배열 앞에 추가한다.
result 배열은 위상 정렬된 순서로 모든 정점을 포함한다.

참고: 깊이 우선 탐색을 사용한 위상 정렬의 약간 다른 구현은 TopologicalSort3.swift를 참고한다. 이 구현은 스택을 사용하며, 진입 차수가 0인 모든 정점을 먼저 찾을 필요가 없다.

Kahn의 알고리즘

깊이 우선 탐색이 위상 정렬을 수행하는 일반적인 방법이지만, 이를 해결할 수 있는 또 다른 알고리즘이 존재한다.

모든 정점의 진입 차수를 계산한다.
진입 차수가 0인 정점들을 leaders라는 새로운 배열에 추가한다. 이 정점들은 다른 정점에 의존하지 않는다.
leaders 배열에 있는 정점들을 하나씩 제거한다. 실제로 그래프를 수정하지 않고, 해당 정점이 가리키는 정점들의 진입 차수를 감소시킨다. 이는 동일한 효과를 낸다.
각 리더의 이웃 정점들을 확인한다. 이웃 정점 중 진입 차수가 0이 된 정점이 있다면, 이 정점들도 leaders 배열에 추가한다.
더 이상 확인할 정점이 없을 때까지 이 과정을 반복한다. 이 시점에서 leaders 배열은 정렬된 순서로 모든 정점을 포함한다.

이 알고리즘은 **O(n + m)**의 시간 복잡도를 가지며, 여기서 n은 정점의 수이고 m은 간선의 수이다. 구현은 TopologicalSort2.swift에서 확인할 수 있다.

출처: 이 대체 알고리즘에 대해 처음으로 읽은 것은 1993년 5월 Dr. Dobb's Magazine의 Algorithm Alley 칼럼이다.

Swift Algorithm Club의 Ali Hafizji와 Matthijs Hollemans가 작성함