데브카이브 데브카이브

위상 정렬 알고리즘 위상 정렬(Topology Sort)은 순서가 있는 작업을 차례대로 수행해야 할 때 사용하는 알고리즘이다. 위상 정렬을 하기 위해서는 사이클이 없는 방향 그래프 DAG(Directed Acyclic Graph)이여야 한다. 위상정렬은 큐와 각 노드의 진입차수(Indegree)를 이용하여 구현할 수 있다. 1. 각 Node 별로 Indegree를 구해준다. 2. Indegree가 0인 Node를 Queue에 넣어준다. 3. Queue에서 Node를 가져와 해당 Node에서 방문 가능한 Node의 Indegree를 감소시킨다. 4. 감소된 Node의 Indegree가 0 이라면 Queue에 넣어준다. 5. Queue가 빌때까지 3,4 작업을 반복한다. 위와같은 순서로 동작한다면 Queue..