[알고리즘] 위상정렬(Topological Sort)

위상이란??

출처 : https://ko.dict.naver.com/#/entry/koko/0718e64ba31b4aba99b7488ee95b2f7e

 

즉, 어떤 정점이 다른 사물과의 관계 속에서 가지는 위치나 상태를 말한다.

 

그래프안에서 인접해 있는 정점 사이의 관계의 '위치'라는 속성이 존재. 그러므로 위상 정렬이 가능하려면, 첫째로 그래프에 방향성이 있어야하고, 둘째로는 그래프내에 사이클이 있어야한다. 이러한 그래프를 DAG(Directed Acyclic Graph)라고 한다.

 

DAG 그래프 예

참고 : https://www.steemcoinpan.com/sct/@dakeshi/master-of-obyte-dag-middlemen

 

 

 

위상정렬은 두 정점이 이웃 또는 인접관계에 있다는 사실뿐만 아니라 간선이 방향성을 가지는 경우에는 어느 정점이 선이고 어느 정점이 후인지도 설명합니다.

정점은 두 가지 종류의 방향성 간선을 가질 수 있는데 그중 하나는 정점으로 들어가는 진입간선과 다른 하나는 진출 간선입니다.

 

1. 리스트 하나를 준비

2. 그래프에서 진입 간선이 없는 정점을 리스트에 추가, 해당 정점 자신과 진출 간선을 제거.

3. 모든 정점에 대해 2를 반복하고 그래프내에 장점이 남아 있지 않으면 정렬을 종료한다. 이때 리스트에는 위상 정렬된 그래프가 저장.

 

이런식으로 진행한다. 하지만 더 유용한 방법은 깊이우선탐색(DFS)와 함께 사용하는것이다.

 

1. 리스트를 하나 준비

2. 그래프에서 진입 간선이 없는 정점에 대해 깊이 우선 탐색을 시행하고, 탐색 중에 더 이상 옮겨갈 수 있는 인접 정점이 없는 정점을 만나면 이 정점을 리스트의 새로운 '헤드'로 입력합니다.

3. 2번을 반복하다가 더 이상 방문할 정점이 없으면 깊이 우선 탐색을 종료. 깊이 우선 탐색이 끝난 후 리스트에는 위상정렬된 그래프가 저장.