圖論：概覽
| , 1 minutes reading.
圖論：世界的隱形結構
地圖不是疆域
當我們在學校學習圖論時，我們看到的是圓圈（節點）和線條（邊）。它感覺抽象而枯燥。 但在軟體工程中，圖從來不僅僅是圖。
- 它是 城市 (Google Maps)。
- 它是 社交圈 (Facebook Friends)。
- 它是 依賴樹 (Webpack/NPM)。
- 它是 狀態機 (Game Logic)。
本章討論的「演算法」，不僅僅是數學公式。她們是 導航的策略。她們是我們用來回答關於「關係」的根本問題的工具：
- 「我該怎麼過去？」 (路徑規劃)
- 「誰最重要？」 (中心性)
- 「我們連通嗎？」 (連通性)
- 「什麼必須先發生？」 (依賴關係)
演算法的版圖
在這一章中，我們將探索七種在這些結構中導航的關鍵策略。
| 演算法 | 靈魂 / 隱喻 | 最佳應用場景 |
|---|---|---|
| Dijkstra | 蔓延的水流 總是優先探索最近的可能性，穩健而貪婪。 | GPS / 導航 當妳需要物理空間中絕對的最短路徑時。 |
| Bellman-Ford | 謹慎的審計師 一遍遍盤點帳目，捕捉負成本和漏洞。 | 金融 / 套利 當系統中存在負權重（獎勵）或需要極高容錯時。 |
| A 搜尋* | 持羅盤的遠見者 在現實成本與未來夢想（啟發式）之間取得平衡。 | 遊戲 / 開放世界 當妳知道目的地在哪裡，並且追求速度時。 |
| Floyd-Warshall | 上帝視角的外交官 坐鎮中央，透過中間人達成全員共識。 | 稠密網絡 / 預計算 當妳需要知道所有人到所有人的距離時（小規模）。 |
| 拓撲排序 | 工廠經理 只有當前置條件全部滿足時，才解鎖任務。 | 建置系統 / 編譯器 解決依賴地獄 (npm, make, webpack)。 |
| 並查集 | 數位官僚 扁平化層級結構，瞬間告訴妳「誰是老大的老大」。 | 社交分組 / 影像分割 高效地管理動態分組數據。 |
| LCA | 歷史調停者 穿越時間，尋找分歧發生的那個源頭。 | Git / 版本控制 尋找合併基準點或生物學共同祖先。 |
工程思維：建模
圖論最難的部分不是寫代碼（現成的函式庫多得是）。最難的是 建模 (Modeling)。
- 妳的問題是一個「最短路徑」問題嗎？（例如：最小化延遲）
- 它是一個「連通性」問題嗎？（例如：存取控制列表 ACL）
- 它是一個「流」問題嗎？（例如：最大頻寬）
一旦妳將混亂的現實問題映射到這些經典模型之一，解決方案往往就變得顯而易見了。
小結
不要死記硬背代碼。去理解每個演算法的 性格 (Personality)。
- 需要帶方向的速度？呼叫遠見者 (A*)。
- 需要在混亂中尋找絕對真理？呼叫審計師 (Bellman-Ford)。
- 需要理清先後順序？呼叫經理 (拓撲排序)。
讓我們開始這段穿越地圖的旅程吧。