[Algorithm] 위상 정렬(Topology Sort)

위상 정렬(Topology Sort)이란?

위상 정렬이란 DAG에서 정점을 선형으로 정렬한 것이다. 이때 간선의 정보가 u -> v 형식으로 주어진다면, 위상 정렬의 결과는 항상 정점 u가 정점 v보다 앞에 오게 된다. 

DAG(Directed Acyclic Graph)
DAG는 비순환 방향 그래프를 의미하며, 사이클이 없고 간선에 방향이 존재하는 그래프를 의미한다. DAG가 아닌 그래프, 즉 간선에 방향이 없거나 사이클이 존재하는 그래프에 대해서는 위상 정렬이 불가능하다. 

위상 정렬을 활용하는 적절한 예시로 대학교 선수 과목을 들 수 있다. 다음 그림과 함께 살펴보자. 

위와 같이 선수 과목들이 정해져 있을 때, 자연어처리와 데이터베이스 시스템 과목을 수강하기 위해서 먼저 들어야 하는 과목을 순서대로 나열하면 다음과 같다. 

 

컴퓨터 프로그래밍 -> 자료구조 -> 알고리즘 -> 데이터베이스 -> 자연어처리 ->  데이터베이스 시스템

 

여기서 알고리즘과 데이터베이스, 자연어처리와 데이터베이스 시스템 간의 순서는 달라져도 상관이 없다. 이처럼 위상 정렬의 결과는 하나가 아니라 여러 가지가 나올 수도 있다. 

 

 

위상 정렬의 구현(Python)

먼저 모든 노드에 대해 들어오는 간선의 수를 저장하기 위해 indegree 배열을 활용한다. 이는 각 노드의 진입 차수를 저장한다.

기본적으로 위상 정렬은 Queue를 활용하여 구현한다. Stack을 사용해 구현하는 방식도 있지만 이번 포스팅에서는 Queue를 사용한 구현 방식을 다룬다. 

 

동작 방식은 아래와 같다. 

1. 모든 정점에 대해 진입차수 indegree[i]를 설정해 준다. 
2. 진입차수 초기화가 끝난 뒤 진입차수가 0인 노드들을 Queue에 추가해 준다. 
3. Queue에서 노드를 꺼내 결과에 저장하고, 그 노드와 인접한 노드들의 진입차수를 하나씩 줄인다. 
4. 만약 진입차수를 줄였을 때, 인접한 노드의 진입차수가 0이 되면 그 노드도 Queue에 추가해 준다. 
5. 3-4 과정을 Queue가 빌때까지 반복한다. 

이를 그림과 함께 살펴보면 아래와 같다. 

먼저 모든 노드의 진입 차수를 설정해주고, 진입 차수가 0인 노드들을 모두 Queue에 넣는다. 첫 번째로 검사할 원소는 1번 노드이다. Queue에서 꺼낸 노드를 result에 넣어주고, 인접한 노드를 검사한다. 인접한 노드인 2번, 4번, 5번 노드는 indegree가 1씩 줄게 된다. 

그림과 같이 인접한 노드들의 진입 차수가 줄게되는데, 이때 2번 노드와 4번 노드의 경우 진입 차수가 0이 되기 때문에 Queue에 삽입해 준다. 

다음으로 Queue에서 3번 노드를 꺼내 앞의 과정을 반복한다. 7번 노드의 진입 차수가 0이 되었으므로 Queue에 삽입해준다. 

 

다음은 2번 노드이다. 인접한 노드인 5번 노드의 진입 차수를 1 줄인다. 

다음으로 4번 노드를 꺼내 인접한 노드인 5번의 진입 차수를 줄인다. 이때 5번 노드의 진입 차수도 0이 되었으므로 Queue에 추가해 준다. 

 

이제 7번 노드를 꺼내 6번 노드의 진입 차수를 줄여준다. 

다음으로 5번 노드를 꺼내 인접한 노드인 6번 노드의 진입 차수를 줄인다. 이제 6번 노드도 진입 차수가 0이 되었으므로 Queue에 추가해준다. 

마지막 6번 노드의 경우 더이상 진행할 노드가 존재하지 않으므로 반복문이 종료된다. 

 

위의 과정을 코드로 구현하면 다음과 같다. 

from collections import deque

# 위상 정렬 함수 
def topology_sort(indegree, graph):
    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 i in graph[now]:
            indegree[i] -= 1
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입 
            if indegree[i] == 0:
                q.append(i)
    
    return result