알고리즘/그래프
2020. 5. 10.
위상 정렬
위상 정렬(Topological sorting)은 유향 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것을 말합니다. 쉽게 말해서 간선 u→v가 있다면, 정점 v는 무조건 정점 u이후에 등장해야 합니다. 예를 들어 다음과 같은 유향 그래프에서, {1,5,2,3,6,4} 는 가능한 위상 정렬 중 하나입니다. 방향 그래프에 사이클이 존재한다면, 위상 정렬 역시 존재할 수 없습니다. 따라서 그래프는 항상 '사이클 없는 유향그래프'(Directed Acyclic Graph, DAG)여야 합니다. 그러면 위상 정렬을 구하는 알고리즘에 대해 알아봅시다. https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫..
