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