Topological Sorting

위상 정렬이라고 불리는 Topological Sorting 에 대해 알아보려고 한다. 

Topological Sorting은 Directed Acyclic Graph (DAG)를 사용하여 Vertices를 순서 있게 나열하는 것이다. 

(즉, DAG 형태가 아니라면 해당 정렬은 사용할 수 없다.)

그림 1. DAG

그런데 기본 구조인 그래프의 특성상 정렬 방법은 여러개가 될 수 있다.

그림 1을 보면 (5, 4, 2, 3, 1, 0), (4, 5, 2, 3, 1, 0) 이렇게 2개가 될 수 있다. 이는 시작점은 항상 들어오는 부분이 없는 (in-degree가 0) 정점이 되어야 한다. 이를 바탕으로 그림 1을 보면 In-degree가 0인 부분은 2개(5, 4) 이다.

Topological Sorting의 구현은 DFS를 기반으로 변형한 것이다.

아래 코드를 확인해보자.

# A recursive function used by topologicalSort def topologicalSortUtil(self, v, visited, stack): # Mark the current node as visited. visited[v] = True # Recur for all the vertices adjacent to this vertex for i in self.graph[v]: if visited[i] == False: self.topologicalSortUtil(i, visited, stack) # Push current vertex to stack which stores result stack.insert(0, v) # The function to do Topological Sort. It uses recursive # topologicalSortUtil() def topologicalSort(self): # Mark all the vertices as not visited visited = [False] * self.V stack = [] # Call the recursive helper function to store Topological # Sort starting from all vertices one by one for i in range(self.V): if visited[i] == False: self.topologicalSortUtil(i, visited, stack) # Print contents of the stack print stack

해당 코드는 앞서 설명했듯이 DFS와 매우 유사하다. 

다만, 인접하는 정점을 재귀 호출 할 때 가장 마지막에 도착한 이후 스택에 쌓기 시작한다.

그런데 한 가지 생각해 볼 점은 해당 코드는 처음 정점이 스택의 처음에 올 수 있도록 만들었다. 스택의 LIFO의 특성을 가지고 있기 때문에 pop을 할 경우 가장 마지막 정점 부터 얻게 된다. 즉, 처음 정점을 찾기 위해서는 pop을 마지막까지 해야 한다. (물론 index 0으로 바로 찾을 수도 있지만..)

문제에 따라 조금씩 달라지긴 하겠지만 Topological Sorting의 기준을 어떻게 잡느냐에 따라 Stack의 위치도 그렇지 않으면 Queue 등등 다양한 방법이 있을 수 있다.

Topological Sorting는 보통 의존성 있는 상황에서 자주 사용되며 시간 복잡도는 O(V+E)이다. (+ 스택으로 인해 공간 복잡도가 더 추가 된다.)

Reference

- https://www.geeksforgeeks.org/topological-sorting/