鐵人檔案
圖論的應用層面有兩種，其中一種應用是把一個題目使用圖論的模型來找出其特性，並且根據這些特性設計出演算法解決該問題。另一種應用則是建立圖論模型後，使用已知的工具（比方說線性規劃、矩陣相乘等等）來解決這些已知的圖論問題。在這 30 天之中，我想要介紹一些與圖論相關的演算法問題，並且描述一些範例程式。
9.2 找出分離點對 (Separating Pair) 如果一個點的子集合移除以後，會讓圖 G 變得不連通，那麼這個集合被稱為分離集 separting se...
9.3 三連通元件 3連通跟2連通真的不太一樣。以2連通來說，如果我們今天把整張圖，依照關節點切開，形成很多破碎子圖(也就是允許有某些邊懸掛在圖上，其中一個端點...
9.4 關於三連通的練習題 這題超難，我把連結放這邊就好。https://acm.timus.ru/problem.aspx?space=1&num=1...
10.3 幾個簡單的 Leetcode 例題 如果邊的權重都相等，那麼使用 BFS 就可以為我們找出最短的路徑了。今天來講講簡單的最短路徑例題吧。這幾個例子都是...
10.4 用矩陣角度看 APSP 從前兩天的文章可以看得出來，如果我們想要找出從 s 到 t 的最短路徑，可以透過枚舉中繼點 v 的方式來更新最短路徑的長度。也...
10.5 Seidel’s APSP 演算法 如果一個無向圖的所有邊都沒有權重，那麼就能用奧地利出生、從康乃爾大學念完博士畢業回到德國教書的 Raimund S...
10.6 Dijkstra’s SSSP 演算法 如果我們只在乎從某個點 s 出發到所有點的距離，而這張圖的所有邊權重都是非負的，那麼我們可以使用 Dijkst...
10.8 更多的 Leetcode 例題 Leetcode 1129. Shortest Path with Alternating Colors https:...
10.9 Chan’s APSP 演算法 我們今天來介紹一個 O(n^3 / log n) 時間複雜度的 APSP 演算法。 切成條狀的 (min, +)-矩陣...
10.10 Thorup’s 無向非負整數權重 SSSP 演算法 今天來介紹 Thorup 在 1997 年發表的整數模型線性時間的 SSSP 演算法。(可能會...
