위상정렬

위상정렬위상정렬(Topological Sorting)은 방향성 비순환 그래프(Directed Acyclic Graph, DAG)의 노드들을 선형으로 정렬하는 알고리즘입니다. 이 정렬은 그래프의 모든 간선이 방향성에 맞도록 순서대로 나열되도록 합니다.DAG = 사이클이 없는 방향 있는 그래프를 의미합니다. 선행그래프 구조를 가지고 있습니다.DAG 에서 할 수 있는 알고리즘은 위상정렬 알고리즘이 활용됩니다.  BFS 알고리즘을 응용해서 구현할 수 있습니다.위상정렬에서 주목해서 봐야할 것은 순서와 큐 입니다. 이 상태에서 인디그리가 0인 상태인 얘들을 큐에 넣어줍니다. 큐 : 1,2,3 이 존재하고 (왜냐하면 1,2,3 노드로 들어오는 화살표가 0) 여기서 하나씩 빼면서 BFS 과정을 거쳐주게 됩니다.순서 :..