目录
常见问题：
图作为非线性数据结构，在社交网络、路径规划等领域应用广泛。本文将系统总结图的表示方法、遍历策略以及经典算法实现，并分享代码实践中的关键细节。
一、图的基础概念与术语
图的定义：由顶点集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）
结论：图的算法设计需紧密结合实际场景。社交网络推荐使用BFS/DFS，路径规划首选Dijkstra，网络布线适用Kruskal/Prim。理解各算法的本质差异，方能灵活解决实际问题。