세상은 내가 정하는 대로 세상은 내가 정하는 대로

[Algorithms/python] 위상 정렬(Topological Sort) DAG : Directed Acyclic Graph 사이클이 없는 방향 그래프 → 일의 선후 관계 등을 표현할 때 사용하기 용이함 Topological Sort란 DAG에서 그래프의 방향성을 거스르지 않고 정점을 나열하는 정렬방법 Topological Sort의 방법 : 시간복잡도 : O(V+E) 그래프 그리기, 진입 차수 세기 가장 먼저 진입차수가 0인 노드들 queue에 넣기 queue를 돌며 해당 노드와 연결되어 있는 다른 노드들의 진입 차수를 하나씩 낮춰주고, 이 진입 차수가 0이 되었다면 또 queue에 삽입 Directed Acyclic Graph (DAG) : 순환(Cycle)을 가지지 않는 "방향" 그래프 위상 ..