토폴로지 정렬이란?
토폴로지 정렬(topological sort)은 방향 그래프(directed graph)의 정점들을 선형 순서로 나열하는 알고리즘입니다. 핵심 규칙은 간단합니다. 정점 u에서 정점 v로 향하는 방향 간선 U→V가 존재한다면, 정렬 결과에서 u는 반드시 v보다 앞에 위치해야 합니다. 따라서 토폴로지 정렬은 방향 그래프에서만 의미가 있습니다.
토폴로지 정렬이 활용되는 실제 사례
토폴로지 정렬은 실생활의 다양한 상황에서 매우 유용하게 사용됩니다.
- 요리 레시피: 레시피에는 다음 단계로 넘어가기 전에 반드시 거쳐야 하는 필수 단계가 있지만, 일부 단계는 서로 독립적이어서 병렬로 수행할 수 있습니다.
- 대학 수강 신청: 고급 과목을 수강하려면 선수 과목을 먼저 이수해야 하며, 그 선수 과목 역시 또 다른 과목의 선수 과목일 수 있습니다.
예제: 대학 교육과정 그래프
/** * CS101 CS102 * / \ / * CS204 CS340 * \ /| \ * CS380 | CS410 * \ | / * CS540 */
위 그래프에서 특정 과목을 수강하려면, 해당 과목과 연결된 바로 위 단계의 모든 과목을 먼저 이수해야 합니다. 이 그래프에서 가능한 토폴로지 정렬 결과는 다음과 같습니다.
CS101 -> CS204 -> CS102 -> CS340 -> CS410 -> CS380 -> CS540
CS102 -> CS101 -> CS340 -> CS204 -> CS410 -> CS380 -> CS540
JavaScript로 토폴로지 정렬 구현하기
이제 JavaScript로 직접 구현해 보겠습니다. 총 두 개의 함수를 작성합니다. 하나는 재귀적으로 그래프를 탐색하며 방문 여부를 표시하는 topologicalSortHelper, 다른 하나는 전체 정렬을 수행하는 topologicalSort입니다.
1. 재귀 헬퍼 함수와 메인 정렬 함수
topologicalSortHelper(node, explored, s) {
explored.add(node);
// 현재 노드를 방문 처리한 뒤,
// 이 노드에 의존하는 노드들로 이동합니다. 간선 방향은 node ----> n 입니다.
this.edges[node].forEach(n => {
if (!explored.has(n)) {
this.topologicalSortHelper(n, explored, s);
}
});
// 현재 노드의 모든 의존성이 해결되었으므로 스택에 추가합니다.
s.push(node);
}
topologicalSort() {
// 정렬된 순서의 요소들을 추적하기 위한 스택을 생성합니다.
let s = new Stack(this.nodes.length);
let explored = new Set();
// 그래프의 모든 미방문 노드에 대해 헬퍼 함수를 호출합니다.
this.nodes.forEach(node => {
if (!explored.has(node)) {
this.topologicalSortHelper(node, explored, s);
}
});
while (!s.isEmpty()) {
console.log(s.pop());
}
}구현 테스트하기
작성한 코드를 아래와 같이 테스트할 수 있습니다.
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addDirectedEdge("A", "C");
g.addDirectedEdge("A", "B");
g.addDirectedEdge("A", "D");
g.addDirectedEdge("C", "D");
g.addDirectedEdge("D", "E");
g.addDirectedEdge("E", "F");
g.addDirectedEdge("B", "G");
g.topologicalSort();
그래프 구조 시각화
위 코드로 생성한 그래프는 다음과 같은 구조를 가집니다.
/**
* A
* / | \
* C | B
* \ | |
* D G
* |
* E
* |
* F
*/
실행 결과
코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.
A
B
G
C
D
E
F
동작 원리 정리
이 알고리즘이 올바르게 동작하는 이유는 DFS(깊이 우선 탐색)의 특성 때문입니다. DFS는 한 노드에서 출발해 더 이상 진행할 수 없는 지점까지 먼저 탐색한 후 되돌아오기 때문에, 어떤 노드가 스택에 push되는 시점에는 해당 노드가 의존하는 모든 노드가 이미 스택에 들어가 있는 상태입니다. 따라서 스택에서 pop하는 순서대로 출력하면 의존 관계를 만족하는 올바른 토폴로지 순서를 얻게 됩니다. 시간 복잡도는 그래프의 정점 수를 V, 간선 수를 E라 할 때 O(V + E)로 매우 효율적입니다.