11. [Algorithm] 위상 정렬 (그래프 이론)

위상 정렬 (Topological Sorting)

• 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.
• 조금 더 이론적인 설명은, 사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 을 의미한다.

 

예시를 통해 확실하게 이해해보도록 하자.

 

그림과 같이 총 3개의 과목이 있다고 가정하자.
세 과목을 모두 듣기 위해서는 자료구조 → 알고리즘 → 고급알고리즘 (O) 순서로 과목을 들어야 한다.
만약 자료구조 → 고급 알고리즘 → 알고리즘 (X) 순서로 과목을 듣게 되면, 올바른 학습순서가 아니다.

 

 

진입차수와 진출차수

위상 정렬 알고리즘을 살펴보기 위해서는 먼저 진입차수와  진출차수에 대한 개념을 알아야한다.

• 진입차수 (Indegree) : 특정한 노드로 들어오는 간선의 개수
• 진출차수 (Outdegree) : 특정한 노드에서 나가는 간선의 개수

 

---

위상 정렬 알고리즘 동작 과정

위상 정렬 알고리즘은 큐를 이용하여 구현한다. 위상 정렬 알고리즘은 다음과 같다.

1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
   2. 새롭게 진입차수가 0이 된 노드를 큐에 삽입

 

즉, 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과이다.

---

 

위 그림은 위상 정렬을 수행할 그래프이다.
이떄 위상 정렬을 수행할 수 있는 그래프는 사이클이 없는 방향 그래프(DAG)이어야 한다.

※Directed Acyclic Graph 는 방향성이 있는 비순환 그래프를 의미하며, 블록체인의 특성이기도 함.

 

• step 0 : 진입차수가 0인 모든 노드를 큐에 삽입. 현재 1번 노드의 진입차수만 0이므로 큐에 1번 노드만 삽입하게 된다.

step 0

 

• step 1 : 큐에 있는 1번 노드를 꺼낸다. 이후 1번 노드와 연결되어 있는 간선들을 제거한다. 그러면 2번 노드와 5번 노드의 진입차수가 0이 되고, 2번 노드와 5번 노드의 진입차수가 0이므로 큐에 삽입한다.

 

step1

 

• step 2 : 큐에 있는 2번 노드를 꺼낸다. 2번 노드와 연결되어 있는 간선들을 제거한다. 그러면 3번 노드의 진입차수가 0이 되므로 3번 노드를 큐에 삽입한다.

step 2

 

• step 3 : 큐에 있는 5번 노드를 꺼낸다. 5번 노드와 연결되어 있는 간선들을 제거한다. 그러면 6번 노드의 진입차수가 0이 되므로 6번 노드를 큐에 삽입한다.

step 3

 

• step 4 : 큐에 있는 3번 노드를 꺼낸다. 3번 노드와 연결되어 있는 간선들을 제거한다. 이번 단계에서는 새롭게 진입차수가 0이 되는 노드가 없으므로 넘어간다.

step 4

 

• step 5 : 큐에 있는 6번 노드를 꺼낸다. 6번 노드와 연결되어 있는 간선들을 제거한다. 그러면 4번 노드의 진입차수가 0이 되므로 4번 노드를 큐에 삽입한다.

step 5

 

• step ~ : 위와 동일한 로직으로 큐에 있는 노드를 꺼내고, 꺼낸 노드와 연결되어 있는 간선들을 제거한다. 새롭게 진입차수가 0이 되는 노드를 큐에 삽입한다.

 

[결과] 1 → 2 → 5 → 3 → 6 → 4 →7 

 

 

※ 위상 정렬의 답안은 여러가지가 될 수 있다는 점이 특징이다. 
따라서 1 → 5  → 2 → 3 → 6 → 4 → 7

 

---

위상 정렬의 특징

• 위상 정렬은 사이클이 없는 방향 그래프 (DAG)에 대해서만 수행할 수 있다.
  ※ DAG (Directed Acyclic Graph) : 순환하지 않는 (=사이클이 없는) 방향 그래프
• 위상 정렬에서는 여러 가지 답이 존재할 수 있다.  한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러 가지 답이 존재할 수 있다는 의미이다.
• 모든 원소를 방문하기 전에 큐가 비게 된다면 사이클이 존재한다고 판단할 수 있다. 왜냐하면 사이클에 포함된 원소 중에서 해당되는 어떠한 원소도  큐에 들어가지 못하게 되기 때문이다.
• 보통 큐로 구현하나, 스택을 이용한 DFS를 이용해 위상 정렬을 구현할 수도 있다.

 

위상 정렬 알고리즘 코드 (Python)

 

# 위상 정렬 함수
import sys
from collections import deque


def topology_sort():
    result = [] # 알고리즘 수행 결과를 담을 리스트
    q = deque() # 큐 기능을 위한 deque 라이브러리 사용

    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)

    # 큐가 빌 때까지 반복
    while q:
        # 큐에서 원소 꺼내기
        now = q.popleft()
        result.append(now)
        # 해당 원소와 연결된 노드들의 진입차수에서 1빼기
        for g in graph[now]:
            indegree[g] = indegree[g] - 1
            # 새롭게 진입 차수가 0이 되는 노드를 큐에 삽입
            if indegree[g] == 0:
                    q.append(g)

    # 위상 정렬을 수행한 결과 출력
    for i in result:
        print(i, end = ' ')



# 노드의 개수와 간선의 개수 입력
v, e = map(int, sys.stdin.readline().rstrip().split())

# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0 for i in range(v + 1)]

# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트
graph = [[] for i in range(v + 1)]

for i in range(e):
    # a 에서 b로 가는 간선
    a, b = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    indegree[b] = indegree[b] + 1   # a에서 b로 가는 간선이면 b의 진입차수가 +1 되기 때문.


topology_sort()


'''
입력 예시
7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4

출력 예시
1 2 5 3 6 4 7 
'''

 

시간 복잡도

• 시간 복잡도는 O(V+E)
  
  위상 정렬을 수행할 때는 차례대로 모든 노드를 확인하면서 (O(V)), 해당 노드에서 출발하는 간선을 차례대로 제거(O(E)) 해야 한다.
  따라서 노드와 간선을 모두 확인하는 것을 고려하여 O(V) + O(E) = O(V + E)의 시간이 소요된다.