算法訓練營day58 圖論⑧ 拓撲排序精講、dijkstra（樸素版）精講

? ? ? ? 本篇應該是圖論的經典部分了，本篇的內容作為小白沒有了解過，但是至少會聽說過——拓撲排序精講、dijkstra（樸素版）精講。

拓撲排序精講

????????本題是拓撲排序的經典題目。一聊到拓撲排序，一些錄友可能會想這是排序，不會想到這是圖論算法。其實拓撲排序是經典的圖論問題。

????????給出一個有向圖，把這個有向圖轉成線性的排序就叫拓撲排序。當然拓撲排序也要檢測這個有向圖是否有環，即存在循環依賴的情況，因為這種情況是不能做線性排序的。所以拓撲排序也是圖論中判斷有向無環圖的常用方法。

????????拓撲排序指的是一種解決問題的大體思路，而具體算法，可能是廣搜也可能是深搜。實現拓撲排序的算法有兩種：卡恩算法（BFS）和DFS。一般來說我們只需要掌握 BFS （廣度優先搜索）就可以了，清晰易懂，如果還想多了解一些，可以再去學一下 DFS 的思路，但 DFS 不是本篇重點。

????????當我們做拓撲排序的時候，應該優先找入度為 0 的節點，只有入度為0，它才是出發節點。?理解以上內容很重要！

????????接下來我給出拓撲排序的過程，其實就兩步：

找到入度為0 的節點，加入結果集
將該節點從圖中移除（從頭開始循環）

????????結果集的順序，就是我們想要的拓撲排序順序（結果集里順序可能不唯一）

判斷有環

????????那么如果我們發現結果集元素個數不等于圖中節點個數，我們就可以認定圖中一定有有向環！這也是拓撲排序判斷有向環的方法。

代碼實現

? ? ? ? 并不需要一定要把節點刪除，重點在于節點入度的判斷，只要相關節點入度-1即可，重點在于對于節點入度的處理，以及通過隊列結構對于節點的遍歷，類似我們之前做到過的二叉樹的層序遍歷

# 導入必要的模塊
# deque：用于實現隊列（高效的彈出左側元素操作）
# defaultdict：用于構建鄰接表（默認值為列表，簡化鍵不存在時的處理）
from collections import deque, defaultdictdef topological_sort(n, edges):"""拓撲排序函數：對有向無環圖(DAG)進行拓撲排序，常用于解決依賴關系問題（如文件依賴、任務調度）參數：n: 節點總數（如文件數量）edges: 邊的列表，每個元素為 tuple(s, t)，表示存在一條從 s 到 t 的有向邊（s 依賴 t 或 t 依賴 s，根據場景而定）功能：輸出拓撲排序結果；若圖中存在環，則輸出 -1"""# inDegree 數組：記錄每個節點的入度（即有多少個前置依賴）# 索引代表節點編號，值代表入度數量inDegree = [0] * n# umap：鄰接表，記錄節點間的依賴關系# key 是起始節點，value 是 key 指向的所有節點（列表）umap = defaultdict(list)# 構建圖（鄰接表）和入度表for s, t in edges:# s -> t 表示：要完成 t 必須先完成 s（或 t 依賴 s）# 因此 t 的入度 +1（增加一個前置依賴）inDegree[t] += 1# 在鄰接表中記錄 s 指向 t（s 完成后可處理 t）umap[s].append(t)# 初始化隊列：將所有入度為 0 的節點加入隊列# 入度為 0 表示該節點沒有前置依賴，可以直接開始處理queue = deque([i for i in range(n) if inDegree[i] == 0])# 存儲拓撲排序的結果result = []# 隊列不為空時，循環處理節點while queue:# 取出隊列左側的節點（當前可處理的節點）cur = queue.popleft()# 將當前節點加入結果列表result.append(cur)# 遍歷當前節點指向的所有節點（即依賴當前節點的節點）for file in umap[cur]:# 依賴當前節點的節點，其入度減 1（少了一個前置依賴）inDegree[file] -= 1# 若入度減為 0，說明該節點的所有前置依賴都已處理完，可加入隊列等待處理if inDegree[file] == 0:queue.append(file)# 若結果列表長度等于節點總數，說明所有節點都被處理（圖無環），輸出排序結果if len(result) == n:print(" ".join(map(str, result)))# 否則，說明圖中存在環（部分節點因入度無法減為 0 而未被處理），輸出 -1else:print(-1)if __name__ == "__main__":"""程序入口：讀取輸入并調用拓撲排序函數"""# 讀取節點總數 n 和邊數 mn, m = map(int, input().split())# 讀取 m 條邊，每條邊為 (s, t) 的元組edges = [tuple(map(int, input().split())) for _ in range(m)]# 執行拓撲排序topological_sort(n, edges)

