위상정렬1 [WEEK03] 위상정렬 Topology Sort 방향그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 특징 - 정렬 알고리즘의 일종으로 순서가 정해져 있는 일련의 작업을 차례대로 수행해야할 때 사용할 수 있는 알고리즘 - 예를 들면 '선수과목을 고려한 학습순서 설정'을 들 수 있음 - 진입차수 (indegree) ? 특정한 노드로 '들어오는' 간선의 개수 - 위상 정렬은 여러 개의 답이 존재할 수 있음 - DAG(Directed Acyclic Graph)에서만 적용 DAG? 사이클이 발생하지 않는 방향 그래프 - 위상정렬 알고리즘은 두가지 해결책을 낸다는 특징이 있음 1. 현재 그래프는 위상정렬이 가능한지 2. 위상정렬이 가능하다면 그 결과는 무엇인지 알고리즘 진행과정 1. 진입차수가 0인 노드를 큐에 넣.. 2022. 10. 13. 이전 1 다음
