그래프 이론 - 6. 위상 정렬 (Topological Sorting)

 

6. 위상 정렬 (Topological Sorting)

6.1 위상 정렬이란?

📌 활용 사례 - 프로젝트 빌드 순서 (실제 사례 코드 추가)

소프트웨어 프로젝트에서는 컴파일해야 할 파일들이 서로 의존성을 가짐

• 예를 들어, main.o 파일을 빌드하기 위해 util.o, network.o를 먼저 빌드해야 함
• 소스 코드 파일 간의 의존성을 DAG로 표현하여 위상 정렬을 수행하면 올바른 빌드 순서를 결정할 수 있음

📌 프로젝트 의존성 그래프

  (compile util.c) → (util.o)
          ↓
  (compile main.c) → (main.o)
          ↓
  (link)

📌 프로젝트 빌드 순서 - 위상 정렬 코드 (Kahn’s Algorithm 활용)

from collections import deque

def build_project(tasks):
    in_degree = {task: 0 for task in tasks}
    for task in tasks:
        for dependency in tasks[task]:
            in_degree[dependency] += 1

    queue = deque([task for task in in_degree if in_degree[task] == 0])
    build_order = []

    while queue:
        task = queue.popleft()
        build_order.append(task)

        for dependency in tasks[task]:
            in_degree[dependency] -= 1
            if in_degree[dependency] == 0:
                queue.append(dependency)

    return build_order if len(build_order) == len(tasks) else "사이클이 존재함"

# 프로젝트 빌드 의존성 그래프
tasks = {
    "compile util.c": ["util.o"],
    "compile main.c": ["main.o"],
    "util.o": ["main.o"],
    "main.o": ["link"],
    "link": []
}

print("프로젝트 빌드 순서:", build_project(tasks))

📌 출력 결과:

프로젝트 빌드 순서: ['compile util.c', 'compile main.c', 'util.o', 'main.o', 'link']

---

6.2 더 복잡한 그래프 예제 추가

📌 확장된 DAG 예제

      (A)
     /   \
   (B)   (C)
    |  \  |  \
   (D)  (E)  (F)
    |   /    |
   (G)       (H)

📌 코드에서 더 복잡한 DAG 처리

graph_large = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['E', 'F'],
    'D': ['G'],
    'E': ['G'],
    'F': ['H'],
    'G': [],
    'H': []
}

print("확장된 DAG 위상 정렬 결과:", kahn_topological_sort(graph_large))

📌 출력 결과:

확장된 DAG 위상 정렬 결과: ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']

---

6.3 Kahn’s Algorithm vs DFS 성능 비교

import time
import random

# 대규모 DAG 생성 함수 (정점 N개, 간선 E개)
def generate_large_dag(N, E):
    graph = {str(i): [] for i in range(N)}
    edges = set()
    
    while len(edges) < E:
        u = random.randint(0, N-2)
        v = random.randint(u+1, N-1)  # 사이클 방지 (DAG)
        if (u, v) not in edges:
            graph[str(u)].append(str(v))
            edges.add((u, v))
    
    return graph

# 성능 테스트용 DAG 생성
N, E = 1000, 3000
large_dag = generate_large_dag(N, E)

# Kahn’s Algorithm 실행 시간 측정
start_time = time.time()
kahn_topological_sort(large_dag)
print(f"Kahn’s Algorithm 실행 시간: {time.time() - start_time:.6f}초")

# DFS 기반 위상 정렬 실행 시간 측정
start_time = time.time()
dfs_topological_sort(large_dag)
print(f"DFS 기반 위상 정렬 실행 시간: {time.time() - start_time:.6f}초")

📌 예상 출력 결과:

Kahn’s Algorithm 실행 시간: 0.015초
DFS 기반 위상 정렬 실행 시간: 0.018초

• 두 알고리즘의 시간 복잡도는 동일(𝑂(𝑁+𝐸))이지만, Kahn’s Algorithm이 큐(Queue)를 사용하므로 일반적으로 약간 더 빠름
• DFS 기반 위상 정렬은 재귀 호출이 많을 경우 오버헤드가 발생할 수 있음

---

📌 최종 비교표

알고리즘	방식	시간 복잡도	자료구조	장점	단점
Kahn’s Algorithm	진입 차수 기반	𝑂(𝑁+𝐸)	큐(Queue)	빠르고 사이클 감지 가능	추가적인 진입 차수 배열 필요
DFS 기반	DFS 역순	𝑂(𝑁+𝐸)	스택(Stack)	구현이 직관적	사이클 감지 어려움, 재귀 오버헤드 가능

📌 언제 Kahn’s Algorithm을 사용해야 하는가?

• 작업 스케줄링, 패키지 의존성 해결 등에서 적합
• 사이클이 있는지 확인해야 할 경우

📌 언제 DFS 기반 위상 정렬을 사용해야 하는가?

• 그래프 탐색을 주로 수행하는 경우
• 재귀적인 접근 방식이 필요한 경우