위상정렬

위상 정렬은 방향성 있는 비순환 그래프(Directed Acyclic Graph, DAG)의 노드들을 정렬하는 알고리즘으로, 모든 간선 (u, v)에 대해 노드 u가 항상 노드 v보다 앞에 오도록 정렬합니다. 위상 정렬은 주로 작업 스케줄링, 컴파일러에서의 종속성 해결 등에 사용

---

위상 정렬의 기본 원리

위상 정렬은 주어진 그래프의 방향성을 유지하며 순서를 찾습니다. 정렬 결과가 여러개일 수 있습니다.

방향성이 없거나 순환이 있는 그래프에서는 적용할 수 없습니다.

위상 정렬 구현 단계

다음은 위상 정렬을 구현하기 위한 주요 단계입니다:

1. 진입 차수 배열 생성

   • 각 노드의 진입 차수를 저장하는 배열(또는 딕셔너리)을 만듭니다.
   • 진입 차수는 해당 노드로 들어오는 간선의 개수입니다.

2. 진입 차수가 0인 노드 찾기

   • 초기 상태에서 진입 차수가 0인 모든 노드를 찾아 큐에 추가합니다.

3. 큐에서 노드 처리

   • 큐에서 노드를 하나씩 꺼내 위상 정렬 리스트에 추가합니다.
   • 해당 노드와 연결된 간선을 제거하며, 연결된 노드들의 진입 차수를 1씩 감소시킵니다.

4. 진입 차수가 0이 된 노드 추가

   • 간선을 제거한 결과, 진입 차수가 0이 된 노드들을 큐에 추가합니다.

5. 큐가 빌 때까지 반복

   • 큐가 빌 때까지 3~4 단계를 반복합니다.

6. 결과 확인

   • 위상 정렬 리스트의 노드 개수가 그래프의 노드 개수와 같으면 정렬이 성공적으로 완료된 것입니다.
   • 만약 정렬 리스트에 모든 노드가 포함되지 않았다면, 그래프에 사이클이 존재하여 위상 정렬이 불가능합니다.