topological sort1 위상정렬(Topological sort) 위상정렬 - 위상정렬이란, 사이클이 없는 방향 그래프(DAG: Directed Acyclic Graph)에서 정점 사이의 선후 관계를 위배하지 않고 정렬하는 알고리즘이다. - 흔히 선수과목들의 수강 순서를 정하는 문제가 위상정렬에 비유된다. - 정해진 순서를 위배하지 않고 정렬하는 방법은 여러가지가 있을 수 있다. 위상정렬의 과정 N(노드의 개수) = 7, M(간선의 개수) = 7 인 다음과 같은 그래프에서 위상정렬을 수행해보자. 간선이 노드 x에서 노드 y로 흐를 때, 노드 x는 노드 y보다 앞에 위치되어야 한다. - 즉, 어떠한 노드가 해당 노드 쪽으로 들어오는 간선을 가지고 있다면 이 노드는 가장 앞에 올 수 없다. - 결과적으로, 현재 상태에서 가장 앞에 올 수 있는 노드들은 indegree(노드.. 2022. 3. 1. 이전 1 다음
