Directed Acyclic Graph

Algorithm

[Algorithm] 위상 정렬(Topology Sort)

위상 정렬(Topology Sort)이란? 위상 정렬이란 DAG에서 정점을 선형으로 정렬한 것이다. 이때 간선의 정보가 u -> v 형식으로 주어진다면, 위상 정렬의 결과는 항상 정점 u가 정점 v보다 앞에 오게 된다. DAG(Directed Acyclic Graph) DAG는 비순환 방향 그래프를 의미하며, 사이클이 없고 간선에 방향이 존재하는 그래프를 의미한다. DAG가 아닌 그래프, 즉 간선에 방향이 없거나 사이클이 존재하는 그래프에 대해서는 위상 정렬이 불가능하다. 위상 정렬을 활용하는 적절한 예시로 대학교 선수 과목을 들 수 있다. 다음 그림과 함께 살펴보자. 위와 같이 선수 과목들이 정해져 있을 때, 자연어처리와 데이터베이스 시스템 과목을 수강하기 위해서 먼저 들어야 하는 과목을 순서대로 나열..

hin1209
'Directed Acyclic Graph' 태그의 글 목록