『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.
위상 정렬 (Topological sort)
- 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.
- 노드 간의 순서를 결정한다.
- 사이클이 없어야 한다.
- 노드 수를 V, 에지 수를 E라고 했을 때 시간 복잡도는 O(V+E)이다.
- 위상 정렬에서는 다음 사항들을 주의해야 한다.
- 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다.
- 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로, 위상 정렬을 적용할 수 없다.
핵심 이론
진입 차수
진입 차수(in-degree)는 자기 자신을 가리키는 에지의 개수이다.
예를 들어, 다음과 같은 관계를 갖는 그래프가 있다고 하자.
- 1 → 2, 3
- 2 → 4, 5
- 3 → 4
- 4 → 5
이때 진입 차수 배열 D는 다음과 같다.
- D[1] = 0
- D[2] = 1
- D[3] = 1
- D[4] = 2
- D[5] = 2
위상 정렬 단계
- ArrayList로 사이클이 없는 그래프를 표현한다.
- 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.
- 예를 들어, 선택된 1의 인접 리스트 연결값으로 2와 3이 있다면
1) 정렬 배열에 1을 추가
2) D[2] = D[2]-1;
D[3] = D[3]-1;
주의!
여기서 진입 차수가 0인 것들 중 어떤 것을 먼저 선택하느냐에 따라 정렬이 달라진다.
즉, 위상 정렬은 늘 같은 정렬 결과를 보장하지 않는다.
- 모든 노드가 정렬될 때까지 2번 과정을 반복한다.
- 정렬이 종료되면 진입 차수 배열은 모두 0이 된다.
Reference
[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런