위상정렬 시각화
방향 비순환 그래프(DAG)에서 의존성 순서를 결정하는 칸(Kahn) 알고리즘을 학습합니다
그래프★★☆
속도
1 / 1처리 노드: 0큐 크기: 0
미처리 큐 대기 현재 처리 처리 완료
칸(Kahn) 알고리즘이 진입차수를 추적하며 위상 순서를 결정하는 과정을 관찰하세요.
칸(Kahn) 알고리즘이 진입차수를 추적하며 위상 순서를 결정하는 과정을 관찰하세요.
위상정렬이란?
위상정렬(Topological Sort)은 방향 비순환 그래프(DAG)의 모든 정점을 간선의 방향을 거스르지 않도록 나열하는 알고리즘입니다. 의존성이 있는 작업의 실행 순서를 결정할 때 사용됩니다. 칸(Kahn) 알고리즘은 진입차수(in-degree) 기반 BFS 방식으로 위상정렬을 수행합니다.
사용 방법
- 1새 DAG 버튼으로 랜덤 방향 비순환 그래프를 생성하세요
- 2각 노드 옆의 숫자(배지)는 진입차수(들어오는 간선 수)입니다
- 3진입차수가 0인 노드가 먼저 큐에 들어갑니다
- 4노드가 처리되면 나가는 간선이 제거되고, 이웃의 진입차수가 감소합니다
- 5노드 아래 초록 배지는 위상정렬 순서 번호입니다
학습 팁
- •위상정렬은 DAG에서만 가능합니다 — 순환이 있으면 불가능합니다
- •위상정렬 결과는 유일하지 않을 수 있습니다 (여러 정답 가능)
- •빌드 시스템(Make, Gradle)의 의존성 해결에 핵심적으로 사용됩니다
- •대학 수강 순서 결정, 프로젝트 일정 관리에도 활용됩니다
자주 묻는 질문
Q. DFS 기반 위상정렬과 칸 알고리즘의 차이점은?
A. 칸(Kahn): 진입차수 기반 BFS로, 순환 감지가 자연스럽습니다. DFS 기반: 후위 순회 역순으로, 별도 순환 감지(방문 상태 추적)가 필요합니다. 두 방법 모두 O(V+E) 시간 복잡도입니다.
Q. 위상정렬은 어디에 사용되나요?
A. 빌드 시스템의 컴파일 순서 결정, 패키지 매니저의 의존성 해결, 스프레드시트 셀 계산 순서, 대학 수강 선수과목 체크, 프로젝트 관리(PERT/CPM)에 사용됩니다.