위상 정렬
위상 정렬은 방향 간선 u→v가 있을 때 u가 v보다 앞서도록 정점을 선형 순서로 배치한다 그래프 알고리즘의 방향 비순환 그래프 순서화 분야에 속한다. 그래프의 정점·간선에 대한 관계를 계산하며, 간선의 방향·가중치와 허용하는 입력 구조에 따라 결과의 의미가 달라진다. 이 알고리즘의 전...
| 분류 | 알고리즘 · 그래프 알고리즘 · 방향 비순환 그래프 순서화 |
|---|---|
| 문제 | 방향 간선 u→v가 있을 때 u가 v보다 앞서도록 정점을 선형 순서로 배치한다 |
| 입력 | 방향 비순환 그래프(DAG)여야 하며 사이클 존재 시 모든 정점을 정렬할 수 없다 |
| 핵심 단계 | Kahn 방식은 진입 차수가 0인 정점을 큐에서 제거하며 순서를 구성한다 |
| 시간 복잡도 | O(V+E) |
| 공간·구현 | 시간 O(V+E), 공간 O(V) |
| 관련 분야 | 그래프, 자료구조 |
| 참고 문헌 | MIT Algorithms |
위상 정렬은 방향 간선 u→v가 있을 때 u가 v보다 앞서도록 정점을 선형 순서로 배치한다 그래프 알고리즘의 방향 비순환 그래프 순서화 분야에 속한다. 그래프의 정점·간선에 대한 관계를 계산하며, 간선의 방향·가중치와 허용하는 입력 구조에 따라 결과의 의미가 달라진다. 이 알고리즘의 전제는 방향 비순환 그래프(DAG)여야 하며 사이클 존재 시 모든 정점을 정렬할 수 없다.[1]
핵심 절차는 Kahn 방식은 진입 차수가 0인 정점을 큐에서 제거하며 순서를 구성한다. DFS 방식은 종료 순서를 역전해 위상 순서를 얻을 수 있다. 구현에서는 각 정점 또는 간선에 기록된 상태가 어떤 의미를 갖는지 불변식을 정의하고, 탐색·갱신 과정에서 해당 상태를 일관되게 유지해야 한다.
계산 비용은 시간 O(V+E), 공간 O(V) 정점 수를 V, 간선 수를 E라고 나타낼 때 O(V+E)의 시간 특성을 가진다. 저장 공간은 그래프의 표현 방식, 큐·스택·우선순위 큐 및 결과 배열의 선택에 영향을 받으므로 실제 적용 시 구현 구조를 함께 분석한다.
빌드 의존성·작업 스케줄과 강의 선수 조건을 정리한다. 여러 유효한 위상 순서가 존재할 수 있다. 대표적인 변형 알고리즘 및 자료구조의 선택은 결과의 최적성, 음수 가중치나 사이클의 허용 여부, 희소·밀집 그래프 여부에 따라 달라진다. 동점 처리와 비연결 그래프 등의 경계 사례까지 정의해야 구현 결과가 명확해진다.[2]