演算法 · 11 個細項
Graph Algorithms圖論演算法
圖能描述地圖、社交網路、任務相依關係等各種「東西之間有關聯」的問題。本主題從兩種基本走訪方式出發，再逐步進入環偵測、拓撲排序、各種最短路徑與最小生成樹。
前置知識QueueStack遞迴鄰接串列
為什麼要學 Graph Algorithms
現實中的應用細項
11 篇#演算法複雜度難度狀態
01BFS 廣度優先搜尋一層一層向外擴散，天生適合找無權圖最短路徑用在：最少步數、幾度人脈、爬蟲逐層抓取O(V+E)空間 O(V)可學習02DFS 深度優先搜尋一路走到底再回頭，是連通分量與拓撲排序的基礎用在：遍歷資料夾、油漆桶填色、偵測循環依賴O(V+E)空間 O(V)可學習03Grid as Graph 網格圖把二維陣列當圖，四方向就是邊用在：數島嶼、迷宮、影像連通區域O(mn)空間 O(mn)可學習04Cycle Detection 環偵測有向圖用三色標記，無向圖用併查集用在：循環依賴、死鎖偵測O(V+E)空間 O(V)可學習05Topological Sort 拓撲排序Kahn 的入度法與 DFS 完成順序法用在：套件安裝順序、課程先修、建置流程O(V+E)空間 O(V)可學習06Bipartite Check 二分圖判定兩色染色，相鄰不同色用在：配對問題、衝突分組O(V+E)空間 O(V)可學習07Dijkstra 單源最短路徑非負權重圖上，用優先佇列逐步確定最短距離用在：導航最快路線、網路路由O((V+E) log V)空間 O(V)可學習08Bellman-Ford 含負權最短路徑鬆弛 V−1 輪，第 V 輪還能鬆弛就有負環用在：匯率套利偵測、負權邊的路徑O(VE)空間 O(V)可學習09Floyd-Warshall 全點對最短路徑三層迴圈的 DP，適合稠密小圖用在：小型網路的路由表、任兩點距離查詢O(V³)空間 O(V²)可學習10Shortest Path in DAG DAG 最短路徑先拓撲排序再依序鬆弛，負權也可以用在：專案排程的關鍵路徑O(V+E)空間 O(V)可學習11MST: Kruskal & Prim 最小生成樹Kruskal 按邊排序加併查集，Prim 用堆積用在：鋪設電纜或光纖、叢集分析O(E log E)空間 O(V)可學習