简单图论大学习
图的存储与遍历
存储
存图有多种方法，都不复杂，很容易实现。
1.邻接矩阵
直接使用二维数组 graph[N][N] 来存，它虽然代码简单，查询较快，但是有时候很浪费空间，而且数据范围有较大的限制，并不常用。
2.邻接表
顾名思义，邻接表就是 每个节点值储存它直接可以到的其他节点 。
它的空间浪费比邻接矩阵小得多，但是，在找邻居的时候，要遍历它的整个邻接表，速度比邻接矩阵慢。
3.链式前向星
它其实就是用链表实现的邻接表。
主体一个 head[u] 数组，指向 u 的邻居存的地址。
和一个 struct Edge{int to,nxt}; ，其中， to 指邻居编号， nxt 指下一个邻居的地址。
具体代码如下：
点击查看代码
4.Vector 直接存边
这个方法是最常用的一个。
直接用 vector<Edge> e[N] 存边就可以了。
struct Edge{int to,w;};
vector<Edge> e[N];
...
遍历
这里只介绍后两种常见方法的遍历方法，前两种请读者自行探讨。
链式前向星
for(int i=head[u];~i;i=e[i].nxt){
...
}
Vector 直接存边
for(auto it:e[u]){
...
}
那么，学会存图和遍历后，来做一下几道模板题来练一练吧：
二、拓扑排序
首先，你要了解拓扑在干什么：
给一个有向无环图(DAG)的所有节点排序————OI_WIKI
那么，拓扑排序之后，就一定有：
- 每个顶点仅出现一次；
- 对于有向边
A->B，在序列中都必有A在B前。
操作还是比较简单的：
- 1.找到入度为 0 的点并输出；
- 2.将所有与该点连接的边删除，邻居入度减 1；
- 3.重复步骤 1~2 ,直到没有任何点入度为 0 为止。
注意：有环图是不能进行拓扑排序的！！注意：有环图是不能进行拓扑排序的！！注意：有环图是不能进行拓扑排序的！！
学了拓扑，还是做一道模板题吧：
【模板】拓扑排序/家谱树
三、欧拉路
欧拉路其实就是一个简单的一笔画问题。
它的定义是：从图中某一个点出发，遍历整个图，图中每一条边通过且仅通过一次。
欧拉回路就是起点和终点一样的欧拉路。
一般关于欧拉路的问题基本上就是：
- 是否有欧拉路。
- 打印欧拉路。
通常是通过处理度来解决问题的。
其中，度数为奇数的为奇点，度数为偶数的为偶点。
1.存在性判断
无向图
若全是偶点，存在欧拉回路，显然。
若有 2 个奇点，存在欧拉路，一个是起点，另一个是终点。
有向图
和无向图差不多，我们将一个点的度数记作入度减去出度。
若所有点度数为零，才会存在欧拉回路。
若仅有一个点度数为 1，一个点度数为 −1，其余点的度数为零，才存在欧拉路，1 的为起点，−1 的为终点。
2.输出欧拉回路
dfs 即可。
习题
四、连通性问题
关于连通性：
- 连通：对于无向图的两点 �,� ，若存在途径使得 �0=� 且 ��=�，则称 �,� 连通。
- 连通图：任意两点连通的无向图称为连通图。
1.无向图
一些定义：
- 割点：对于 �=(�,�)，�∈�,若删去 � 以及关联的边后，图分裂为两个及以上不相连的子图，则称 � 为 � 的割点。
- 割边（桥）：同上。
首先，我们要会求割点和割边：
很明显考虑 Tarjan 算法。
求割点 【模板】割点（割顶）
依赖一下两个主要的数组：
- 追溯值 ���� ：定义为以 � 为根的搜索树上的点以及通过一条不在搜索树上的边能达到的结点中的最小编号。
- 时间戳 ���� ：定义为 � 按访问顺序的编号。
void Tarjan(int u){
dfn[u]=low[u]=++Time;
int son=0;
for(auto v:e[u]){
if(dfn[v]){
low[u]=min(low[u],dfn[v]);
continue;
}
son++;
Tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]&&u!=root)cnt+=!is_cut[u],is_cut[u]=1;
}
if(son>=2&&u==root)cnt+=!is_cut[u],is_cut[u]=1;
}
求割边 【模板】割边（桥）
和割点很像：
void tarjan(int u,int fa){
dfn[u]=low[u]=++idx;
for(int v:g[u]){
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u], low[v]);
if(dfn[u]<low[v])add_bridge(u,v);
}
else if(v!=fa)low[u]=min(low[u],dfn[v]);
}
}
习题：
割点和割边可以引出以下这些更为重要的定义：
- 点双连通图：不存在割点的无向连通图称为点双连通图。
- 边双连通图：不存在割边的无向连通图称为边双连通图。
- 点双连通分量：一张图的极大点双连通子图称为点双连通分量（v-DCC），简称点双。
- 边双连通分量：一张图的极大边双连通子图称为边双连通分量（e-DCC），简称边双。
但是，实际上，点双的定义是有歧义的，而笔者采用的是接下来的这一个 OI_WIKI 版本的定义，笔者以后的代码书写也参考接下来的版本。
在一张连通的无向图中，对于两个点 � 和 �，如果无论删去哪一个点（不能删 � 和 � 自己）都不能使它们不连通，我们就说 � 和 � 点双连通。——OI_WIKI
求边双 【模板】边双连通分量
边双连通分量的求法很简单。并不比求割边的代码长太多，依旧依赖一下两个主要的数组：
- 追溯值 ����
- 时间戳 ����
在求割边的时候，我们已经对所有割边进行了标记。
所以我们只要再次 DFS ，不访问割边，对每一各连通块进行标记，则可以得到边双。
求点双 【模板】点双连通分量
点双联通分量的求法就没有边双那么简单了。虽然割边不隶属于任何边双，但是割点是有可能隶属于多个点双的。
所以此时我们就应该在跑 Tarjan 的过程中维护一个栈。
- 当一个节点第一次被访问时，入栈。
- 当
dfn[x]<=low[y]成立时，不断弹栈，直至 � 被弹出。而且刚刚弹掉的节点和 � 构成一个 v-DCC 。
习题：
边双：
点双：
2.有向图
一些定义：
- 强连通：若一张有向图的节点两两互相可达，则称这张图是强连通的。
- 强连通分量：即极大的强连通子图，称为SCC。
首先，我们要了解 DFS 生成树。
我们在一个有向图上选一点 � ，从 � 开始遍历，每一个点只遍历一次，这样就会构成一棵树，即 DFS 生成树。
这棵树上会有这么几种边：
- 树边：每次由⼀个已遍历的点到达未遍历的点，就形成了⼀条树边。
- 返祖边：也叫做回边，指向该节点的祖先。
- 横叉边：搜索时遇到⼀个已访问的节点，但这个节点并不是该节点的祖先。
- 前向边：访问时遇到⼦树中的节点时形成的。
举个栗子，如图：
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
6
0- 0
已为社区贡献1条内容
所有评论(0)