📚 Kahn 알고리즘

📚 Kahn 알고리즘

• 유향 그래프에서 위상 정렬(Topological sorting)을 수행하는 알고리즘 이다.

💡 TIP : 위상 정렬이란?

• 순서가 존재하는 작업들을 정렬하는 과정으로, 사이클이 없는 방향 비순환 그래프에서만 수행 가능하다.
• 예시로 선수 과목, 프로젝트 작업 순서, 패키지 의존성 해결 등등

🔎 Kahn 알고리즘 동작 원리

1. 진입 차수(in-degree)를 계산한다.
   • 진입 차수란 특정 노드로 들어오는 간선의 개수를 의미한다.
2. 진입 차수가 0인 노드를 큐(queue)에 삽입한다.
   • 진입 차수가 ‘0’이란 것은 선수 조건없이 시작할 수 있는 과목이라고 할 수 있다.
3. 큐에서 노드를 하나씩 꺼내며 위상 정렬을 수행한다.
   • 꺼낸 노드와 연결된 간선을 제거하고, 해당 노드에서 이동할 수 있는 노드들의 진입 차수를 1 감소시킨다.
   • 감소 후 진입 차수가 0이 된 노드는 큐에 삽입한다.
4. 모든 노드를 방문하면 정렬 완료!
   • 모든 노드를 방문하지 못하고 큐가 비어버린다면 사이클 이 존재하는 것이다.

🚀 Kahn 알고리즘을 활용한 Leecode 문제!!

• Course Schedule
• Course Schedule II

📊 시간 복잡도 계산

• degree 계산 : O(E)
• 큐에 삽입 및 제거 : O(V)
• 위상 정렬 수행 : O(V+E)

결과적으로 Kahn 알고리즘의 시간 복잡도는 O(V+E) (V : 노드 수, E : 간선 수)이다.

📌 Kahn 알고리즘의 특징

• 유향 비순환 그래프에서만 동작가능
• BFS기반으로 수행되며 진입 차수(in-degree)를 사용
• 사이클이 있는 경우 위상 정렬을 만들 수 없음 -> 이를 통해 사이클 검출 가능!!

• c
• graph
• topological-sorting
• bfs