『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
  • 1이 가리키고 있다.
• D[3] = 1
  • 1이 가리키고 있다.
• D[4] = 2
  • 2와 3이 가리키고 있다.
• D[5] = 2
  • 2와 4가 가리키고 있다.

위상 정렬 단계

1. ArrayList로 사이클이 없는 그래프를 표현한다.
   • 진입 차수 배열 D를 업데이트한다.
2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.
   • 예를 들어, 선택된 1의 인접 리스트 연결값으로 2와 3이 있다면
     1) 정렬 배열에 1을 추가
     2) D[2] = D[2]-1; D[3] = D[3]-1;

     주의!
     여기서 진입 차수가 0인 것들 중 어떤 것을 먼저 선택하느냐에 따라 정렬이 달라진다.
     즉, 위상 정렬은 늘 같은 정렬 결과를 보장하지 않는다.

3. 모든 노드가 정렬될 때까지 2번 과정을 반복한다.
   • 정렬이 종료되면 진입 차수 배열은 모두 0이 된다.

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런