위상 정렬 (topology sort)

위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.

 

기능	특징	시간 복잡도(V : 노드 수, E: 엣지 수)
노드 간의 순서를 결정	사이클이 없어야 함	O(V + E)

 

 

위상 정렬의 핵심 이론

 

1. 진입 차수 이해하기

진입 차수(in-degree)는 자기 자신을 가리키는 에지의 개수이다.

 

 

이 때, 진입 차수 배열 D[N]은 아래와 같다.

1	2	3	4	5
0	1	1	2	2

 

 

2. 진입 차수 배열 D[N]에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다. 그 후, 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.

 

위 그림의 경우 진입 차수가 0인 노드 1을 선택하여 2, 3의 진입 차수를 1씩 빼 D[2], D[3]을 0으로 만든 것이다. 계속해서 다음 노드 2를 선택해서 반복한다. 이 과정을 모든 노드가 정렬될 때까지 반복한다. 여기서 진입 차수가 0인 노드 3을 먼저 선택했다면 3이 우선 위산 정렬 배열에 들어갈 것이다. 이를 통해 위상 저렬은 늘 같은 정렬 결과를 보장하지 않는다는것을 알 수 있다.