10.1 Định nghĩa sắp xếp topo
Sắp xếp topo là việc sắp xếp tuyến tính các đỉnh của một đồ thị có hướng không chu trình (DAG) sao cho với mỗi cạnh (u, v), đỉnh u đứng trước đỉnh v. Điều này chỉ có thể thực hiện được với DAG và không áp dụng được trên các đồ thị có chu trình.
Định nghĩa thế nào? Nếu bạn hiểu ngay từ lần đầu, thì có lẽ bạn đã có nhiều kinh nghiệm làm việc với thuật toán.
Nói đơn giản là: bạn có một danh sách các nhiệm vụ (đỉnh của đồ thị) và một danh sách các phụ thuộc giữa chúng (mũi tên trong đồ thị). Hãy sắp xếp các nhiệm vụ (đỉnh) sao cho tất cả các nhiệm vụ mà "nhiệm vụ A" phụ thuộc vào được thực hiện trước nó. Nghe dễ hiểu ngay, chứ không phải là "sắp xếp tuyến tính các đỉnh của đồ thị có hướng không chu trình"...
Sắp xếp topo là một thuật toán rất quan trọng từ thực tế, do đó nó có tên riêng chứ không chỉ tên của tác giả. Hãy cùng tìm hiểu xem nó cần thiết ở đâu:
Ứng dụng:
1. Lên kế hoạch tác vụ (Task Scheduling):
Xác định thứ tự thực hiện các tác vụ phụ thuộc sao cho mỗi tác vụ được thực hiện sau khi tất cả các phụ thuộc của nó đã hoàn thành.
Ví dụ:
Lên kế hoạch dự án trong hệ thống quản lý dự án.
2. Biên dịch mã:
Xác định thứ tự biên dịch các module hoặc file mã nguồn mà phụ thuộc vào nhau.
Ví dụ:
Tối ưu hóa quá trình xây dựng phần mềm trong các hệ thống build (ví dụ, Makefile).
3. Giải quyết phụ thuộc trong trình quản lý gói:
Sắp xếp các gói sao cho tất cả các phụ thuộc được cài đặt trước khi cài đặt chính gói đó.
Ví dụ:
Đơn giản hóa quá trình cài đặt phần mềm trong các trình quản lý gói (ví dụ, npm, pip, apt).
4. Tối ưu hóa lộ trình:
Xác định thứ tự điểm đến hoặc hành động, có tính đến các phụ thuộc giữa chúng.
Ví dụ:
Logistics và lập kế hoạch lộ trình giao hàng.
Độ phức tạp thời gian và không gian của sắp xếp topo:
Độ phức tạp thời gian:
Cả hai thuật toán chính cho sắp xếp topo (DFS và thuật toán Kahn)
đều có độ phức tạp thời gian là O(V + E), trong đó V là số lượng đỉnh và E là số lượng cạnh trong đồ thị.
Độ phức tạp không gian:
Độ phức tạp không gian của cả hai thuật toán là O(V + E), vì
cần lưu trữ đồ thị và mảng để theo dõi các đỉnh đã được thăm và các tiền nhiệm.
10.2 Triển khai qua tìm kiếm theo chiều sâu (DFS)
Sắp xếp topo có thể thực hiện theo nhiều cách, một trong số đó dựa trên tìm kiếm theo chiều sâu — DFS. Thuật toán DFS cho sắp xếp topo sử dụng stack để theo dõi các nút đã hoàn thành.
Ví dụ triển khai:
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] # Kết quả theo thứ tự ngược lại
# Ví dụ sử dụng:
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_dfs(graph)
print("Sắp xếp topo:", result)
Đầu ra:
Sắp xếp topo: ['B', 'D', 'F', 'G', 'A', 'C', 'E', 'H']
10.3 Triển khai: thuật toán Kahn
Một cách tiếp cận khác gọi là thuật toán của Kahn (Kahn's Algorithm). Thuật toán Kahn cho sắp xếp topo sử dụng khái niệm bậc vào của các đỉnh.
Ví dụ triển khai:
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("Đồ thị chứa chu trình")
# Ví dụ sử dụng:
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_kahn(graph)
print("Sắp xếp topo:", result)
Đầu ra:
Sắp xếp topo: ['A', 'B', 'D', 'C', 'E', 'H', 'F', 'G']
GO TO FULL VERSION