알고리즘 7장
그래프 판정: 위상 정렬 검사(Kahn)
Kahn 알고리즘은 진입차수가 0인 정점을 큐에 넣고 간선을 제거하며 위상 순서를 만듭니다.
상태 변화
진입차수
A
0
B
1
C
2
D
1
queue A
→
remove A
→
B indegree 0
처리한 정점 수가 V보다 작으면 남은 정점이 사이클에 묶여 있습니다.
불변식
점검
indegree 0
먼저 처리 가능한 정점을 큐에 넣습니다.
pop
정점을 결과 순서에 추가합니다.
decrease
나가는 간선의 도착 정점 진입차수를 줄입니다.
사이클 점검
큐가 비었는데 처리 수가 V 미만이면 사이클입니다.