칸 알고리즘

칸 알고리즘(Kahn's algorithm)

위상 정렬(topological sort)을 수행하는 알고리즘 중 하나라고 한다.
여기에서 위상 정렬이란, 방향 그래프에서 모든 정점을 방향성에 거스르지 않도록 순서대로 나열하는 정렬 방법이다.
즉, 우선 순위가 있는 그래프에서 순서에 맞게 모든 노드를 정렬하는 방식이다.

동작 방식

1. 모든 정점의 진입 차수(in-degree)를 계산한다.
   진입 차수란 해당 정점으로 들어오는 간선의 개수이다.
2. 진입 차수가 0인 모든 정점을 큐에 넣는다.
3. 큐에서 정점을 꺼내고, 해당 정점과 연결된 모든 간선을 제거한다.
4. 간선 제거 이후 진입 차수가 0이 된 정점을 큐에 넣는다.
5. 큐가 빌 때까지 3~4 과정을 반복한다.

알고리즘이 종료되어 큐에서 꺼낸 정점 순서가 정렬된 결과이다. 만약 그래프에 사이클이 있다면, 위상 정렬이 불가능하기 때문에 알고리즘이 종료되기 전에 큐가 빈다는 것을 생각할 수 있다.

그렇기 때문에 위상 정렬은 DAG(Directed Acyclic Graph, 사이클이 없는 유향 그래프)에서만 사용이 가능하다. 만약 그래프에 사이클이 존재한다면 위상 정렬을 수행할 수 없다고 한다.
이를 검출하는 알고리즘은 탐색을 이용한다고 하는데, 대표적으로 DFS(Depth-First Search)를 이용하는 Tarjan 알고리즘이 있다고 한다.

시간 복잡도

칸 알고리즘은 O(V+E)의 시간 복잡도를 가지고 있다.