如果你想在 USACO 這類競賽中不斷晉級分區，掌握競賽程式設計中的圖演算法是你能學習的、回報最高的內容之一。
圖幾乎可以為一切建模：道路網路、社交關係、任務之間的依賴，甚至像素網格。正因為它如此靈活，命題人非常依賴它。事實上，從 Silver 到 Platinum，大多數 USACO 競賽都至少包含一道圖論題，因此能熟練運用這些工具的學生在比賽當天就擁有真正的優勢。
本路線圖大致按照你應當學習的順序，逐一介紹核心演算法，並展示隨著你在分區中不斷攀升，每種演算法通常會以怎樣的形式出現。要了解完整情況，請始終在 USACO 官方網站上確認細節，因為賽制和分數線可能在不同賽季之間發生變化。
從走訪開始：BFS 與 DFS
有兩種演算法幾乎是其他一切的基礎：廣度優先搜尋（BFS）和深度優先搜尋（DFS）。兩者都能在 O(V + E) 時間內走訪每一個可達的頂點，其中 V 是頂點數，E 是邊數。
- DFS 會沿著一條路徑盡可能深入地探索，然後再回溯。它是尋找連通分量、偵測環路以及對有向無環圖進行拓撲排序的天然工具。
- BFS 逐層探索，因此能在無權圖或網格中找到最短路徑。一種常見的 Silver 風格題目是對網格進行洪水填充，以統計區域數量或測量距離。
許多早期的競賽題目其實只是偽裝過的走訪。一片農田網格、一座迷宮，或者一個朋友網路，都可以重新表述為「從這裡執行 BFS 或 DFS」。熟練掌握這兩者，是日後每一項技術的根基。
帶權圖：最短路徑與生成樹
一旦邊帶上了權值，單純的 BFS 就不再夠用了。這通常正是 Gold 分區圖論工作的起點，也是學生開始接觸更豐富工具箱的地方。
最短路徑
- 當所有邊權均為非負時，Dijkstra 演算法能從單一源點求出最短路徑。用優先佇列實作時，它的執行時間約為 O(E log V)，是帶權最短路徑問題的主力工具。
- Bellman-Ford 能處理負邊權，並能偵測負環，代價是速度較慢。
- Floyd-Warshall 能在 O(V³) 時間內計算所有頂點對之間的最短路徑，當圖較小時這是可以接受的。
- 0-1 BFS 是一種巧妙的折中方案，適用於邊權只取 0 或 1 的圖，它借助雙端佇列實作。
最小生成樹
Kruskal 和 Prim 演算法都能求出最小生成樹，即讓每個頂點保持連通的、成本最低的一組邊。Kruskal 依賴並查集（互斥集合聯集）結構，這一結構本身就值得學習，因為它會出現在許多連通性問題中。
進階結構：分量、樹與網路流
到了 Platinum 級別，題目往往要求對高階思想進行創造性的組合。以下幾項值得了解：
- 透過 Tarjan 或 Kosaraju 演算法求強連通分量，用於簡化有向圖。
- 樹演算法，例如最近共同祖先（LCA）、倍增以及尤拉序，因為許多偽裝過的圖其實本質上是樹。
- 最大流與最小割（例如 Dinic 演算法），它們能為匹配和容量問題建模，而這些問題乍看之下與圖毫不相干。
你並不需要這些就能開始參賽。它們只有在走訪和最短路徑都變得駕輕就熟之後才會變得相關，所以請克制住急於趕進度的衝動。
如何練習
讀懂一個演算法，和在限時之下把它實作出來，是兩回事。要有意識地累積能力：
- 先按專題刷題，然後再回到混合練習，這樣你就必須自己辨識出正確的方法。
- 在接近真實競賽的條件下給自己計時，競賽通常會給三道題留出幾個小時。
- 複盤每一次錯誤的提交，直到你弄懂導致失敗的那個測試案例。
有體系的指導能極大地加速這一過程。我們的競賽程式設計專案正是圍繞這一進階路徑打造的，志在奧賽的學生還可以在我們的 USACO 備賽頁面上找到專門的訓練方向。當你準備好規劃路線時，歡迎在 BIAA 探索全部可選方案，從今天起把圖論變成競賽成績：從這裡開始。