图论核心算法详解：从存储结构到最短路径（附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(V²)，其中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(n³)，适合稠密图
空间复杂度：O(n²)
可以处理负权边（但不能有负权回路）
能检测图中是否存在负权回路

应用场景：

交通网络中的最短路线规划
计算机网络中的路由选择
社交网络中的关系链分析
物流配送路径优化

六、实践总结与经验

调试技巧：
- 使用小规模图（如5个顶点）验证算法正确性
- 可视化输出路径矩阵辅助调试
- 对负权图专门设计测试用例
工程优化：
- 邻接表适合稀疏图（节省空间）
- 堆优化Dijkstra提升性能至O(ElogV)
- 并查集路径压缩优化Kruskal
常见问题：
- 负权环导致Bellman-Ford无法收敛
- 非连通图的最小生成树需分别处理各连通分量
- 邻接矩阵初始化注意对角线（dist[i][i]=0）