위상정렬(Topologcal Sort)

위상 정렬(Topological Sort)란?

위상 정렬은

**유향 비순환 그래프(DAG, Directed Acyclic Graph)**에서

노드들을 선행 관계에 따라 순서대로 정렬하는 알고리즘입니다.

특징

1. 선행 관계를 보장:
   • 노드 A에서 B로 가는 간선이 있다면, 정렬 결과에서 A는 항상 B보다 먼저 나옵니다.
2. **DAG(Directed Acyclic Graph)**에서만 수행 가능:
   • 싸이클이 있는 그래프에서는 위상 정렬이 불가능합니다.

예제

• 입력 그래프:
  • 간선: [[1, 0], [2, 0], [3, 1], [3, 2]]
  • 설명: 0은 1과 2의 선행 조건이고, 1과 2는 3의 선행 조건입니다.
• 위상 정렬 결과:
  • 가능한 정렬: [0, 1, 2, 3] 또는 [0, 2, 1, 3]

---

위상 정렬 알고리즘

1. Kahn's Algorithm:
   • 진입 차수(Indegree)를 사용하여 정렬합니다.
   • 진입 차수가 0인 노드를 큐에 넣고,
   • 큐가 빌 때까지 반복합니다.
2. DFS 기반 알고리즘:
   • 방문하지 않은 노드에서 DFS를 수행하며,
   • 모든 후속 노드의 탐색이 끝난 후
   • 현재 노드를 결과 리스트에 추가합니다.
   • 리스트를 뒤집으면 위상 정렬 결과가 됩니다.