圖論核心算法詳解：從存儲結構到最短路徑（附C++實現）

一、圖的基礎概念與術語

二、圖的存儲結構

1. 鄰接矩陣

實現思路：

2. 鄰接表

實現思路：

應用場景：

時間復雜度分析：

三、圖的遍歷算法

1. 廣度優先搜索（BFS）

核心思想：

應用場景：

注意事項：

2. 深度優先搜索（DFS）

核心思想：?

算法特點：

應用場景：

注意事項：

四、最小生成樹算法

1. Kruskal算法

貪心策略：

應用場景：

實現技巧：

2. Prim算法

算法概述：

貪心策略：

核心思想：

應用場景：

算法特點：

五、最短路徑算法

1. Dijkstra算法（無負權圖）

核心思想：

具體步驟：

算法特點：

應用場景：

注意事項：

2. Bellman-Ford算法（支持負權）

核心思想：

算法說明：

應用場景：

算法特點：

3. Floyd-Warshall算法（多源最短路徑）

核心思想：

算法步驟：

算法特點：

應用場景：

六、實踐總結與經驗

調試技巧：

工程優化：

常見問題：

圖作為非線性數據結構，在社交網絡、路徑規劃等領域應用廣泛。本文將系統總結圖的表示方法、遍歷策略以及經典算法實現，并分享代碼實踐中的關鍵細節。

一、圖的基礎概念與術語

圖的定義：由頂點集V和邊集E構成，記為G=(V, E)
有向圖：邊有方向，<x, y> ≠ <y, x>
無向圖：邊無方向，(x, y) ≡ (y, x)
完全圖：任意兩頂點間均有邊連接
鄰接頂點：通過邊直接相連的頂點對
頂點的度：與其關聯的邊數（有向圖分出/入度）
連通圖：任意兩頂點間存在路徑
生成樹：連通圖的極小連通子圖（n頂點，n-1條邊）

二、圖的存儲結構

1. 鄰接矩陣

鄰接矩陣是圖論中最常用的圖的存儲方式之一，它通過二維矩陣來直觀地表示圖中頂點之間的連接關系。

實現思路：

頂點存儲：
- 使用一維數組存儲圖中所有頂點
- 每個頂點可以通過其在數組中的索引來快速訪問
- 例如：vector<string> vertices?存儲頂點名稱
邊關系存儲：
- 使用二維矩陣（二維數組）存儲頂點之間的邊關系
- 對于無權圖，矩陣元素通常用0/1表示邊的有無
- 對于有權圖，矩陣元素存儲邊的權值
- 無連接時可以用特殊值表示（如0、INT_MAX等）
空間復雜度：
- 鄰接矩陣的空間復雜度為O(V2)，其中V是頂點數量
- 適合稠密圖的存儲，但對于稀疏圖會造成空間浪費

C++實現核心代碼：

template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph {
public:// 添加邊（自動處理無向圖對稱性）void AddEdge(const V& src, const V& dst, const W& w) {size_t srci = _GetIndex(src);size_t dsti = _GetIndex(dst);_matrix[srci][dsti] = w;if (!Direction) _matrix[dsti][srci] = w; // 無向圖對稱處理}
private:vector<V> _vertexs;            // 頂點集合vector<vector<W>> _matrix;     // 鄰接矩陣map<V, size_t> _vIndexMap;     // 頂點->下標映射
};

2. 鄰接表

實現思路：

鄰接表是一種常用的圖存儲結構，它結合了數組和鏈表的優點。具體實現思路如下：

頂點存儲：使用一個數組來存儲圖中的所有頂點信息。數組的每個元素對應圖中的一個頂點，通常包含頂點數據和指向鄰接鏈表的指針。
邊存儲：對于每個頂點，使用鏈表來存儲其所有鄰接點。鏈表中的每個節點表示一條邊，包含鄰接點的索引（或指針）和可能的邊權重等信息。

C++實現核心代碼：

