[D-14] 위상 정렬

📍 위상 정렬

✅ 정의

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

 

이미지 출처 : 나무위키, 위상정렬(https://namu.wiki/w/%EC%9C%84%EC%83%81%20%EC%A0%95%EB%A0%AC)

✅ 핵심 이론

항상 유일한 값으로 정렬되지 않는다.
사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.

 

✅ 정렬 원리

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

ArrayList로 표현한 그래프이다.
다음의 그래프는 사이클이 없는 상태이다.

 

진입 차수 배열 D를 업데이트한다.
다음은 1에서 2, 3을 가리키고 있으므로 D[2], D[3]을 각각 1만큼 증가시킨 배열의 결과이다.

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

진입 차수가 0인 노드 1을 선택하여 2, 3의 진입 차수를 1씩 빼 D[2], D[3]을 0으로 만든 것이다.

계속해서 다음 노드 2를 선택하여 반복한다.
이 과정은 모든 노드가 정렬될 때까지 반복한다.

위상 정렬 배열 결과는 다음과 같다.

여기서 진입 차수가 0인 노드를 3을 먼저 선택했다면 3이 우선 위상 정렬 배열에 들어갈 것이다.
앞서 위상 정렬이 늘 같은 정렬 결과를 보장하지 않는다고 말했던 것이 바로 이런 경우를 말한다.

---

 

✔️ 추가 참고 : 위상정렬(http://www.ktword.co.kr/index.php)

위상 정렬

 

✔️ 추가 참고 : 그래프 용어(http://www.ktword.co.kr/index.php)

 

그래프 용어