위상 정렬(Topological Sort)

위상 정렬(topological sort)은 G가 간선 (u,v)를 가질 때 u가 v보다 순서상으로 먼저 나타나도록 모든 정점을 선형으로 나열하는 것이다. 여기서 만약 그래프가 순환을 가진다면 선형 나열은 불가능하다.

 

아래와 같은 알고리즘은 하나의 방향 비순환 그래프를 위상 정렬 한다.

 

위상 정렬(G)

1 각 정점 v에 대해 종료 시간 v.f를 계산하기 위해 DFS(G)를 호출한다.

2 각 정점이 종료될 때마다 연결 리스트의 맨 앞에 삽입한다.

3 return 정점의 연결 리스트

 

그림 1. INTRODUCTION TO ALOGORITHM 의 위상 정렬 파트에 나오는 그림. a를 위상 정렬하여 b를 나타낼 수 있다.

중요한것은 위상 정렬한 순서대로 일을 수행할 때 일을 수행하지 못하는 일이 나오지 않는다는 것이다.

미리 어떠한 행동 A를 해야 B를 할 수 있다면 A를 하고 B를 해야한다는 것이다.

 

위 방식으로 위상 정렬을 할 때 시간복잡도는 Θ(V+E)이다.

 

Reference

INTRODUCTION TO ALGORITHM 3rd Edtion