Algorithm

알고리즘 - 위상 정렬

안중환 2015. 11. 14. 17:55

- topological sort

- 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

- 진입 차수가 0인 정점을 선택하고, 선택된 정점과 여기에 부속된 모든 간선을 삭제 -> 반복

- 사이클이 있는 경우 위상정렬 불가