[Algorithm] 위상 정렬

* Python을 기준으로 합니다

---

위상 정렬 (Topology Sort)

- 개념

• 위상 정렬 : 방향 비순환 그래프 (Directed Acyclic Graph, DAG)의 모든 노드를 순서대로 나열하는 것
  • 진입차수 (Indegree) : 그래프에서 특정 노드를 가리키는 간선의 개수
  • 위상 정렬의 동작
    1. 진입차수가 0인 노드를 큐에 push
    2. 큐에서 노드를 pop 하면서, 인접 노드의 진입차수를 1씩 줄임
    3. 이후 진입차수가 0이 된 노드를 큐에 push
    4. 위 2~3번 과정을 큐가 빌 때까지 반복
  • 위상 정렬의 동작 과정에서 모든 노드들을 방문하기 전에 큐가 비어지면, cycle이 존재하는 것으로 볼 수 있음
    - Cycle이 존재하는 경우 어떠한 노드도 큐에 push 되지 못하기 때문
    - BUT, 일반적으로 위상 정렬은 DAG에서만 동작하는 경우를 고려함
  • $V$개의 노드, $E$개의 간선이 있는 DAG에서 위상 정렬을 수행했을 때, time complexity는 $O(V+E)$

위상 정렬 동작 예시 1

위상 정렬 동작 예시 2

- 구현

1. 위상 정렬의 구현

• 위상 정렬은 주로 큐를 활용하여 구현됨

import collections #큐 사용 위함

def topology_sort(graph, indegree):
  result = [] 
  queue = collections.deque() #큐 선언

  for i in range(1, 9+1): #노드개수+1 만큼 반복
    if indegree[i] == 0: #진입차수가 0이면
      queue.append(i) #큐에 push
  
  while queue: #큐가 빌 때까지 반복
    node = queue.popleft() #큐에서 pop하고
    result.append(node) #result에 추가
    for i in graph[node]: #pop한 노드의 인접 노드들에 대해
      indegree[i] -= 1 #진입차수 -1
      if indegree[i] == 0: #진입차수가 0인 노드가 있으면
        queue.append(i) #큐에 push

  return result

• 위상 정렬 결과 확인

#인접 리스트 형식 그래프 표현
graph = {
    1:[5],
    2:[4],
    3:[4],
    4:[5,6,7],
    5:[7,8],
    6:[7],
    7:[8,9],
    8:[9],
    9:[]
}

indegree = [0] * (9+1) #진입차수 0으로 초기화 (노드개수+1 만큼)

for cur, adj in graph.items(): #그래프의 각 노드들에 대해
  for node in adj:
    indegree[node] += 1 #진입차수 계산

print(indegree) #진입차수 배열 [0, 0, 0, 0, 2, 2, 1, 3, 2, 2] 
print(topology_sort(graph, indegree)) #위상 정렬 결과 [1, 2, 3, 4, 5, 6, 7, 8, 9]