위상정렬
-
[알고리즘] TopologicalSoring (위상정렬)SW/Algorithm 2018. 1. 1. 20:30
위상정렬 (topological sorting) 방향 그래프에 존재하는 각 정점들의 선행 순서를 위해하지 않으면서 모든 정점을 나열하는 것. 진입 차수 0인 정점(들어오지않는)을 선택하고 선택된 정점과 여기에 부속된 모든 간선을 삭제한다. 반복해서 모든 정점이 선택,삭제되면 알고리즘을 종료. 이 과정에서 선택되는 정점의 순서를 위상순서(topological order)라 한다.example 진입 차수가 없는 0,1 선택가능. 후보: 0,1 (여기선 1 선택) (스택사용) 1에서 뻗는 간선들 삭제.(그러면 4에 들어오는 차수 0) 후보: 0,4 (4 선택) 4에서 뻗는 간선(4->5)삭제. (5는 들어오는 다른 간선이 있기 때문에 후보X) 후보: 0 (0 선택) 반복... 위상 순서: 1 4 0 2 3 5..