위상정렬(topology sort)은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.
| 기능 | 특징 | 시간 복잡도(노드 수 : V, 에지 수 : E) |
|---|---|---|
| 노드 간의 순서를 결정 | 사이클이 없어야 함 | O(V + E) |
위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.
위상 정렬의 원리 이해하기
1 ArrayList로 그래프를 표현했다. 그래프는 사이클이 없는 상태이다.
그래프를 보고 진입 차수 배열 D를 만든다. 진입 차수는 자기 자신을 가리키는 에지의 개수이다.
예를 들어 1에서 2, 3을 가리키고 있으므로 D[2], D[3]을 각각 1만큼 증가시킨다.
2 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.
3 모든 노드가 정렬될 때까지 반복한다. 다음 노드로 선택될 수 있는 것은 진입 차수가 0인 2와 3이 된다. 여기서 누굴 먼저 선택할지에 따라 정렬 순서가 달라지게 되므로 위상 정렬은 늘 같은 결과를 보장하지 않는다.
- Do it! 알고리즘 코딩테스트 자바 편
