언제 사용할까
서가 정해져 있는 작업들을 수행해야 할 때, 그 작업의 순서를 결정하는 데 사용됩니다. 즉, 방향 그래프(Directed Acyclic Graph, DAG) 에서 정점 간의 선후 관계를 파악하여 정렬하는 알고리즘입니다.
정의
-
방향 간선이 사이클을 이루면 정렬을 할 수 없다.(DAG여야 함)
방향 그래프(DAG: Directed Acyclic Graph) -
전형적으로 작업 스케줄링, 선행 관계가 있는 강의 듣기/ 과제 순서, 의존 관계가 있는 빌드 순서 등을 결정할 때 사용합니다.
진입 차수(In-degree)
진입 차수란 어떤 노드로 들어오는 직접적인 간선의 개수를 의미한다.
예를 들어 a -> b라는 방향 간선이 있으면,
이는 b로 가기 위해 거쳐야 하는 노드의 수, 혹은 b까지의 거리를 말하는 것이 아니라 b로 직접 들어오는 간선이 몇 개인지를 의미하는 것입니다.
진입 차수(In-degree): 해당 노드로 직접 들어오는 간선의 개수
진출 차수(Out-degree): 해당 노드에서 직접 나가는 간선의 개수
따라서, 진입 차수가 3이라면, 그 노드로 이어지는 직접 연결된 간선이 3개 존재한다는 뜻입니다.
Kahn 알고리즘에서 싸이클 찾기
-
모든 노드에 대해 진입 차수를 구한다.
-
진입 차수가 0인 노드를 큐에 넣는다.
-
큐가 빌 때 까지 과정을 반복한다.
-
만약 큐가 비었는데, 아직 방문하지 않은 노드가 남아있다면, 싸이클이 존재한다는 의미이다.
-
즉, 방문에 포함된 노드의 수가 전체 노드 수보다 작을 경우 사이클 때문에 진입 차수가 0이 되지 못한 노드들이 있다는 것을 의미한다.
