DAG #위상정렬1 DAG, 위상정렬 Directed 방향 Acycllic 사이클이 없는 Graph 그래프 즉 DAG(사일클이 없는 방향 그래프)에서는 특수한 위상정렬이라는 알고리즘을 적용할 수 있습니다! 위상정렬은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 예를 들면, 1을 해야 4를 할 수 있다. 1과 2를 모두해야 4를 할 수 있다. 그렇다면 1 2 4 순으로 일을 해야 합니다. DAG에서 indegree가 0이 되어야 일을 할 수 있습니다. 그러므로 큐에 indegree가 0이 되는 정점을 push하면서 정렬을 진행합니다. bfs와 유사한 구조를 가져요 :) 들어오는 간선 : indegree 나오는 간선 : outdegree 문제를 풀면서 이해해 봅시다! 처음에는 들어오는 간선이 0인 정점을 큐에 넣고 시작합니다. 큐 : 1 2 3.. 2019. 6. 1. 이전 1 다음
