Topological Sorting (1) 썸네일형 리스트형 123. Topological Sorting 위상 정렬(Topological Sorting)은 DAG의 정점을 재배열하는 알고리즘으로, 정점을 재배열했을 때 간선의 방향은 모두 동일해야 한다. 모든 DAG는 위상 정렬이 가능하며, DAG가 아닌 모든 그래프는 위상 정렬이 불가능하다. 위상 정렬을 하는 방법은 다음과 같다. 1. 아직 선택하지 않은 정점들 중 진입 차수가 $0$인 정점 하나를 선택하고 정렬된 정점 목록의 맨 뒤에 추가한다. 2. 선택한 정점 및 그 정점과 연결된 간선들을 그래프에서 제거한다. 3. 모든 정점이 선택될 때까지 과정 1, 2를 반복한다. 아래의 그래프에서 위상 정렬을 실행하면 다음과 같다. 진입 차수가 $0$인 정점은 $\text{D}$ 하나이므로 정점 $\text{D}$ 및 정점 $\text{D}$와 연결된 간선들을 그.. 이전 1 다음
