위상 정렬 Topological Sorting

위상 정렬

위상 정렬이란?

위상 정렬 Topological Sorting 이란 방향이 있는 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 즉 한 정점에 도달하기 전 먼저 거쳐야 하는 정점들의 순서가 있는 경우 사용하는 알고리즘이다.

만약 특정 수강과목에 선수과목이 있다면 그 선수과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 대 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 방향이 있는 (유향의) 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 유향 그래프 directed acyclic graph 여야 한다.

위상 정렬의 수행과정

1. 자기 자신을 가리키는 변이 없는 정점을 찾는다.
2. 찾은 정점을 출력하고 출력한 정점과 그 정점에서 출발하는 변을 삭제한다.
3. 아직 그래프에 정점이 남아있으면 1로 돌아가고, 아니면 알고리즘을 종료한다.

예시

위 그래프에서 정점 x로부터 y로의 간선은 일 x가 y를 시작하기 전 선행되어야 함을 나타낸다. 이 그래프를 대상으로 위상 정렬 알고리즘을 수행하면 다음과 같다. (가장 작은 수 부터)

회차	조건	수행	출력
1	2를 가리키는 간선이 있다	다음 정점으로 넘어간다	-
2	3을 가리키는 간선이 없다	3을 출력, 정점 3과 간선 <3, 8>, <3, 10> 을 삭제	3
3	5를 가리키는 간선이 없다	5를 출력, 정점 5와 간선 <5, 11> 삭제	3 5
4	7을 가리키는 간선이 없다	7을 출력, 정점 7과 간선 <7, 11>, <7, 8> 삭제	3 5 7
5	8을 가리키는 간선이 없다	8을 출력, 정점 8과 간선 <8, 9> 삭제	3 5 7 8
6	9를 가리키는 간선이 있다	다음 정점으로 넘어간다	3 5 7 8
7	10을 가리키는 간선이 있다	다음 정점으로 넘어간다	3 5 7 8
8	11을 가리키는 간선이 없다	11을 출력, 정점 11과 간선 <11,2>, <11, 9>, <11, 10>을 삭제	3 5 7 8 11
9	남은 정점 2를 가리키는 간선이 없다	2를 출력, 정점 2 삭제	3 5 7 8 11 2
10	남은 정점 9를 가리키는 간선이 없다	9를 출력, 정점 9 삭제	3 5 7 8 11 2 9
11	남은 정점 10을 가리키는 간선이 없다	10을 출력, 정점 10 삭제	3 5 7 8 11 2 9 10
12	남아있는 정점이 없다	루프를 종료한다	3 5 7 8 11 2 9 10

알고리즘

위상 정렬의 일반적인 알고리즘은 정점의 양수 노드의 선형 실행 시간을 갖는다. $O(|V|+|E|)$

더 알아볼 것

• Kahn 알고리즘
• DFS 알고리즘을 기반한 위상 정렬 대체
• Parallel 알고리즘

위키피디아 참고