c++图论————图的基本与遍历
目录
注：本文所有题目均来自蓝桥杯官网公开真题，仅做算法学习，代码皆由本人做出来并附上解析！
一，图的基础概念
1.结点：图中的点，结点间由边连接。
2.出边：从 A 指向 B 的边 E，是 A 的出边；出边数量叫出度。
3.入边：从 A 指向 B 的边 E，是 B 的入边；入边数量叫入度。
4.度数：某个点的出边 + 入边总数（无向图中对应边数）。
5.点权：结点上的权重（可表示价值、重要程度等）。
6.边权：边上的权重。
7.有向图：图中的边是有向边（有方向）。
8.无向图：图中的边是无向边（无方向）。
9.完全图：任意两个点之间都有一条边相连。
10.连通图：任意两个点之间都可达，一般用于无向图。
11.图的存储方式
（1）主要有邻接矩阵（如用d[i][j]表示）和邻接表（常用vector或 “前向星” 实现）两种。
（2）多数情况用邻接表；邻接矩阵常用于 Floyd 算法等场景。
如图（来自蓝桥杯官网）：
二，图的存储方式
1）领接表
1.存储结构：用vector<pair<int, int>> g[N]表示，其中：
g[x]存储结点x的所有出点信息；
g[i][j] = {first, second}：first是从i出发的某个出点的编号，second是这条边的边权。
2.示例（对应上图，未标注边权默认为 0）：
g[1] = {{2, 0}, {3, 0}}（结点 1 的出点是 2、3，边权为 0）；
g[6] = {{3, 7}}（结点 6 的出点是 3，边权为 7）；
g[4] = {{5, 0}, {6, 0}}（结点 4 的出点是 5、6，边权为 0）。
2）领接矩阵
1.定义：用d[i][j]表示从结点i到j的边的距离（通常代表最短距离）；若i到j无边，则d[i][j] = inf（无穷大）。
2.示例（对应上图）：
d[1,2] = 0（结点 1 到 2 的边权为 0）；
d[6,3] = 7（结点 6 到 3 的边权为 7）；
d[4,3] = inf（结点 4 到 3 无边）。
3.遍历出点的方式：若要枚举某个点的所有出点，需遍历所有点，再判断d[当前点][遍历点]是否不为inf。
三，图的遍历
1.dfs（深度优先搜索）遍历图
通俗的讲，就是“一条路走到黑”。
代码：
const int N = 1000l; bitset<N>vis;//vis[i]=true表示该点已走过 vector<int>g[N]; void dfs(int x) { vis[x] = true;//给该点打上标记 for (const auto y : g[x]) { if (vis[y]) continue; dfs(y); } }2，bfs（广（宽）度优先搜索）遍历图
就是“一层层往外走，每个点只走一次”。
核心思想是：从起点出发，先访问起点的所有直接邻接节点（第一层），再依次访问每个邻接节点的邻接节点（第二层），以此类推，直到遍历完所有可达节点。
形象理解：像 “水波扩散” 一样，从起点向外逐层覆盖，能保证第一次到达某个节点时的路径是最短路径（适用于无权图 / 边权为 1 的图）。
需要用队列，代码：
bitset<int>vis;//vis[x]=true说明已经走过 queue<int>q;//表示待拓展的点队列 while (q.size()) { // 步骤0：判断队列非空，进入循环 // 步骤1：取出当前队头节点x，并从队列中移除 int x = q.front(); q.pop(); // 步骤2：如果x已访问过，直接跳过后续逻辑，回到循环顶部 if (vis[x]) continue; // 步骤3：标记x为已访问 vis[x] = true; // 步骤4：遍历x的所有邻接节点y for (const auto& y : g[x]) { // 步骤4.1：将y入队（核心操作） q.push(y); // 步骤4.2：y入队后，代码做什么？ // -->继续执行for循环的下一次迭代，遍历x的下一个邻接节点 } // 步骤5：x的所有邻接节点遍历完成后，代码回到while循环顶部 // -->重新判断q.size()是否为真，若为真则重复步骤1-5 } 详细图解：
//bfs详细理解： // 1 // / \ // 2 3 // \ / // 4起点 1 入队，vis[1]=true
队列变为[1]
弹出队头 1，遍历其邻接节点 2、3：
2未访问-->vis[2] = true + 入队；
3未访问-->vis[3] = true + 入队；
队列变为[2,3]
处理 2 弹出队头 2，遍历其邻接节点 4：
4 未访问-->vis[4] = true + 入队；
队列变为[3,4]
处理 3 弹出队头 3，遍历其邻接节点 4：
4 已访问（vis[4] = true）-->跳过；
队列变为[4]
四，例题训练
例题一：蓝桥杯官网——帮派弟位
问题描述
有一个帮派，小明不学无术，混入其中。
给定一个正整数 n ，代表该帮派的总人数，并且小明的序号是 m ，给出这 n 个人中每个人的附属关系，确保给出的关系网为一棵树。帮派地位的定义是按照自己手下有多少帮众决定的，注意手下的手下也算是自己的手下。如果手下的帮众相同则按序号较小的在前面。你能帮助小明找到自己的帮派地位吗？
输入格式
第一行，两个正整数 n (1≤n≤10^5) 和 m (1≤m≤n) ，代表该帮派的总人数以及小明的序号。
接下来 n−1 行，每行两个正整数，格式如下：
l r(1≤l,r≤n) ， 代表序号为 l 的人附属于序号为 r 的人。
输出格式
一行，包含 1 个正整数，输出按手下人数多少排序后小明的排名。
样例输入
6 4 2 1 3 1 4 2 5 2 6 5 样例输出
5代码详解：
#include <iostream> #include<vector> #include<bitset> #include<algorithm> using namespace std; const int N=1e5+9; int sz[N]; vector<int>g[N]; //例题：bpdw // 题目逻辑： // 1 // / \ // 2 3 // / \ // 4 5 // / // 6 // 其实就是dfs求size子树大小-1 // 最终可得： // 1 5（1有5个小弟，1为第一关键字，5为第二关键字） // 2 3 // 3 0 // 4 0 // 5 1 // 6 0 // 然后按第二关键字降序，第一关键字升序排序： // 5 3 1 0 0 0 // 1 2 5 3 4 6 --->小明是编号4，他排行5，所以答案输出5 void dfs(int x,int p) { sz[x]=0; for(const auto &y:g[x]) { if(y==p) continue; dfs(y,x); sz[x]+=sz[y]+1;//要加一，不然全是0 } } //改写sort规则 struct Node { int id,siz; bool operator<(const Node&u)const { return siz==u.siz?id<u.id:siz>u.siz; } };//不要忘了结构体的分号！ int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int n,m;cin>>n>>m; for(int i=1;i<n;i++) { int l,r;cin>>l>>r; g[r].push_back(l);//表示r是l的小弟 } dfs(1,0);//计算小弟数量 vector<Node>v; for(int i=1;i<=n;i++) { v.push_back({i,sz[i]}); } sort(v.begin(),v.end()); for(int i=0;i<n;i++) { if(v[i].id==m) { cout<<i+1<<'\n'; } } return 0; }这小明就是弟中之弟O(∩_∩)O哈哈~。
例题二：蓝桥杯官网——可行路径的方案数
问题描述
有 n 个城市，这些城市间有 m 条双向路径，第 i 条路径连接城市 ai 和城市 bi，通行时间为 1 小时。请问1--->n有多少种可行路径?由于答案可能非常大，因此将答案对 10^9+7 取模。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 ai 和 bi，表示存在一条连接城市 ai 和城市 bi 的双向路径。
数据范围保证：2≤n≤2×10^5，0≤m≤2×10^5，1≤ai<bi≤n。
输出格式
输出一个整数，表示小蓝最快到达小桥的城市的方案数，答案对 10^9+7 取模。
输入样例
4 4 1 2 1 3 3 4 2 4 输出样例
2代码详解：
#include <iostream> #include<set> #include<algorithm> #include<vector> #include<queue> #include<bitset> #include<cstring>//memset头文件 using namespace std; using ll=long long; /*先建图，bfs第一次走到终点时的距离一定是最近距离，设dp[i]表示 从1到i的最近距离的路径方案数，在bfs过程中A->B更新d[B](即B到1点的最近距离)*/ //d[B]=min(d[B],d[A]+1),如果距离变小了。就重新计算dp[B]=dp[A],否则就dp[B]+=dp[A]。 //d[i]指的是索引城市i到1的最近距离！dp[i]指的是i到1的最短路径数（方案数）！ //一定要注意是两个最近！ const ll N=2e5+9; const ll P=1e9+7; vector<int>g[N]; ll dp[N],d[N]; void bfs(int x) { bitset<N>vis; queue<int>q; q.push(1); memset(d,0x3f,sizeof d);//初始化d无穷大！ d[1]=0;//初始化1到1的距离是0 //在此题目城市间的距离默认为1 dp[1]=1;//初始化1到1的路径方案数为1 while(q.size())//只要q不为空 { int x=q.front();q.pop(); if(vis[x])continue; vis[x]=true; for(const auto &y:g[x]) { // 情况1：从1到x再到y的路径长度（d[x]+1）比已知最短距离d[y]长 --> 不是最短路径，跳过 if(d[x]+1>d[y])continue; // 情况2：从1到x再到y的路径长度等于已知最短距离d[y] --> 找到新的最短路径，累加路径数 else if(d[x]+1==d[y]) dp[y]=(dp[x]+dp[y])%P; // 情况3：从1到x再到y的路径长度比已知最短距离d[y]短 --> 更新最短距离和路径数 else { d[y] = d[x] + 1; // 更新最短距离 dp[y] = dp[x]; // 路径数继承自x（此时x是第一条最短路径的前驱） q.push(y);//最后两个条件满足其一就入栈 } } } } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n,m;cin>>n>>m; while(m--) { int x,y;cin>>x>>y; g[x].push_back(y); g[y].push_back(x);//双向图 } bfs(1); cout<<dp[n]<<'\n'; return 0; }注意：
memset(d, 0x3f, sizeof d) 的作用
1. 为什么需要这行代码？
d[i] 表示「城市 i 到起点 1 的最短距离」，初始化时需要给所有节点的最短距离赋一个极大值（无穷大），原因是：
初始状态下，我们只知道起点 1 到自己的距离是 0（d[1]=0），其他节点到 1 的距离是未知的，默认设为 “无穷大” 表示「尚未找到路径」；
BFS 过程中，当第一次通过节点 x 到达节点 y 时，d[x]+1 一定小于 d[y]（因为 d[y] 是无穷大），此时才能正确更新 d[y] = d[x]+1（标记为第一条最短路径）。
2. 0x3f 是什么？
memset 是按字节赋值的函数，0x3f 是十六进制数，对应的十进制是 63，二进制是 00111111；
d 数组的类型是 ll（long long，8 字节），memset(d, 0x3f, sizeof d) 会给 d 中每个字节都赋值为 0x3f，因此每个 ll 类型的 d[i] 的值为：
0x3f3f3f3f3f3f3f3f（8 个 0x3f 拼接），对应的十进制约是 1e18，远大于题目中 n≤2e5 的最大可能距离（最长路径最多 2e5 步），是一个安全的 “无穷大”。
3. 为什么不用 memset(d, 0, ...) 或其他值？
若初始化为 0：d[y] 初始为 0，而 d[x]+1 ≥1，会导致 d[x]+1 > d[y] 永远成立，无法更新任何节点的距离，逻辑完全错误；
若初始化为其他小值（比如 1e9）：虽然也能作为 “无穷大”，但 0x3f3f3f3f3f3f3f3f 是 memset 能赋出的、适合 long long 的最优极大值（不会溢出，且足够大）。