struct Edge {int _dsti; W _w;Edge* _next;
};class Graph {
public:void AddEdge(const V& src, const V& dst, const W& w) {size_t srci = _GetIndex(src);size_t dsti = _GetIndex(dst);// 添加src->dst邊Edge* edge = new Edge(dsti, w);edge->_next = _table[srci];_table[srci] = edge;// 無向圖添加反向邊if (!Direction) {Edge* reEdge = new Edge(srci, w);reEdge->_next = _table[dsti];_table[dsti] = reEdge;}}
private:vector<V> _vertexs;vector<Edge*> _table;  // 鄰接表頭指針數組
};

應用場景：

社交網絡中的好友關系表示
城市間的交通路線圖
稀疏圖的高效存儲
路徑查找算法（如Dijkstra算法）的實現基礎

時間復雜度分析：

添加邊：O(1)
查詢兩個頂點是否相鄰：O(degree(v))
遍歷所有鄰接點：O(degree(v))
空間復雜度：O(V+E)

三、圖的遍歷算法

1. 廣度優先搜索（BFS）

核心思想：

分層遍歷，使用隊列輔助實現。這是一種在圖或樹數據結構中進行遍歷的經典算法，特點是按層級逐步擴展搜索范圍，確保在訪問下一層節點前先完整訪問當前層的所有節點。

void BFS(const V& src) {vector<bool> visited(_vertexs.size(), false);queue<size_t> q;q.push(_GetIndex(src));visited[q.front()] = true;while (!q.empty()) {size_t front = q.front();q.pop();cout << _vertexs[front] << " "; // 訪問頂點// 遍歷鄰接點for (size_t i = 0; i < _vertexs.size(); ++i) {if (!visited[i] && _matrix[front][i] != MAX_W) {q.push(i);visited[i] = true;}}}
}

應用場景：

社交網絡中的好友關系推薦
網絡爬蟲的網頁抓取策略
解決迷宮問題
查找兩個節點間的最短路徑
計算機網絡中的廣播路由

注意事項：

需要維護訪問標記數組避免重復訪問
對于非連通圖，需要對每個連通分量分別執行BFS
隊列的實現可以使用鏈表或數組
在樹結構中不需要標記已訪問（因為不存在環路）

2. 深度優先搜索（DFS）

核心思想：?

深度優先搜索是一種經典的圖遍歷算法，其核心思想是沿著圖的深度方向盡可能深入地進行搜索。當到達無法繼續前進的節點時，算法會回溯到最近的分叉點，嘗試其他未探索的路徑。這種"一條路走到底"的策略使得DFS能夠高效地探索整個圖結構。

算法特點：

遞歸實現：DFS通常采用遞歸的方式實現，自然體現了"后進先出"的棧特性
回溯機制：當遇到死胡同時會自動回退到上一個節點
空間復雜度：O(h)，其中h是圖的最大深度
不完全性：在無限圖中可能無法找到解

void _DFS(size_t index, vector<bool>& visited) {cout << _vertexs[index] << " ";visited[index] = true;for (size_t i = 0; i < _vertexs.size(); ++i) {if (!visited[i] && _matrix[index][i] != MAX_W) {_DFS(i, visited); // 遞歸深入未訪問鄰接點}}
}

應用場景：

迷宮求解
拓撲排序
連通分量檢測
尋找圖中的環路
解決八皇后問題等回溯問題

注意事項：

需要記錄已訪問節點防止重復訪問
遞歸實現可能導致棧溢出，大規模數據時建議使用顯式棧
不保證找到最短路徑

四、最小生成樹算法

1. Kruskal算法

貪心策略：

該算法采用貪心思想，每次從剩余邊中選擇權值最小的邊加入到生成樹中，但要確保所選邊不會與已選邊構成環路。具體步驟如下：

(1) 初始化：將圖中所有邊按權值從小到大排序，并創建一個空的邊集合MST（最小生成樹）。

(2) 邊選擇：依次取出權值最小的邊進行判斷：

如果該邊的兩個頂點不在同一個連通分量中（即加入該邊不會形成環路），則將該邊加入MST
否則跳過該邊

(3) 終止條件：當MST中包含|V|-1條邊時（V為頂點數），算法終止

W Kruskal(Graph& minTree) {priority_queue<Edge> minHeap; // 最小堆存儲邊UnionFindSet ufs(_vertexs.size()); // 并查集判環// 遍歷所有邊入堆for (size_t i = 0; i < _matrix.size(); ++i) {for (size_t j = i+1; j < _matrix[i].size(); ++j) {if (_matrix[i][j] != MAX_W) {minHeap.push(Edge(i, j, _matrix[i][j]));}}}W total = W();size_t edgeCount = 0;while (edgeCount < _vertexs.size()-1 && !minHeap.empty()) {Edge minEdge = minHeap.top();minHeap.pop();if (!ufs.InSameSet(minEdge._srci, minEdge._dsti)) {minTree.AddEdge(_vertexs[minEdge._srci], _vertexs[minEdge._dsti], minEdge._w);ufs.Union(minEdge._srci, minEdge._dsti);total += minEdge._w;edgeCount++;}}return total; // 返回總權值
}

應用場景：

網絡布線問題：在多個節點間鋪設最經濟的網絡線路
電路設計：連接電子元件的最短布線方案
交通規劃：構建城市間最低成本的公路網絡

實現技巧：

使用并查集(Disjoint Set)數據結構高效判斷是否形成環路
時間復雜度：O(ElogE)或O(ElogV)，其中E為邊數，V為頂點數

2. Prim算法

算法概述：

Prim算法是一種用于求解加權無向連通圖的最小生成樹問題的貪心算法。該算法由捷克數學家沃伊捷赫·亞爾尼克（Vojtěch Jarník）于1930年首次發現，后來在1957年被美國計算機科學家羅伯特·普里姆（Robert C. Prim）獨立發現，因此也被稱為Jarník-Prim算法。該算法與Kruskal算法并列為求解最小生成樹問題的兩大經典算法。

貪心策略：

從頂點出發擴展最小邊

核心思想：

是采用貪心策略，逐步構建最小生成樹。具體步驟如下：

初始階段：
- 隨機選擇一個頂點作為起始點
- 將該頂點加入生成樹集合T
- 初始化邊的優先隊列Q，包含所有與該頂點相連的邊
迭代過程：
- 從Q中取出權重最小的邊(u,v)
- 如果頂點v不在T中：
  - 將邊(u,v)加入最小生成樹
  - 將v加入集合T
  - 將與v相連且另一端不在T中的所有邊加入Q
- 重復上述過程，直到T包含所有頂點

W Prim(Graph& minTree, const V& src) {vector<bool> inSet(_vertexs.size(), false);priority_queue<Edge> minHeap;size_t srci = _GetIndex(src);inSet[srci] = true;// 初始頂點鄰接邊入堆for (size_t i = 0; i < _vertexs.size(); ++i) {if (_matrix[srci][i] != MAX_W) {minHeap.push(Edge(srci, i, _matrix[srci][i]));}}W total = W();while (!minHeap.empty()) {Edge minEdge = minHeap.top();minHeap.pop();if (!inSet[minEdge._dsti]) {minTree.AddEdge(_vertexs[minEdge._srci],_vertexs[minEdge._dsti],minEdge._w);inSet[minEdge._dsti] = true;total += minEdge._w;// 新頂點鄰接邊入堆for (size_t i = 0; i < _vertexs.size(); ++i) {if (!inSet[i] && _matrix[minEdge._dsti][i] != MAX_W) {minHeap.push(Edge(minEdge._dsti, i, _matrix[minEdge._dsti][i]));}}}}return total;
}

應用場景：

網絡布線設計：選擇成本最低的網絡連接方案
交通規劃：建立城市間最經濟的交通網絡
電路板設計：優化元件之間的連線路徑

算法特點：

時間復雜度：使用優先隊列時為O(ElogV)，其中E為邊數，V為頂點數
適用于稠密圖（邊數較多的圖）
始終保持當前解是連通的

五、最短路徑算法

1. Dijkstra算法（無負權圖）

核心思想：

貪心策略 + 松弛操作

具體步驟：

初始化階段
- 設置起始節點的距離為0，其他所有節點的距離為無窮大
- 將所有節點標記為未訪問
- 創建一個優先隊列（通常使用最小堆）來存儲節點
主循環階段
- 從優先隊列中取出當前距離最小的節點u
- 標記節點u為已訪問
- 對u的每個鄰接節點v進行松弛操作：
  - 計算從起始節點到v的新距離（u的距離 + u到v的邊權重）
  - 如果新距離小于v當前記錄的距離，則更新v的距離值
  - 將v加入優先隊列（如果未訪問過）
終止條件
- 當優先隊列為空時終止
- 或當目標節點被標記為已訪問時提前終止

void Dijkstra(const V& src, vector<W>& dist, vector<int>& parentPath) {size_t srci = _GetIndex(src);dist.assign(_vertexs.size(), MAX_W);parentPath.assign(_vertexs.size(), -1);vector<bool> s(_vertexs.size(), false);dist[srci] = 0;for (size_t i = 0; i < _vertexs.size(); ++i) {// 選取未訪問的最小dist頂點size_t u = srci;W min = MAX_W;for (size_t j = 0; j < _vertexs.size(); ++j) {if (!s[j] && dist[j] < min) {min = dist[j];u = j;}}s[u] = true;// 松弛操作for (size_t v = 0; v < _vertexs.size(); ++v) {if (!s[v] && _matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v]) {dist[v] = dist[u] + _matrix[u][v];parentPath[v] = u;}}}
}

算法特點：

適用于有向圖和無向圖
要求圖中不能有負權邊
時間復雜度：O((V+E)logV)，使用優先隊列實現
空間復雜度：O(V)

應用場景：

道路網絡中的最短路線規劃
電信網絡中的數據傳輸路徑選擇
物流配送中的最優路線計算
游戲AI中的路徑規劃

注意事項：

當圖中存在負權邊時，需要使用Bellman-Ford算法
對于稠密圖，使用數組實現的版本可能更高效
在實際實現中，通常需要記錄前驅節點以重建最短路徑

2. Bellman-Ford算法（支持負權）

核心思想：

動態規劃 + 松弛V-1輪

算法說明：

初始化階段：

創建距離數組dist[]，初始時設置源點s的dist[s]=0
其他所有頂點的dist值設為無窮大(∞)

松弛操作(V-1輪)：

對每條邊(u,v)進行松弛操作： if dist[v] > dist[u] + weight(u,v): dist[v] = dist[u] + weight(u,v)
每輪松弛操作都會使得至少一個頂點的最短距離被確定
總共需要進行|V|-1輪松弛，其中|V|是頂點數量

負權環檢測：

完成V-1輪松弛后，再進行一次額外松弛
如果還能繼續松弛，說明圖中存在負權環

bool BellmanFord(const V& src, vector<W>& dist, vector<int>& parentPath) {size_t srci = _GetIndex(src);dist.assign(_vertexs.size(), MAX_W);parentPath.assign(_vertexs.size(), -1);dist[srci] = 0;// 松弛V-1輪for (size_t k = 0; k < _vertexs.size()-1; ++k) {bool updated = false;for (size_t i = 0; i < _vertexs.size(); ++i) {for (size_t j = 0; j < _vertexs.size(); ++j) {if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]) {dist[j] = dist[i] + _matrix[i][j];parentPath[j] = i;updated = true;}}}if (!updated) break; // 提前收斂}// 檢測負權環for (size_t i = 0; i < _vertexs.size(); ++i) {for (size_t j = 0; j < _vertexs.size(); ++j) {if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]) {return false; // 存在負權環}}}return true;
}

應用場景：

路由協議中的路徑選擇
金融系統中的套利檢測
交通網絡中的最短路徑規劃
帶負權邊的圖論問題

算法特點：

時間復雜度O(VE)，其中V是頂點數，E是邊數
可以處理帶負權邊的圖
相比Dijkstra算法更通用但效率較低
能夠檢測負權環的存在

3. Floyd-Warshall算法（多源最短路徑）

?Floyd-Warshall算法是一種經典的動態規劃算法，用于求解帶權圖中所有頂點對之間的最短路徑。該算法通過逐步優化距離矩陣來找到最短路徑。

核心思想：

動態規劃 + 三重循環

算法步驟：

初始化距離矩陣D，其中D[i][j]表示頂點i到頂點j的直接距離。若兩點不相連，則設為無窮大(∞)；i到i的距離為0。
執行三重循環：
- 外層循環(k)：遍歷所有可能的中間頂點(1到n)
- 中層循環(i)：遍歷所有起點(1到n)
- 內層循環(j)：遍歷所有終點(1到n) 每次比較D[i][j]和D[i][k]+D[k][j]，取較小值更新D[i][j]
最終D矩陣即為所有頂點對的最短距離矩陣

void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvParentPath) {size_t n = _vertexs.size();vvDist.resize(n, vector<W>(n, MAX_W));vvParentPath.resize(n, vector<int>(n, -1));// 初始化for (size_t i = 0; i < n; ++i) {for (size_t j = 0; j < n; ++j) {if (_matrix[i][j] != MAX_W) {vvDist[i][j] = _matrix[i][j];vvParentPath[i][j] = i;}if (i == j) vvDist[i][j] = 0;}}// 動態規劃核心for (size_t k = 0; k < n; ++k) {     // 中轉點for (size_t i = 0; i < n; ++i) { // 起點for (size_t j = 0; j < n; ++j) { // 終點if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W &&vvDist[i][k] + vvDist[k][j] < vvDist[i][j]) {vvDist[i][j] = vvDist[i][k] + vvDist[k][j];vvParentPath[i][j] = vvParentPath[k][j]; // 更新路徑}}}}
}

算法特點：

時間復雜度：O(n3)，適合稠密圖
空間復雜度：O(n2)
可以處理負權邊（但不能有負權回路）
能檢測圖中是否存在負權回路

應用場景：

交通網絡中的最短路線規劃
計算機網絡中的路由選擇
社交網絡中的關系鏈分析
物流配送路徑優化

六、實踐總結與經驗

調試技巧：
- 使用小規模圖（如5個頂點）驗證算法正確性
- 可視化輸出路徑矩陣輔助調試
- 對負權圖專門設計測試用例
工程優化：
- 鄰接表適合稀疏圖（節省空間）
- 堆優化Dijkstra提升性能至O(ElogV)
- 并查集路徑壓縮優化Kruskal
常見問題：
- 負權環導致Bellman-Ford無法收斂
- 非連通圖的最小生成樹需分別處理各連通分量
- 鄰接矩陣初始化注意對角線（dist[i][i]=0）