위상 정렬(Topological Sort)

위상 정렬(Topological Sorting)

위상 정렬은 복잡한 작업들 사이의 순서를 정리하는 강력한 도구다. 이 알고리즘은 방향성 비순환 그래프(DAG, Directed Acyclic Graph)에서 작동한다. 여기서 '방향성'이란 작업들 사이에 명확한 선후관계가 있다는 뜻이고, '비순환'이란 어떤 작업도 자기 자신으로 돌아오는 순환고리에 갇히지 않는다는 의미이다. 

위상 정렬의 목표는 이러한 그래프의 모든 노드(작업들)를 일렬로 늘어세우는 것이다. 이때 중요한 점은 그래프의 방향, 즉 작업들 간의 선후관계를 어기지 않아야 한다는 것이다.  마치 도미노를 세우듯이, 각 작업은 자신에게 필요한 모든 선행 작업들이 완료된 후에야 수행될 수 있다. 

이 알고리즘의 핵심은 '선행 관계'를 철저히 지키는 데 있다. 실생활의 예를 들어보자. 대학에서 학생들이 수강 계획을 세울 때, 어떤 고급 과목을 듣기 위해서는 반드시 그 과목의 선수과목을 먼저 들어야 한다. 예를 들어, '고급 프로그래밍' 과목을 듣기 전에 '기초 프로그래밍'을 먼저 수강해야 하는 것과 같다. 

그래프로 표현하면, 각 과목은 하나의 노드가 되고, 선수과목 관계는 노드 사이의 화살표(간선)로 표현된다. 위상 정렬은 이런 관계를 모두 고려하여 과목들의 순서를 정렬한다. 만약 과목 A에서 과목 B로 향하는 화살표가 있다면, 정렬된 결과에서 A는 반드시 B보다 앞에 위치해야 한다. 

 

위상 정렬의 재미있는 특징 중 하나는, 하나의 그래프에 대해 여러 가지 유효한 정렬 결과가 나올 수 있다는 점이다. 이는 어떤 작업들 사이에 직접적인 선후관계가 없을 때 발생한다. 예를 들어, '기초 수학'과 '기초 물리'를 모두 들어야 '고급 공학'을 수강할 수 있다고 할 때, '기초 수학'과 '기초 물리' 사이의 순서는 어떻게 정하든 상관없다. 

그러나 주의할 점은 모든 그래프에 대해 위상 정렬이 가능한 것은 아니라는 것이다. 만약 그래프에 순환(cycle)이 존재한다면, 즉 어떤 작업이 직간접적으로 자기 자신의 선행 조건이 된다면, 위상 정렬은 불가능하다. 이는 "닭이 먼저냐, 달걀이 먼저냐"와 같은 딜레마를 만들어내기 때문이다. 

 

위상 정렬의 핵심 메커니즘

위상 정렬의 핵심 메커니즘은 "의존성 관계를 유지하면서 순서를 정하는 것"이다. 

 

위상 정렬을 구현하는 두 가지 방식

예제 그래프 

① 깊이 우선 탐색(DFS)을 이용한 방법 - 스택

def dfs_topological_sort(graph):
    # 방문한 노드를 추적하기 위한 집합
    visited = set()
    # 위상 정렬 결과를 저장할 스택
    stack = []

    def dfs(node):
        # 현재 노드를 방문 처리
        visited.add(node)
        
        # 현재 노드의 모든 이웃(의존하는 노드들)에 대해
        for neighbor in graph[node]:
            # 아직 방문하지 않은 이웃이라면
            if neighbor not in visited:
                # 재귀적으로 DFS 수행
                dfs(neighbor)
        
        # 현재 노드의 모든 이웃을 처리한 후, 스택에 현재 노드 추가
        # 이는 현재 노드가 의존하는 모든 노드들이 먼저 스택에 추가되었음을 보장함
        stack.append(node)

    # 그래프의 모든 노드에 대해
    for node in graph:
        # 아직 방문하지 않은 노드라면 DFS 수행
        if node not in visited:
            dfs(node)

    # 스택을 뒤집어 반환
    # DFS 특성상, 의존성이 없는 노드가 먼저 스택에 추가되므로 뒤집어야 올바른 위상 정렬 순서가 됨
    return stack[::-1]

# 사용 예시
graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['H', 'F'],
    'F': ['G'],
    'G': [],
    'H': []
}

# 위상 정렬 수행
result = dfs_topological_sort(graph)
print("위상 정렬 결과:", result)

# 결과 해석:
# 1. B와 A는 어떤 노드에도 의존하지 않으므로 먼저 나올 수 있음
# 2. C는 A와 B 다음에 나와야 함
# 3. D는 B 다음에 나와야 함
# 4. E는 C 다음에 나와야 함
# 5. F는 D와 E 다음에 나와야 함
# 6. G와 H는 마지막에 나와야 함 (G는 F 다음, H는 E 다음)
# 따라서 B, A, D, C, E, H, F, G 또는 이와 유사한 순서가 올바른 위상 정렬 결과임

 

② 진입차수(Indegree)를 이용한 방법 (Kahn's 알고리즘) - 큐

from collections import deque

def kahns_topological_sort(graph):
    # 각 노드의 진입차수(들어오는 간선의 수)를 계산
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    # 진입차수가 0인 노드를 큐에 삽입
    # 이 노드들은 어떤 노드에도 의존하지 않으므로 정렬의 시작점이 됨
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    result = []  # 위상 정렬 결과를 저장할 리스트

    while queue:
        # 큐에서 노드를 하나 꺼내어 결과 리스트에 추가
        node = queue.popleft()
        result.append(node)
        
        # 현재 노드에 의존하는 모든 이웃 노드들에 대해
        for neighbor in graph[node]:
            # 이웃 노드의 진입차수를 1 감소
            in_degree[neighbor] -= 1
            # 진입차수가 0이 되면 큐에 추가
            # 이는 해당 노드의 모든 의존성이 해결되었음을 의미
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # 모든 노드를 처리했는지 확인
    # 사이클이 있으면 모든 노드를 처리할 수 없음
    if len(result) != len(graph):
        return None  # 사이클이 존재하면 None 반환
    return result

# 사용 예시
graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['H', 'F'],
    'F': ['G'],
    'G': [],
    'H': []
}

# 위상 정렬 수행
result = kahns_topological_sort(graph)
print("위상 정렬 결과:", result)

# 결과 해석:
# 1. A와 B는 진입차수가 0이므로 먼저 처리될 수 있음
# 2. C는 A와 B가 처리된 후에 진입차수가 0이 되어 처리됨
# 3. D는 B가 처리된 후에 진입차수가 0이 되어 처리됨
# 4. E는 C가 처리된 후에 진입차수가 0이 되어 처리됨
# 5. F는 D와 E가 모두 처리된 후에 진입차수가 0이 되어 처리됨
# 6. G와 H는 각각 F와 E가 처리된 후에 진입차수가 0이 되어 처리됨
# 따라서 A, B, C, D, E, H, F, G 또는 이와 유사한 순서가 올바른 위상 정렬 결과임

 

DFS와 Kahn's 알고리즘 비교

참고 자료 

• [유튜브] 27강 - 위상 정렬(Topology Sort) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #27 ]
• [블로그] 25. 위상정렬(Topology Sort)