728x90

목록topological sort (1)

728x90

내 세상

[Algorithms] Topological Sort, 위상정렬

Topological Sort - DAG(Directed Acyclic Graph)를 활용해 노드들 사이에 선후관계를 중심으로 정렬하는 알고리즘 - DFS(Depth-First Search, 깊이우선탐색) 사용 → 결과를 역으로 나타냈을 때 위상정렬 결과와 동일함. - '그래프'를 정렬하는 것으로 정렬 기준은 '진입 차수(해당 노드로 들어오는 간선의 개수)의 비 내림차순' 순서 - 진입차수가 0인 노드들 제거 - 진입차수가 0이 아닌 노드들은 점점 0으로 수정되며 제거 # 참고 : https://ratsgo.github.io/data%20structure&algorithm/2017/11/21/Topological/
Coding/Algorithms 2019. 4. 30. 23:40
이전 Prev 1 Next 다음