dijkstra（樸素版）精講

????????dijkstra算法：在有權圖（權值非負數）中求從起點到其他節點的最短路徑算法。

????????需要注意兩點：

dijkstra 算法可以同時求起點到所有節點的最短路徑
權值不能為負數

?dijkstra三部曲：

第一步，選源點到哪個節點近且該節點未被訪問過
第二步，該最近節點被標記訪問過
第三步，更新非訪問節點到源點的距離（即更新minDist數組）

????????與prim算法基本一致，區別在于?dijkstra算法是一個積累的過程對數組賦值，而prim是當下節點的值沒有累加。即：prim是求非訪問節點到最小生成樹的最小距離，而 dijkstra是求非訪問節點到源點的最小距離。

????????prim算法可以有負權值嗎？當然可以！prim算法只需要將節點以最小權值和鏈接在一起，不涉及到單一路徑。

對于負值

? ? ? ? 該算法不能接受權值為負數（對應算法為Bellman-Ford 算法，后續講），因為權值存在負數會對節點循環造成影響，需要多次遍歷已經訪問過的節點（之前是每個節點只會遍歷一次），會造成循環結構的困擾

import sysdef dijkstra(n, m, edges, start, end):"""Dijkstra算法實現：求解從起點到終點的最短路徑參數:n: 節點總數m: 邊的數量edges: 邊的列表，每個元素為元組(p1, p2, val)，表示從p1到p2的有向邊，權重為valstart: 起點編號end: 終點編號返回:起點到終點的最短路徑長度；若無法到達，返回-1"""# 初始化鄰接矩陣，用于存儲節點間的距離# 初始值設為無窮大(float('inf'))，表示初始時節點間不可達# 矩陣大小為(n+1)x(n+1)，因為節點編號從1開始grid = [[float('inf')] * (n + 1) for _ in range(n + 1)]# 填充鄰接矩陣：根據邊的信息設置節點間的距離for p1, p2, val in edges:grid[p1][p2] = val  # 有向邊，僅設置p1到p2的距離# minDist數組：記錄從起點到每個節點的最短距離# 初始值設為無窮大，表示尚未確定距離minDist = [float('inf')] * (n + 1)# visited數組：標記節點是否已被訪問（即是否已確定最短路徑）visited = [False] * (n + 1)# 起點到自身的距離為0minDist[start] = 0# Dijkstra算法主循環：需要遍歷所有節點（最多n次）for _ in range(1, n + 1):# 1. 找到當前未訪問且距離起點最近的節點minVal = float('inf')  # 暫存當前最小距離cur = -1               # 暫存選中的節點# 遍歷所有節點，尋找符合條件的節點for v in range(1, n + 1):# 條件：未被訪問 且 距離起點更近if not visited[v] and minDist[v] < minVal:minVal = minDist[v]  # 更新最小距離cur = v              # 更新選中的節點# 如果找不到可訪問的節點（所有可達節點已處理），提前結束循環if cur == -1:break# 2. 標記當前節點為已訪問（其最短路徑已確定）visited[cur] = True# 3. 更新所有未訪問節點通過當前節點到達起點的距離for v in range(1, n + 1):# 條件：# - 節點v未被訪問# - 當前節點cur到v存在路徑（距離不為無窮大）# - 通過cur到達v的距離比當前已知距離更短if not visited[v] and grid[cur][v] != float('inf') and minDist[cur] + grid[cur][v] < minDist[v]:# 更新最短距離minDist[v] = minDist[cur] + grid[cur][v]# 返回結果：若終點不可達（距離仍為無窮大），返回-1；否則返回最短距離return -1 if minDist[end] == float('inf') else minDist[end]if __name__ == "__main__":"""程序入口：讀取輸入并調用Dijkstra算法計算結果"""# 一次性讀取所有輸入數據input = sys.stdin.readdata = input().split()  # 按空白字符分割成列表# 解析節點總數和邊數n, m = int(data[0]), int(data[1])# 解析所有邊的信息edges = []index = 2  # 從第三個元素開始是邊的信息for _ in range(m):p1 = int(data[index])p2 = int(data[index + 1])val = int(data[index + 2])edges.append((p1, p2, val))  # 將邊信息存入列表index += 3  # 移動到下一條邊的起始位置# 設定起點為1，終點為n（可根據實際需求修改）start = 1end = n# 調用Dijkstra算法計算最短路徑并輸出結果result = dijkstra(n, m, edges, start, end)print(result)