Topological Sorting (위상정렬)
개요
위상 정렬(Topological Sorting)은 방향성을 가지며 순환이 없는 그래프(Directed Acyclic Graph, DAG)의 노드들을 특정 순서로 정렬하는 알고리즘이다. DAG 구조에서 위상 정렬은 주로 작업 스케줄링, 의존성 관리 등에 활용된다.
위상 정렬이란?
위상 정렬(Topological Sorting)은 방향성을 가진 순환이 없는 그래프(DAG, Directed Acyclic Graph)에서 모든 노드를 순서대로 정렬하는 기법이다. 이때, 정렬된 순서는 노드 간의 의존 관계를 유지해야 한다. 즉, 어떤 작업 A가 작업 B에 의존한다면, 위상 정렬 결과에서는 반드시 작업 A가 작업 B보다 앞에 나와야 한다.
위상 정렬의 본질은 그래프의 각 노드들이 가지는 의존성(간선)을 고려하여 순서를 정하는 것이다. DAG에서 이러한 의존성을 해결하는 유일한 방법이 바로 위상 정렬이다.
•
위상 정렬의 결과는 반드시 유일하지 않다.
주요 개념
다음은 위상정렬의 수도 코드
위상 정렬 알고리즘(그래프 G):
진입 차수가 0인 모든 노드를 큐에 삽입한다.
큐가 빌 때까지 다음을 반복한다:
큐에서 노드를 하나 꺼내서 정렬 결과에 추가한다.
해당 노드와 연결된 모든 노드의 진입 차수를 1 감소시킨다.
진입 차수가 0이 된 노드를 다시 큐에 삽입한다.
결과가 그래프의 모든 노드를 포함한다면 위상 정렬 성공.
포함하지 않는다면 순환이 존재하는 그래프이므로 실패.
Python
복사
위상 정렬의 규칙
위상 정렬의 규칙은 매우 간단하다. 선행 관계가 있는 노드는 항상 후행 노드보다 먼저 정렬되어야 한다는 것이다. 예를 들어, 어떤 작업이 다른 작업에 의존하는 경우, 의존하는 작업이 반드시 먼저 수행되어야 한다. 위상 정렬은 이러한 의존성을 정확히 반영한 정렬 결과를 제공한다.
DAG (Directed Acyclic Graph)
위상 정렬은 대그 (DAG) 라는 조건을 만족해야한다. 사이클이 없는 방향 그래프를 DAG라고 하며, 그래프 내에서 사이클이 없어야한다. 만약 사이클이 존재하면 서로 어떤 것이 먼저인지 판별이 불가능하기 때문이다.
위상 정렬의 방법
1.
싱크를 활용하기
2.
DFS를 활용하기
•
예시로 쓸 그래프 도식화 (노드 8개)
1 → 2 → 5 → 8
↓ ↓ ↓
3 → 4 6
↓
7
Plain Text
복사
위상 정렬 과정 - 1. 싱크 제거 방식
1 → 2 → 5
↓ ↓ ↓
3 → 4 6
↓
7
Plain Text
복사
1단계
•
첫번째 제거할 싱크는 8 이다.
◦
그 결과로 6, 7 이 싱크로 남는다.
1 → 2 → 5
↓ ↓ ↓
3 → 4 6
Plain Text
복사
2단계
•
두번째 제거할 싱크는 7 이다.
◦
그 결과로 4 가 싱크가 된다
◦
7 → 8 로 정렬이 된 상태이다.
1 → 2 → 5
↓ ↓
3 → 4
Plain Text
복사
3단계
•
세번째로 제거할 싱크는 6이다.
◦
그 결과로 5 가 싱크가 된다.
◦
6 → 7 → 8 로 정렬이 된 상태가 된다.
1 → 2
↓ ↓
3 → 4
Plain Text
복사
4단계
•
네번째로 제거할 싱크는 5 이다.
◦
그 결과로 4 만 싱크가 된다.
◦
5 → 6 → 7 → 8 로 정렬이 되었다.
1 → 2
↓
3
Plain Text
복사
5단계
•
다섯번째로 제거할 싱크는 4 이다.
◦
그 결과로 2, 3 이 싱크가 된다
◦
4 → 5 → 6 → 7 → 8 로 정렬이 되었다.
•
이후 여섯번째, 일곱번째를 거쳐서 1 만 남게 된다.
◦
최종적으로 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 로 정렬이 되었다.
◦
앞에서 언급했지만, 위상 정렬에서 싱크가 여러 개일 때 어떤 것을 없앨지는 자기 만의 기준을 가지고 선택하면 된다. 즉, 위상 정렬의 결과는 여러 개 나올 수가 있으면 유니크하지 않다.
위 싱크 제거 방식은 백 트래킹을 통해서 구현할 수 있다. 유사 코드는 다음과 같다.
TopologicalSort(G) {
for (step = 1 through N)
{
Select a Sink T; # 싱크가 여럿이면 아무거나
L.Insert(1, T); # 연결 리스트의 맨 앞에 삽입
Remove the Sink T and Edges Connected to It; # 싱크 및 연결된 간선 삭제
}
}
Python
복사
위상 정렬 과정 - DFS
•
DFS로 위상 정렬을 할 때의 문제점
◦
더 이상 방문할 곳이 없을 때 직전에 방문한 노드로 되돌아가는 작업인 ‘백 트랙’에서부터 문제가 발생한다. 마지막 노드가 싱크이므로 백트랙을 하면서 싱크를 제거하는 작업을 진행하는 것과 마찬가지가 된다.
◦
그러나 유의할 점은 DFS로 간 순서 자체가 위상정렬 순서는 아니다.
▪
위 예시에서 DFS를 실행한 결과를 보면,
1 → 2 → 5 → 8 → 6 → 4 → 7 → 3 이 된다. 3 이 8 보다 나중될 수가 없다.
따라서, DFS 결과가 반드시 위상정렬의 결과가 되는 것은 아니다.
◦
이를 해결하기 위해서 백 트랙이 발생한 순서대로 기록하면 된다. 즉, 백 트랙이 발생할 때마다 리스트에 결과를 집어 넣어주면 된다.
1 → 2 → 5 → 8
↓ ↓ ↓
3 → 4 6
↓
7
Plain Text
복사
위 예시에서 DFS로 들어가는 과정 중 백트랙이 제일 먼저 시작되는 것은 6이다.
따라서, 6 → 8 → 5 로 백트랙을 하면서 돌아오면 4 로 넘어간다. 4에서 연결되있는 것은 7 이므로 7 이후 싱크임을 확인하고 백트랙 한다.
이렇게 되면 6 → 8 → 5 → 7 이 되고, 4 도 싱크가 되므로 백트랙을 하여 2 로 돌아간다.
2 이후로 갈 곳이 없게 되므로 3 을 가게되고 백트랙하면서 6 → 8 → 5 → 7 → 4 → 2 → 3 → 1 로 순으로 정리된다.
싱크 제거하는 방식으로 다시 돌아가보면, 6 을 먼저 없애고, 그 다음 싱크인 8 을 없애면서 싱크를 제거하면서 가져가는 결과와 같은 결과가 나온다.
수도 코드는 다음과 같다.
TopologicalSort(V){
for All Nodes T Adjacent to V
if (T Is Unvisited)
TopologicalSort(T);
L.ListInsert(1, V);
}
Python
복사
요약
•
위상 정렬(Topological Sorting)은 방향성을 가진 순환이 없는 그래프(DAG, Directed Acyclic Graph)에서 모든 노드를 순서대로 정렬하는 기법이다.
•
위상 정렬은 싱크 제거 방식과 DFS 방식으로 구현 가능하다.
REFERENCES
1.
주우석, 2015, C/C++로 배우는 자료구조론, 한빛미디어
Written by Changyu Lee