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