201225 개발일지(18일차) - 순서를 구하는 알고리즘 위상 정렬(Topology Sort)

위상 정렬이란?

• 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. (출처 : 위키백과)
• 위상 정렬은 정렬 알고리즘의 일종으로, 방향 그래프의 모든 노드를 '방향성에 거스리지 않도록 순서대로 나열하는 것'이다. 즉, 순서가 정해져 있는 일련의 작업들을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. (출처 : 이것이 취업을 위한 코딩테스트다(with 파이썬))

위상 정렬의 조건

위의 내용을 보아 추측할 수 있겠지만, 아래 2가지 조건을 꼭 만족하는 그래프여야만 한다.
1. 간선이 방향성을 가지는, 유향 그래프여야 한다.
2. 그래프 내부에 순환(Cycle)이 없어야 한다.

※ 그래프 내부 순환이 있으면 어떻게 될까?
  → 시작부터 할 수 없다. 진입 차수가 0인 것

진입 차수(In-degree)

위상 정렬의 기본 아이디어를 이해하기 위해 진입 차수 개념을 짚고 가야 한다. 간단한 말로 한 정점으로 들어오는 간선의 갯수가 진입 차수이다.
아래 그림과 표를 확인하자.
(출처 : https://sexy-developer.tistory.com/56)

위상 정렬 구현하기

큐 개념을 활용하여 아래와 같은 알고리즘 순서로 구현하면 된다.

(+ DFS를 활용한 방법도 있는데, DFS함수가 종료될 때 기록된 순서를 뒤집으면 위상정렬 결과와 같다.)

1. n개의 노드(node)로 이루어진 그래프에서 각 노드의 진입 차수(in-degree)를 계산한다.
2. Indegree 가 0인 정점을 Queue에 넣는다.
3. Queue의 정점이 다 사라질 때까지 아래의 루프를 수행한다.

   1) Queue 에서 정점 하나를 뽑는다.
   2) 해당 정점에서 나가는 간선을 제거한다. (Indegree 업데이트)
   3) 업데이트 된 Indegree 가 0인 정점을 Queue에 추가한다.

이 그림을 토대로 위성 정렬을 구현해보았다.

import queue

# 그래프의 인접 행렬
graph = {0: [2,3], 1: [3,4], 2: [3, 5], 3: [5], 4:[5], 5:[]}

def topology_sort_queue(graph):
    N = len(graph)
    sort_queue = queue.Queue() # 큐
    degree = [0 for _ in range(N)] # 진입차수 리스트

    for nodes in graph:
        for j in graph[nodes]:
            degree[j] += 1
    #print("진입차수 리스트 : ", degree)

    for i in range(N):
        if degree[i] == 0: sort_queue.put(i)

    answer = []
    while not sort_queue.empty():
        current = sort_queue.get()
        answer.append(current)
        for i in graph[current]:
            degree[i] -= 1
            if degree[i] == 0 : sort_queue.put(i)
    print("최종 답 : ", answer)

topology_sort_queue(graph)

출력값
>>> 최종 답 :  [0, 1, 2, 4, 3, 5]