위상 정렬
•
위상 : 어떤 사물이 다른 사물과의 관계 속에서 가지는 위치나 상태
◦
그래프에서 위상 : 어떤 정점이 다른 정점과의 관계속에서 가지는 위치
◦
간선이 뻗어 나오는 정점이 앞이고 간선이 들어가는 정점이 뒤라면 이 앞/뒤 관계를 정렬하는 것이 위상 정렬
•
DAG, Directed Acyclic Graph
◦
그래프에 방향성이 있어서 정점의 앞/뒤 관계를 통해 위상을 표현할 수 있음
◦
그래프 내에 사이클이 있다면 시작과 끝을 정의할 수 없으므로 사이클이 없어야 함
◦
DAG란 비순환 방향 그래프로 그래프내에 사이클이 없으며 간선의 방향이 존재하는 그래프
◦
진입 간선 (Incoming Edge) : 정점으로 들어가는 간선
◦
진출 간선 (Outgoing Edge) : 정점으로 부터 나오는 간선
간단한 위상정렬 알고리즘
1.
리스트를 준비한다.
2.
그래프에서 진입 간선이 없는 정점을 리스트에 추가하고, 해당 정점 자신과 진출 간선을 제거한다.
3.
모든 정점에 대해 2번을 반복하고 그래프 내에 정점이 남아있지 않으면 정렬을 종료한다. 이때 리스트에는 위상 정렬된 그래프가 저장된다.
깊이 우선 탐색을 이용한 위상 정렬
1.
리스트를 준비한다.
2.
그래프에서 진입 간선이 없는 정점에 대해 깊이 우선 탐색을 시행하고, 탐색 중에 더이상 옮겨갈 수 없는 인접 정점이 없는 정점을 만나면(탐색중 가장 깊은 곳의 정점) 이 정점을 리스트의 새로운 Head 로 입력한다.
3.
2번을 반복하다 더 이상 방문할 정점이 없으면 깊이 우선 탐색을 종료한다. 깊이 우선 탐색이 끝난 후 리스트에는 위상 정렬된 그래프가 남는다.
