[알고리즘] 위상 정렬

순환 그래프와 비순환 그래프

정점 간의 연결관계를 표현하는 그래프가 내부에 순환 구간을 가지고 있으면 순환 그래프, 그렇지 않다면 비순환 그래프라고 한다. 

 

2 -> 3 -> 5 -> 2 순환 구간이 존재하는 순환 그래프

비순환 그래프의 에시

 

 

 

DAG(Directed Acyclic Graph)

비순환 방향 그래프라고 부른다. 명칭에서 유추해볼 수 있듯이 간선이 방향성을 가지는 비순환 그래프를 의미한다. 따라서 어느 한 정점으로부터 간선을 따라 출발하면 다시 해당 정점으로 돌아오는 경로는 존재하지 않는다. 

 

Topological Sort

위상 정렬이라고 부르며, 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 정해주고자 할 때 사용하는 알고리즘이다. 주변에서 볼 수 있는 예시로는 대학교에서 커리큘럼대로 강의를 수강하거나, RPG 게임 속의 스킬트리대로 스킬을 찍는 경우이다. 스킬 트리의 각 스킬을 정점, 선행스킬과 다음 스킬간의 관계를 방향이 있는 간선으로 표현하면 비순환 방향 그래프(DAG)가 그려진다. 스킬 트리의 경우 선행 스킬을 먼저 익혀야 다음 스킬을 익힐 수 있고(방향성) 따라서 한정된 스킬포인트로 강한 캐릭터를 육성하기 위해서는 효율적인 스킬 트리(순서)를 따라야 한다. 

이런 특성을 갖고 있는 강의 커리큘럼이나 스킬 트리는 순서가 존재하기에 정렬을 할 수 있다. 위상 정렬을 통하여 그래프 의 정점을 정렬하여 하나의 위상 순서로 만들게 되면 모든 간선은 한쪽 방향만을 가리키게 된다. 

 

 

위상 정렬의 결과