可恶啊,还没写完/(ㄒoㄒ)/~~
先就这样吧,需要补充的以后再补充先逃了ε=ε=ε=┏(゜ロ゜;)┛
谁曾想,这一章内容这么多
2022.08.08更新 已完结,欢迎交流
目录
- 树与图的深度优先遍历
- 树与图的广度优先遍历
- 拓扑排序
- 单源最短路 (dijkstr算法,堆优化dijkstra算法,bellman-ford算法,SPFA算法)
- 多源汇最短路 (floyd算法)
- 最小生成树(kruskal算法,prim算法)
- 图二分 (染色法,匈牙利算法)
观察下面两种遍历类型我们可以发现,dfs使用到了数据结构栈(由计算机内部实现),bfs用到了数据结构队列。看起来是dfs更加简单,其实是因为,dfs用到的栈在计算机内部实现了,而bfs用到的队列是要自己写出来,所以,bfs代码要多一些。两者的时间复杂度都是O(m+n),其中n是点数,m是边数。
时间复杂度分析:
首先,图中每个结点最多被遍历一次,这是因为当某个结点被遍历到后,就会对其进行标记,下次再搜索到该结点时就不会再从这个结点进行搜索,所以每个结点最多调用一次dfs函数,所以这里的时间复杂度为O(n)。遍历图的本质是遍历每个结点的邻接结点,也就是说,当从一个结点开始,去遍历其他结点时,都要对该结点的邻接结点遍历一次。因此对于每个结点来说,遍历其邻接结点的时间复杂度为O(ei),这里的ei是指第i个结点与其邻接结点相连的边的数量。所以,遍历整一个图的时间复杂度就是把每一个结点进行深度优先遍历的时间复杂度加起来,也就是O(n+e),即所有结点和所有边的数量。
树与图的深度优先遍历
下面的第一个函数是dfs的框架,在其中加上一些细节,我们可以求到其他的信息如树的dfs序(用a数组存储),树的深度(用数组d存储)。在dfs序中,相同的两个值之间的区间就是一棵树。
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N*2],d[N];
int h[N],ne[N],ver[N],v[N],idx;//v是visit的缩写,表示下标为i的点是否访问
//以下是深度优先遍历框架,加入不同细节可实现不同功能。
//时间复杂度是O(n+m),n是点的个数,m是边的个数。每个单向边访问一次。
void dfs(int x)
{
v[x]=1;//访问过,标记一下
for(int i=h[x];i;i=ne[i])//遍历x节点后面的节点
{
int y=ver[i];
if(v[y])continue;//如果这个点被访问过,跳过这个点
dfs(y);//没有被访问过,顺着这个点往下访问
}
}
//树的dfs序,用数组a来进行存储
void dfs(int x)
{
a[m++]=x;//向下搜时遇到
v[x]=1;
for(int i=h[x];i;i=next[i])
{
int y=ver[i];
if(v[y])continue;
dfs(y);
}
a[m++]=x;//回溯时遇到的顺序
}
//求树各点的深度d,同时用d来表示该点是否访问过省去了数组v,当然,注意根节点深度为1.
void dfs(int x)
{
v[x]=1;
for(int i=h[x];i;i=next[i])
{
int y=ver[i];
if(d[y])continue;
d[y]=d[x]+1;//从父节点x到子节点y递推,计算深度
dfs(y);
}
}
//图的连通块的划分
void dfs(int x)
{
v[x]=cnt;
for(int i=h[x];i;i=next[i])
{
int y=ver[i];
if(v[y])continue;
dfs(y);
}
}
int main()
{
for(int i=1;i<=n;i++)
{
if(!v[i])
{
cnt++;
dfs(i);//每一次深搜,我们就会把一块连通区域标记为同一个数cnt[i];
}
}
}
树与图的广度优先遍历
void bfs()
{
memset(d,0,sizeof(d));//d数字存储深度,同时也可用d来判断是否遍历过某个点
queue<int>q;
q.push(1);
d[1]=1;
while(q.size()>0)//当q为空时,说明图遍历完毕
{
int x=q.front();q.pop();
for(int i=h[x];i;i=ne[i])//循环该点的每个终点
{
int y=ver[i];//ver数组存储终点
if(d[y])continue;
d[y]=d[x]+1;
q.push(y);
}
}
}
拓扑排序
一个有向无环图是一定存在拓扑排序的,我们也常用拓扑排序来判断一个图是否有环。任何一个有向无环图都存在拓扑序,反过来也成立,他们互为充要条件,我们便可以据此统计一张有向无环图中,从每个点出发能够到达的点的数量
//拓扑排序
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int h[N],ne[N],ver[N],deg[N],a[N],idx,cnt;//degree 度,这里a数组储存拓扑序
int n,m;//分别为点数和边数
void add(int x,int y)
{
ver[++idx]=y;
deg[y]++;
ne[idx]=h[x];
h[x]=idx;
}
void topsort()
{
queue<int>q;
for(int i=1;i<=n;i++)
{
if(deg[i]==0)q.push(i);
}
while(q.size())
{
int x=q.front();q.pop();
a[++cnt]=x;//拓扑排序,下标从1开始或者从0开始均可,权由这里决定
for(int i=h[x];i;i=ne[i])
{
int y=ver[i];
if(--deg[y]==0)q.push(y);
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
add(x,y);
}
topsort();
for(int i=1;i<=cnt;i++)
{
cout<<a[i]<<endl;
}
}
单源最短路
dijkstra算法
该算法的时间复杂度为O($n^2$),主要的瓶颈在于寻找最小值的过程。这时候我们可以很自然的想到用堆来动态维护最小值,使得时间复杂度为O(mlogn)(实际上是O((m+n)logn,但当m规模不小于n时可忽略简写)
算法流程如下:
1.初始化dist[1]=0,其余节点的dist值为无穷大。
2.找出一个未被标记的,并且dist[x],最小的节点下x,然后标记节点x。
3.扫描节点x的所有出边(x,y,z),若dist[y]>dist[x]+z,则使用dist[x]+z更新dist[y].
4.重复上述2~3的步骤,直到所有的节点都被标记。
当然了,算法要求每条边都非负,该算法基于贪心的思想。代码附上:
- dijkstra 算法:
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N][N],d[N],n,m;//a数组储存图,d数组储存距离
bool v[N];//v数组表示i点是否被标记
void dijkstra()
{
memset(d,0x3f,sizeof(d));//dist数组 distance 距离
memset(v,0,sizeof(v));
d[1]=0;
//这里循环了n-1次,是因为每次循环都会标记一个点,用该点更新其他点,
//最后一次循环后还有一个未标记,但已经被更新了,在循环一次不会有任何改变,所以省去了
for(int i=1;i<n;i++)
{
int x=0;
//寻找d数组中未标记的最小值
for(int j=1;j<=n;j++)
{
if(!v[j]&&(x==0||d[j]<d[x]))x=j;
}
v[x]=1;
//用全局最小值点x更新其他节点
for(int y=1;y<=n;y++)
{
d[y]=min(d[y],d[x]+a[x][y]);
}
}
}
int main()
{
//我们下标都是从1开始的,完全可以从0开始,只不过题目叙述就是下标从1开始,我们完全是投其所好
cin>>n>>m;
//构建邻接矩阵
memset(a,0x3f,sizeof(a));
for(int i=1;i<=n;i++)a[i][i]=0;//自己到自己的距离都为0
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
a[x][y]=min(a[x][y],z);//如果两个点之间有多条边,选取最短的一条
}
//求单源最短路径
dijkstra();
for(int i=1;i<=n;i++)
{
cout<<d[i]<<endl;
}
}
- 堆优化dijkstra算法:
#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=1000010;
int h[N],ver[M],e[M],ne[M],d[N];
bool v[N];
int n,m,idx;
//大根堆(优先队列),pair的第二维为节点编号
//pair的第一维为dist的相反数(利用相反数变成小根堆,非常巧妙)
priority_queue<pair<int,int>>q;
void add(int x,int y,int z)
{
ver[++idx]=y,e[idx]=z,ne[idx]=h[x],h[x]=idx;
}
void dijkstra()
{
memset(d,0x3f,sizeof(d));
memset(v,0,sizeof(v));
d[1]=0;
q.push({0,1});
while(q.size())
{
//取出栈顶
int x=q.top().second;q.pop();
if(v[x])continue;
v[x]=1;
//扫描所有出边
for(int i=h[x];i;i=ne[i])
{
int y=ver[i],z=e[i];
if(d[y]>d[x]+z)
{
//更新,把新的二元组插入堆
d[y]=d[x]+z;
q.push({-d[y],y});
}
}
}
}
int main()
{
cin>>n>>m;
//构建邻接表
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
}
//求单源最短路
dijkstra();
for(int i=1;i<=n;i++)
{
cout<<d[i]<<endl;
}
}
-
bellman-ford算法(时间复杂度为O($nm$))
1扫描所有边(x,y,z),若dist[y]>dist[x]+z,则用dist[x]+z更新dist[y]。
2.重复上述步骤,直到没有更新操作发生。 -
SPFA算法 :
在任意时刻,该算法的队列都保存了待扩展的节点,不许要扩展的节点不会入队,这就避免了bellm-ford算法中对不需要扩展的节点的冗余扫描,在随机图上的运行效率为O(km)级别,k是一个较小的常数。但是在特殊的构图上,该算法很可能退化为O(nm)。1.建立一个队列,最初队列中只有起点1
2.取出对头x,扫描他的所有出边(x,y,z),若dist[y]>dist[x]+z,则使用dist[x]+z更新dist[y]。同时,若y不在队列中则把y入队
3.重复上述步骤,直到队列为空。
#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=1000010;
int h[N],ver[M],e[M],ne[M],d[N];
int n,m,idx;
queue<int>q;
bool v[N];
void add(int x,int y,int z)
{
ver[++idx]=y,e[idx]=z,ne[idx]=h[x],h[x]=idx;
}
void spfa()
{
memset(d,0x3f,sizeof(d));//dist数组,记录距离
memset(v,0,sizeof(v));//判断某点是否在队列中
d[1]=0;v[1]=1;
q.push(1);
while(q.size())
{
//取出队头
int x=q.front();q.pop();
v[x]=0;//v表示该点是否在队列中,所以取出后v变成0,这是和dijkstra算法的区别
//扫描所有出边
for(int i=h[x];i;i=ne[i])
{
int y=ver[i],z=e[i];
if(d[y]>d[x]+z)
{
//若y不在队列中,把y入队
d[y]=d[x]+z;
if(!v[y])q.push(y),v[y]=1;
}
}
}
}
int main()
{
cin>>n>>m;
//构建邻接表
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
}
//求单源最短路
spfa();
for(int i=1;i<=n;i++)
{
cout<<d[i]<<endl;
}
}
任意两点间的最短路(多源最短路)
现在,我们来考虑如何求出图中任意两点间的最短路径,这时,我们可以可以把没个点作为起点,求解n次单源最短路,但是,很明显,时间复杂度会大很多,我们可以使用,时间复杂度为O($n^3$)的flody算法来求解。这里我们用到了动态规划的知识。
- floyd算法
首先,我们约定d[k,i,j]表示“经过若干编号不超过k的节点”从i到j的最短路长度。我们使用动态规划的方法就可以把这个状态分为两个子状态,即:
d[k-1,i,j]:经过编号不超过k-1的节点,从i到j的最短长度。
d[k-1,i,k]+d[k-1,k,j]:经过编号不超过k-1的节点从i到k的最短距离,加上编号不超k-1从k到j的距离。
然后,d[k,i,j]便是上面两个子问题的最小值。
我们可以把空间优化为2维,把第一维去掉,虽然我想了好久都想不通为什么,ok这问题留给你们了
#include<bits/stdc++.h>
int n,m,d[310][310];
using namespace std;
int main()
{
cin>>n>>m;
//用邻接矩阵来储存d数组
//d数组在充当了存储最短距离的同时,还用来存储图
//用邻接矩阵而不用邻接表的原因:题目一般会用稠密图,点比较少,边数多,邻接矩阵优势明显
memset(d,0x3f,sizeof(d));
for(int i=1;i<=n;i++)d[i][i]=0;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
d[x][y]=min(d[x][y],z);
}
//下面要出现我们的主角了,floyd算法代码较短,做好心理准备
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
//floyd完毕
//输出
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<d[i][j]<<" ";
}
}
}
最小生成树
ok,我们先来了解一下什么是最小生成树,给定一张边带权的无向图,n个点,m条边。由全部n个点和n-1条边构成的无向连通子图被称为原图的一颗生成树,而其中边的权值之和最小的生成树被称为,原图的最小生成树(mst),下面我们介绍一下算法都有的那些。
首先了解一个定理:任意一颗最小生成树一定包含无向图中权值最小的边。
- kruskal算法(克鲁斯卡尔算法)
1.建立并查集,每个点各自构成一个集合。
2.把所有边按照权值从小到大排序,一次扫描每条边(x,y,z)。
3.若x,y属于同一个集合(联通),则忽略这条边,继续扫描下一条边。
4.否则,合并x,y所在的集合,并把z累加到答案中。
5.所有边扫描完成后,第4步中处理过的边就构成最小生成树。
时间复杂度为O($mlogm$)。
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x,y,z;//x,y是边的两个点,z是边的权值。
}edge[500010];
int fa[100010],n,m,ans;
bool operator <(node a,node b)
{
return a.z<b.z;
}
int get(int x)
{
if(x==fa[x])return x;
return fa[x]=get(fa[x]);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>edge[i].x>>edge[i].y>>edge[i].z;
}
//按照边权排序
sort(edge+1,edge+m+1);
//并查集初始化
for(int i=1;i<=m;i++)fa[i]=i;
//求最小生成树
for(int i=1;i<=m;i++)
{
int x=get(edge[i].x);
int y=get(edge[i].y);
if(x==y)continue;
fa[x]=y;
ans+=edge[i].z;
}
cout<<ans<<endl;
}
- prim算法(普利姆算法)
prim算法的时间复杂度为($O(n^2)$)主要用于稠密图,尤其是完全二叉树的求解。
#include<bits/stdc++.h>
using namespace std;
//下面的d[i]数组比较考验理解,表示非生成树节点i到生成树(注意不是1号点)的最短距离
int a[3010][3010],d[3010],n,m,ans;
bool v[3010];
//下面prim算法非常弔,可以求出完全图的最小生成树,即可以求出任意节点i之前的最小生成树
void prim()
{
memset(d,0x3f,sizeof(v));
d[1]=0;
for(int i=1;i<n;i++)
{
int x=0;
for(int j=1;j<=n;j++)
{
if(!v[j]&&(x==0||d[j]<d[x]))x=j;//查找距离生成树最近的点
}
v[x]=1;
//新加入了一个点,维护一下其他点到生成树的最短距离
for(int y=1;y<=n;y++)
{
if(!v[y])d[y]=min(d[y],a[x][y]);
}
}
}
int main()
{
cin>>n>>m;
memset(a,0x3f,sizeof(a));
for(int i=1;i<=n;i++)a[i][i]=0;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
}
//求最小生成树
prim();
for(int i=2;i<=n;i++)ans+=d[i];
cout<<ans<<endl;
}
图二分
嗯,来到了我们的图二分环节,首先我们来了解一下什么是图二分。
如果是一张无向图的N个节点(N>=2)可以分成A,B两个非空集合,其中A与B的交集为空集。并且在同一集合内的点之间都没有边相连,那么称这张无向图为一张二分图。
下面,我们来了解一下二分图判定的染色法:
二分图判定----染色法
首先我们要知道,一张无向图是二分图,当且仅当图中不存在奇环(长度为奇数的环)。据此我们可以写出下面的代码:
//染色法判定二分图
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int color[N];//存储每个点的颜色,顺便用来判断是否染过该点
int h[N],ne[N],ver[N],idx;//h表示起点,ver表示终点,ne表示终点的下标,idx表示下标
void add(int x,int y)
{
ver[++idx]=y,ne[idx]=h[x],h[x]=idx;
}
bool dfs(int u,int c)//给u点染上颜色c
{
color[u]=c;
for(int i=h[u];i;i=ne[i])//给u点相邻的点染色
{
int x=ver[i];
if(!color[x])
{
if(!dfs(x,3-c))return 0;
}
else if(color[x]==c)return 0;
}
return 1;
}
int main()
{
cin>>n>>m;
while(m--)
{
int a,b;
cin>>a>>b;
add(a,b),add(b,a);//无向图加两条边
}
bool flag=1;//先立个flag
for(int i=1;i<=n;i++)
{
if(!color[i])//对每个连通块染色,但凡发现不符合的情况,flag=0
{
if(!dfs(i,1))
{
flag=0;
break;
}
}
}
if(flag)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
二分图的最大匹配
匈牙利算法(增光路算法)
首先我们要知道,二分图的一组最大匹配S,当且仅当图中不存在S的增广路时成立。
匈牙利算法:
1.设S为空集,即所有边都是非匹配边;
2.寻找增广路path,把路径上所有边的匹配状态取反,得到一个更大的匹配S’
3.重复步骤2,直至图中不存在增广路
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int h[N],ne[N],ver[N],idx;
int v[N],match[N];
int n,m,ans;//n是点数,m是边数。
void add(int x,int y)
{
ver[++idx]=y,ne[idx]=h[x],h[x]=idx;
}
//匈牙利算法,利用了深度优先搜索进行匹配
bool dfs(int x)
{
for(int i=h[x],y;i;i=ne[i])
if(!v[y=ver[i]])
{
v[y]=1;
if(!match[y]||dfs(match[y]))
{
match[y]=x;
return 1;
}
}
return 0;
}
int main()
{
cin>>n>>m;
while(m--)
{
int a,b;
cin>>a>>b;
add(a,b);
}
//每一个点在循环过程中会尽量匹配,匹配上的可能在后面循环过程中更换匹配对象,但觉对保证有匹配
for(int i=1;i<=n;i++)
{
memset(v,0,sizeof(v));//每次都要初始化
if(dfs(i))ans++;//因为每一次增广路算法会消除一个增广路,而每消除一个增广路,匹配总数就会加一
}
cout<<ans<<endl;
}
番外:最大公因数可以用欧几里得算法得出,最小公倍数为两个数的乘积除最大公因数。