위상정렬 Topological Sort 개념 + 시간복잡도

Topological sort 위상정렬 알고리즘에 대해서 살펴보고 시간복잡도를 분석해보도록 하자. 

 

위상정렬 알고리즘이란 순서가 있는 알고리즘인데 쉽게 말해서, 만약 i와 j 사이에 간선이 있다면 i가 j보다 정렬 순서에서 먼저 와야 한다는 뜻이다. 

일상 생활에서도 위상정렬이 필요한 경우를 쉽게 생각해볼 수 있다. 

예를 들어, 일상생활에서 다음과 같이 5개 행동을 한다고 생각해보자. [물 끓이기, 요리하기, 음식먹기, TV 켜기, TV 보기] 그럴 때 물을 먼저 끓여야 요리를 할 수 있고 그래야 음식을 먹을 수 있다. 하지만 음식을 먹으면서 동시에 TV를 켜는 것은 가능하기 때문에 요리와 TV 사이의 순서는 정해져 있는 것이 없다. 하지만 TV를 켠 다음에야 TV를 볼 수 있으므로 아래와 같이 그래프가 만들어 질 것이다.

위에서 언급한 대로 간선이 있다는 것은 시작 노드의 행위가 끝 노드의 행위보다 먼저 일어나야 한다는 것이다. 

 

먼저 위상정렬의 방식을 간단히 설명한 뒤에 위 그림에 위상정렬을 적용해보겠다. 

 

vertex의 개수가 n개라고 했을 때 위상정렬의 pseudocode는 대략 아래와 같다.

 

for i<-1 to n {
   //진입 간선 없는 정점 u 선택
   A[i] = u 
   //u에서부터 시작되는 진출 간선 없앰

}

여기서 진입 간선이란 node로 들어오는 간선을 뜻하고 진출 간선이란 vertex에서부터 밖으로 나가는 간선을 뜻한다. 

즉, 진입 간선이 없는 정점을 택한다는 것은 해당 정점 전에 방문되어야 할 vertex들은 이미 방문되었거나 없다는 뜻이므로 먼저 순서에 정렬되어도 된다는 뜻이다. 그래서 진입 간선이 없는 vertex를 하나 고르고, 방문했다고 표시해주고, 방문한 vertex로부터 나가는 진출 간선을 다 없애주면 된다. 

 

예시로 이것이 무슨 말인지 더 자세히 알아보자.

 

먼저 위와 같은 상태에서부터 시작한다. 가장 먼저 해 주어야 할 일은 전입 간선이 하나도 없는 vertex를 고르는 것이다. 여기서는 물 끓이기와 TV 켜기가 전입 간선이 하나도 없으므로 둘 중에서 선택할 수 있다. 나는 물 끓이기를 선택해보겠다. 물 끓이기를 선택하면 물 끓이기에서 나가는 전출 간선을 모두 없애준다. 그래서 아래와 같은 상태로 변한다.

 

이제 다음으로 또 전입 간선이 없는 vertex를 찾아주었다. 이번에는 TV 켜기와 요리하기에 전입 간선이 하나도 없다. 이번에도 둘 중 하나를 마음대로 골라보자. 나는 TV 켜기를 골라보겠다. 그러면 아래와 같은 상태로 또 변할 것이다.

계속 이렇게 전입 간선이 0인 것을 찾는 과정을 반복해준다. 이번에는 요리하기를 골라보겠다. 

이제는 음식 먹기, TV 보기 모두 다 전입간선이 없으므로 순서대로 하나씩 제거해서 결국,

물 끓이기 => TV 켜기 => 요리하기 => TV 보기 => 음식 먹기

순서로 위상정렬을 끝내주었다. 

 

sorting 된 결과를 보면, 해야 하는 일의 순서를 정확히 만족시켜주었다는 것을 알 수 있다. 요리하기 전에 물을 끓여주었고 TV 보기 전에 TV를 켜 주었기 때문이다. 

---

이처럼 위상정렬은 이해하기 어려운 개념은 아니다. 그렇다면 위상정렬의 시간복잡도는 어떻게 될까? 

vertex의 개수를 V 개 , edge의 개수를 E개라고 했을 때 위상정렬은 Θ(|V| + |E|) 가 된다. 

 

그런데 여기서 한 가지 의문이 든다. 위상정렬의 경우 진입 간선이 0인 vertex를 매번 찾아주어야 하는데 어떻게 Θ(|V| + |E|)의 시간복잡도를 가지게 되는 것일까?

 

아래의 방식대로 조금만 수정을 해주면 된다.

먼저 위상정렬을 시작하기 전에 배열 count를 하나 만들어주고 count에 각 정점의 진입 간선의 개수를 적어주는 것이다. 모든 간선 (i, j)에 대해서 count[j]를 하나 증가시켜주면 된다. count[i]가 아닌 count[j]를 증가시켜주는 이유는 위상 정렬에서는 진출 간선의 개수보다 진입 간선의 개수가 더 중요하기 때문이다. 모든 간선에 대해 count의 값을 바꿔주게 되면 count라는 배열에는 각 정점의 진입 간선의 개수가 담겨있게 된다. 

 

이제 위상정렬은 진입 간선의 개수가 0인 정점을 찾아야 하므로 count 배열을 순회하면서 count의 개수가 0인 정점을 찾아주게 된다. 그리고 해당 정점에서 방문할 수 있는 정점이 v라고 했을 때 count[v]를 1 감소시켜준다. 이런 식으로 과정을 진행하면서 count[v]가 0이 된다면 진입 간선의 개수가 0인 리스트에 이를 넣어주게 된다. 

 

그러면 진입 간선의 개수가 0인 정점을 찾는 것을 상수 시간만에 진행할 수 있즈기 때문에 그 전에 일어났던 과정, 즉  Θ(|V| + |E|)라는 시간복잡도 내에서 해결 할 수 있는 것이다.