C++图论详解（已完结）
接下来我会对这些关键代码逐段拆解、详细讲解，帮你理解每一行代码的作用、设计思路和背后的图论原理。
一、图的表示：邻接矩阵 vs 邻接表
图的表示是所有图论算法的基础，我们先拆解邻接表（更常用）和邻接矩阵的核心代码。
1. 邻接矩阵代码拆解
邻接矩阵用二维数组存储顶点间的连接关系，以下是核心代码的逐行讲解：
#include <iostream>
#include <climits> // 用于INT_MAX（表示无边）
using namespace std;
const int MAXN = 100; // 定义最大顶点数，可根据需求调整
const int INF = INT_MAX; // 用无穷大表示两点间无边
int graph[MAXN][MAXN]; // 邻接矩阵的核心：二维数组存储边的权重
int n, m; // n是顶点数，m是边数
// 初始化邻接矩阵
void init() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 顶点自身到自身的权重为0，其余初始化为无穷大（无边）
graph[i][j] = (i == j) ? 0 : INF;
}
}
}
// 添加有向边：u是起点，v是终点，w是权重（默认1，适配无权图）
void addDirectedEdge(int u, int v, int w = 1) {
graph[u][v] = w; // 直接赋值权重，体现有向边的单向性
}
// 添加无向边：无向边是双向的，需同时赋值graph[u][v]和graph[v][u]
void addUndirectedEdge(int u, int v, int w = 1) {
graph[u][v] = w;
graph[v][u] = w;
}
// 打印邻接矩阵，方便可视化验证
void printGraph() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] == INF) cout << "∞\t"; // 无穷大显示为∞，更直观
else cout << graph[i][j] << "\t";
}
cout << endl;
}
}
int main() {
n = 4; m = 5; // 设定4个顶点，5条边
init(); // 初始化邻接矩阵
// 添加无向带权边，构建具体的图
addUndirectedEdge(0, 1, 2);
addUndirectedEdge(0, 2, 5);
addUndirectedEdge(1, 2, 1);
addUndirectedEdge(1, 3, 3);
addUndirectedEdge(2, 3, 4);
cout << "邻接矩阵：" << endl;
printGraph(); // 打印验证
return 0;
}核心设计思路： 用INF（无穷大）表示无边，避免与有效权重混淆； 无向边的对称性通过双向赋值实现； 初始化时将顶点自身的权重设为 0，符合图论的基本定义。
2. 邻接表代码拆解
邻接表用数组 + vector存储，更节省空间，是稀疏图的首选，核心代码讲解：
#include <iostream>
#include <vector> // 存储邻接顶点的核心容器
#include <utility> // 用于pair，存储<邻接顶点, 权重>
using namespace std;
const int MAXN = 100;
// 邻接表核心：数组的每个元素是vector<pair<int, int>>，存储顶点的邻接关系
vector<pair<int, int>> adj[MAXN];
int n, m; // 顶点数和边数
// 添加有向边：u的邻接表中添加(v, w)
void addDirectedEdge(int u, int v, int w = 1) {
adj[u].emplace_back(v, w); // emplace_back直接构造pair，比push_back更高效
}
// 添加无向边：u和v的邻接表互相添加对方
void addUndirectedEdge(int u, int v, int w = 1) {
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
// 打印邻接表，可视化每个顶点的邻接关系
void printGraph() {
for (int i = 0; i < n; i++) {
cout << "顶点 " << i << " 的邻接顶点：";
// 遍历顶点i的所有邻接边
for (auto& p : adj[i]) {
// p.first是邻接顶点，p.second是权重
cout << "(" << p.first << ", 权重" << p.second << ") ";
}
cout << endl;
}
}
int main() {
n = 4; m = 5;
// 构建无向带权图，与邻接矩阵的图结构一致
addUndirectedEdge(0, 1, 2);
addUndirectedEdge(0, 2, 5);
addUndirectedEdge(1, 2, 1);
addUndirectedEdge(1, 3, 3);
addUndirectedEdge(2, 3, 4);
cout << "邻接表：" << endl;
printGraph();
return 0;
}核心设计思路： 用pair<int, int>同时存储邻接顶点和边权重，兼顾带权图和无权图； emplace_back直接在 vector 中构造 pair，避免临时对象的拷贝，效率更高； 无向边通过双向添加邻接关系实现，与邻接矩阵的对称逻辑一致。
二、图的遍历：DFS（深度优先）与 BFS（广度优先）
遍历是图论的基础操作，DFS 和 BFS 的核心区别在于搜索顺序和数据结构（递归 / 栈 vs 队列）。
1. DFS 递归版代码拆解
DFS 的核心是 “先深后广”，通过递归实现回溯，代码讲解：
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm> // 用于fill函数，初始化数组
using namespace std;
vector<pair<int, int>> adj[100]; // 邻接表存储图
bool visited[100]; // 访问标记数组：标记顶点是否被访问，避免环的重复遍历
int n; // 顶点数
// DFS核心函数：u是当前访问的顶点
void dfs(int u) {
cout << "访问顶点：" << u << endl; // 输出访问的顶点，可视化遍历顺序
visited[u] = true; // 标记为已访问
// 遍历当前顶点的所有邻接顶点
for (auto& p : adj[u]) {
int v = p.first; // 提取邻接顶点
if (!visited[v]) { // 仅访问未被标记的顶点
dfs(v); // 递归访问邻接顶点，实现“深度优先”
}
}
}
int main() {
n = 4;
// 构建无向图，与之前的图结构一致
adj[0].emplace_back(1, 2); adj[0].emplace_back(2, 5);
adj[1].emplace_back(0, 2); adj[1].emplace_back(2, 1); adj[1].emplace_back(3, 3);
adj[2].emplace_back(0, 5); adj[2].emplace_back(1, 1); adj[2].emplace_back(3, 4);
adj[3].emplace_back(1, 3); adj[3].emplace_back(2, 4);
fill(visited, visited + n, false); // 初始化访问标记为false
cout << "DFS遍历（起点0）：" << endl;
dfs(0); // 从顶点0开始遍历
return 0;
}核心设计思路： visited数组是 DFS 的关键，解决图中环的重复遍历问题； 递归调用dfs(v)实现 “深度优先”：沿着一条路径走到头，再通过递归回溯到上一个顶点； 遍历邻接顶点时仅处理未访问的顶点，保证每个顶点只被访问一次（连通图）。
2. BFS 代码拆解
BFS 的核心是 “先广后深”，通过队列实现层级遍历，代码讲解：
#include <iostream>
#include <vector>
#include <utility>
#include <queue> // 队列容器，BFS的核心
#include <algorithm>
using namespace std;
vector<pair<int, int>> adj[100];
bool visited[100];
int n;
// BFS核心函数：start是遍历的起点
void bfs(int start) {
queue<int> q; // 队列存储待访问的顶点
q.push(start); // 起点入队
visited[start] = true; // 标记为已访问
// 队列非空时循环，处理所有待访问顶点
while (!q.empty()) {
int u = q.front(); // 取出队首顶点
q.pop(); // 队首出队
cout << "访问顶点：" << u << endl; // 输出访问的顶点
// 遍历当前顶点的所有邻接顶点
for (auto& p : adj[u]) {
int v = p.first;
if (!visited[v]) {
visited[v] = true; // 标记为已访问（入队时标记，避免重复入队）
q.push(v); // 邻接顶点入队，实现“广度优先”
}
}
}
}
int main() {
n = 4;
// 构建无向图，与DFS示例一致
adj[0].emplace_back(1, 2); adj[0].emplace_back(2, 5);
adj[1].emplace_back(0, 2); adj[1].emplace_back(2, 1); adj[1].emplace_back(3, 3);
adj[2].emplace_back(0, 5); adj[2].emplace_back(1, 1); adj[2].emplace_back(3, 4);
adj[3].emplace_back(1, 3); adj[3].emplace_back(2, 4);
fill(visited, visited + n, false);
cout << "BFS遍历（起点0）：" << endl;
bfs(0);
return 0;
}核心设计思路： 队列是 BFS 的核心，实现层级遍历：先处理当前层的顶点，再处理下一层； 入队时标记访问而非出队时标记，避免同一顶点被多次入队（如环的情况）； BFS 的天然特性：可求解无权图的最短路径（层级就是最短距离）。
三、经典算法：Dijkstra（单源最短路径）
Dijkstra 算法解决非负权图的单源最短路径问题，核心是贪心 + 优先队列，代码拆解：
#include <iostream>
#include <vector>
#include <queue> // 优先队列
#include <climits> // INT_MAX
#include <algorithm>
using namespace std;
const int MAXN = 100;
const int INF = INT_MAX;
vector<pair<int, int>> adj[MAXN]; // 邻接表：<邻接顶点, 权重>
int dist[MAXN]; // 距离数组：dist[i]表示起点到i的最短距离
// Dijkstra核心函数：start是起点
void dijkstra(int start, int n) {
// 初始化距离数组：所有顶点的初始距离为无穷大（不可达）
fill(dist, dist + n, INF);
dist[start] = 0; // 起点到自身的距离为0
// 小根堆：pair<距离, 顶点>，优先选择距离最小的顶点（贪心核心）
// greater<pair<int, int>> 表示按pair的第一个元素升序排列
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.emplace(0, start); // 起点入堆：距离0，顶点start
while (!pq.empty()) {
auto [d, u] = pq.top(); // 取出距离最小的顶点u，d是当前记录的距离
pq.pop();
// 剪枝：如果当前距离d大于已记录的最短距离dist[u]，直接跳过
// 原因：优先队列中可能存在同一顶点的多个距离记录，仅处理最短的
if (d > dist[u]) continue;
// 遍历顶点u的所有邻接顶点，更新最短距离
for (auto& [v, w] : adj[u]) {
// 松弛操作：如果通过u到v的距离更短，更新dist[v]
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.emplace(dist[v], v); // 新的距离入堆
}
}
}
}
int main() {
int n = 4;
// 构建无向带权图
adj[0].emplace_back(1, 2); adj[0].emplace_back(2, 5);
adj[1].emplace_back(0, 2); adj[1].emplace_back(2, 1); adj[1].emplace_back(3, 3);
adj[2].emplace_back(0, 5); adj[2].emplace_back(1, 1); adj[2].emplace_back(3, 4);
adj[3].emplace_back(1, 3); adj[3].emplace_back(2, 4);
dijkstra(0, n); // 从顶点0出发求最短路径
// 输出结果
cout << "起点0到各顶点的最短距离：" << endl;
for (int i = 0; i < n; i++) {
if (dist[i] == INF) cout << "到顶点" << i << "：不可达" << endl;
else cout << "到顶点" << i << "：" << dist[i] << endl;
}
return 0;
}核心设计思路： 距离数组初始化：用INF表示初始不可达，起点距离设为 0； 小根堆（优先队列）：贪心选择当前距离最短的顶点，是 Dijkstra 的核心； 松弛操作：dist[v] > dist[u] + w时更新距离，是所有最短路径算法的基础； 剪枝优化：跳过优先队列中过时的距离记录（同一顶点的非最短距离），减少无效计算。
四、经典算法：Kruskal（最小生成树）
Kruskal 算法解决无向连通图的最小生成树问题，核心是贪心 + 并查集，代码拆解：
#include <iostream>
#include <vector>
#include <algorithm> // 排序、fill
using namespace std;
// 边的结构体：存储起点u、终点v、权重w
struct Edge {
int u, v, w;
// 重载<运算符，用于按权重升序排序（贪心核心）
bool operator<(const Edge& other) const {
return w < other.w;
}
};
vector<Edge> edges; // 边集数组：存储所有边
int parent[MAXN]; // 并查集数组：维护顶点的连通性
// 并查集查找函数：带路径压缩，降低查找复杂度
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩：直接指向根节点
return parent[x];
}
// 并查集合并函数：合并两个顶点的连通分量
void unite(int x, int y) {
x = find(x); // 找到x的根节点
y = find(y); // 找到y的根节点
if (x != y) parent[y] = x; // 不同根则合并
}
// Kruskal核心函数：返回最小生成树的总权重
int kruskal(int n) {
sort(edges.begin(), edges.end()); // 边按权重升序排序（贪心）
// 初始化并查集：每个顶点的父节点是自身
for (int i = 0; i < n; i++) parent[i] = i;
int totalWeight = 0; // 最小生成树的总权重
int edgeCount = 0; // 已选的边数（最小生成树需n-1条边）
// 遍历所有边，按权重从小到大选择
for (auto& e : edges) {
// 若u和v属于不同的连通分量，说明选这条边不会形成环
if (find(e.u) != find(e.v)) {
unite(e.u, e.v); // 合并连通分量
totalWeight += e.w; // 累加权重
edgeCount++; // 已选边数+1
if (edgeCount == n - 1) break; // 选够n-1条边，直接退出（优化）
}
}
// 若边数不足n-1，说明图不连通，无最小生成树
return (edgeCount == n - 1) ? totalWeight : -1;
}
int main() {
int n = 4; // 4个顶点
// 边集数组：存储所有边，与之前的图结构一致
edges = {{0,1,2}, {0,2,5}, {1,2,1}, {1,3,3}, {2,3,4}};
int minTotal = kruskal(n);
if (minTotal == -1) cout << "图不连通，无最小生成树" << endl;
else cout << "最小生成树的总权重：" << minTotal << endl; // 结果为6
return 0;
}核心设计思路：边集数组 + 排序：按权重升序排序，贪心选择最短的边；并查集：解决环的检测和连通性维护，是 Kruskal 的关键；路径压缩：优化并查集的查找效率，将时间复杂度降到近似(O(1))；终止条件：选够(n-1)条边时退出，因为最小生成树的边数固定为顶点数 - 1。
五、关键知识点总结图的表示：
邻接矩阵适合稠密图（顶点少），邻接表适合稀疏图（顶点多）；遍历核心：DFS 用递归 / 栈实现深度探索，BFS 用队列实现层级探索，均需visited数组避免重复访问；Dijkstra：贪心 + 优先队列，解决非负权单源最短路径，核心是松弛操作；Kruskal：贪心 + 并查集，解决最小生成树，核心是按权选边 + 环检测。
六、刷题
P10109 [GESP202312 六级] 工作沟通
P13016 [GESP202506 六级] 最大因数