위상 정렬 (Topological Sort)

위상 정렬은 사이클이 없는 방향 그래프 (Directed Acyclic Graph, DAG) 에서 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 정렬을 말합니다. 즉, 시작점이 존재하는 방향 그래프에서 순서를 거스르지 않고 정점을 나열하는 것입니다.

위상 정렬을 위해서는 진입차수 (In degree) 와 진출차수 (Out degree) 를 알아야 합니다. 그래프는 정점과 간선 정보로 존재하는데, 진입차수란 특정한 노드로 들어오는 간선의 개수, 진출차수는 특정한 노드에서 나가는 간선의 개수입니다. 

위상 정렬은 진입차수가 0인 정점 (시작점)을 먼저 배치하고, 그 정점에서 나가는 간선들을 제거합니다. 그 후, 다음 진입차수가 0인 정점을 배치합니다.

위상 정렬은 큐나 스택을 이용해 구현할 수 있습니다. 다음 그래프를 통해 큐를 이용한 위상 정렬을 살펴보도록 하겠습니다.

EXAMPLE

< STEP 1 >

맨 처음 단계에서는 진입 차수가 0인 (시작점) 모든 노드를 큐에 넣습니다. 

노드	1	2	3	4	5	6	7
진입차수	0	1	1	2	1	2	1
큐	1

 

< STEP 2 >

큐에서 원소를 꺼내 해당 노드에서 나가는 간선들을 제거합니다. 다음 진입 차수가 0인 노드 (2, 5)를 큐에 넣습니다. 노드의 개수가 2개 이상이므로 어떤 순서로 넣든지 상관 없습니다. (따라서 위상 정렬은 하나의 그래프에 대해 여러 정렬 결과가 생길 수 있습니다.) 

노드	1	2	3	4	5	6	7
진입차수	0	0	1	2	0	2	1
큐	2, 5

 

< STEP 3>

마찬가지로 큐에서 원소를 꺼내 (2) 해당 노드에서 나가는 간선들을 (3, 6) 제거합니다. 다음 진입 차수가 0인 노드를 큐에 추가합니다.

노드	1	2	3	4	5	6	7
진입차수	0	0	0	2	0	1	1
큐	5, 3

 

< STEP 4>

위 과정을 큐에 원소가 없을 때까지 반복합니다. 이렇게 위상 정렬을 수행한 결과는 큐에 삽입된 순서가 되어 1 -> 2 -> 5 -> 3 -> 6 -> 4 -> 7 이 됩니다.

 

스택을 이용한 위상 정렬

스택을 이용한 위상 정렬도 큐와 매우 비슷합니다. 진입차수가 0인 노드를 큐가 아닌 스택에 넣고 알고리즘을 진행하는 것이 큰 차이점입니다. 스택을 이용한 위상 정렬은 다음과 같이 동작합니다.

1. 진입차수가 0인 노드를 스택에 넣습니다. 
2. 스택에서 원소를 추출 (마지막 원소)하면서 그 원소와 연결된 간선을 제거합니다.
3. 간선 제거 후 진입차수가 0인 노드를 스택에 넣습니다.
4. 이 과정을 스택에 원소가 빌 때까지 수행합니다.

 

파이썬 코드

위의 예제에 대해 구현한 코드는 다음과 같습니다.

from collections import defaultdict, deque

N = 7
edges = [(1,2), (1,5), (2,3), (2,6), (3,4), (6,4), (4,7)]

## 그래프 정보 및 진입차수 테이블 초기화
graph = defaultdict(list)
indegree = defaultdict(int)
for edge in edges:
    v, w = edge # v 는 시작점 w 는 끝점
    graph[v].append(w) # w를 v의 이웃에 추가
    indegree[w] += 1 # w의 진입차수 증가
    
## 큐를 이용한 위상 정렬
def queue_topology_sort():
    result = [] # 결과를 담을 배열
    queue = deque()
    ## 진입 차수가 0인 것을 큐에 삽입
    for ind in indegree.keys():
        if indegree[ind] == 0:
            queue.append(ind)
            
    ## 큐가 빌 때까지 반복
    while queue:
        node = queue.popleft() # 큐에서 원소 추출
        result.append(node) # 결과에 원소 추가
        for neighbor in graph[node]: 
            indegree[neighbor] -= 1 # 간선 제거했으므로 진입차수 감소
            if indegree[neighbor] == 0: # 진입 차수가 0인 노드 큐에 추가
                queue.append(neighbor)
  
  	return result
    
## 스택을 이용한 위상 정렬
def stack_topology_sort():
    result = [] # 결과를 담을 배열
    stack = [] # 스택
    ## 진입 차수가 0인 것을 스택에 삽입
    for ind in indegree.keys():
        if indegree[ind] == 0:
            stack.append(ind)
            
    ## 스택이 빌 때까지 반복
    while stack:
        node = stack.pop() # 스택에서 원소 추출
        result.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1 # 간선 제거했으므로 진입차수 감소
            if indegree[neighbor] == 0: # 진입 차수가 0인 노드 스택에 추가
                stack.append(neighbor)
                
    return result
    

주목할 점은 만약 모든 원소를 방문하기 전에 큐나 스택이 비어있다면 사이클이 존재한다고 판단할 수 있는 점입니다. 사이클이 존재할 경우 사이클에 해당하는 정점의 진입차수는 1 이상이므로 큐나 스택에 들어갈 수 없습니다. 

 

홍머스 정리

• 사이클이 없는 방향 그래프에 대해 방향성을 고려한 노드 정렬
• 큐나 스택으로 구현 가능

참조

• velog.io/@piopiop/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%ACTopology-Sort-%ED%8C%8C%EC%9D%B4%EC%8D%AC
• www.youtube.com/watch?v=xeSz3pROPS8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=37