10.1 위상 정렬의 정의
위상 정렬은 방향성 비순환 그래프(DAG)의 정점을 선형으로 정렬하는 것으로, 각 간선 (u, v)에서 정점 u가 정점 v에 앞서도록 하는 것입니다. 이 정렬은 DAG에 대해서만 가능하며, 순환이 있는 그래프에서는 수행할 수 없습니다.
정의가 어때? 처음에 이해했다면 아마 알고리즘에 대한 경험이 많은걸 거야.
쉽게 말하면 이렇지: 너한테는 작업 목록(그래프의 정점들)이 있고, 그들 사이의 의존성 목록(그래프의 화살표들)이 있어. 작업들(정점들)을 배치해서 '작업 A'에 의존하는 모든 작업들이 그것보다 먼저 실행되도록 해. 이제 이해됐지, "방향성 비순환 그래프의 정점의 선형적 정렬" 이런 말 대신에…
위상 정렬은 실무에서 매우 중요한 알고리즘이라서 그 자체로 이름이 있지, 그냥 저자의 이름이 아닌. 어디에 필요한지 알아보자:
적용 예시:
1. 작업 스케줄링(Task Scheduling):
의존적인 작업들이 각 작업의 모든 의존성이 완료된 후에 수행되도록 순서를 정하는 것.
예시:
프로젝트 관리 시스템에서의 프로젝트 계획.
2. 코드 컴파일:
서로 의존하는 모듈이나 소스 코드 파일의 컴파일 순서를 정하는 것.
예시:
빌드 시스템(예: Makefile)에서 소프트웨어 빌드 최적화.
3. 패키지 매니저에서의 의존성 해결:
패키지 설치 전에 모든 의존성이 해결되도록 패키지를 정렬하는 것.
예시:
패키지 매니저(npm, pip, apt 등)에서 소프트웨어 설치 과정의 간소화.
4. 경로 최적화:
의존성을 고려하여 포인트를 방문하거나 작업을 수행하는 순서를 정하는 것.
예시:
물류 및 상품 배달 루트의 계획.
위상 정렬의 시간 및 공간 복잡도:
시간 복잡도:
위상 정렬의 두 주요 알고리즘(DFS와 Kahn 알고리즘)은 시간 복잡도가 O(V + E)입니다. 여기서 V는 정점의 수, E는 그래프의 간선 수입니다.
공간 복잡도:
두 알고리즘 모두 그래프와 방문된 정점 및 선행자 추적을 위한 배열
저장이 필요하므로 공간 복잡도는 O(V + E)입니다.
10.2 깊이 우선 탐색(DFS)을 통한 구현
위상 정렬은 여러 방법으로 수행할 수 있으며, 그 중 하나는 깊이 우선 탐색(DFS)을 기반으로 합니다. 위상 정렬을 위한 DFS 알고리즘은 완료된 노드를 추적하기 위해 스택을 사용합니다.
구현 예시:
def topological_sort_dfs(graph):
def dfs(vertex, visited, stack):
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs(neighbor, visited, stack)
stack.append(vertex)
visited = set()
stack = []
for vertex in graph:
if vertex not in visited:
dfs(vertex, visited, stack)
return stack[::-1] # 결과를 역순으로 반환
# 사용 예시:
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_dfs(graph)
print("위상 정렬:", result)
결과:
위상 정렬: ['B', 'D', 'F', 'G', 'A', 'C', 'E', 'H']
10.3 구현: Kahn 알고리즘
또 다른 접근 방식은 Kahn 알고리즘이라고 불립니다. 위상 정렬을 위한 Kahn 알고리즘은 정점의 진입 차수 개념을 사용합니다.
구현 예시:
from collections import deque, defaultdict
def topological_sort_kahn(graph):
in_degree = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
in_degree[v] += 1
queue = deque([u for u in graph if in_degree[u] == 0])
top_order = []
while queue:
u = queue.popleft()
top_order.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(top_order) == len(in_degree):
return top_order
else:
raise ValueError("그래프에 순환이 있음")
# 사용 예시:
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_kahn(graph)
print("위상 정렬:", result)
결과:
위상 정렬: ['A', 'B', 'D', 'C', 'E', 'H', 'F', 'G']
GO TO FULL VERSION