搜素:
遍历出给定元素所有的排序可能。
1.DFS(深度优先搜索)
(先往深处走)
使用的数据结构:栈
时间复杂度:O(h)
使用条件:n≤30 (为该题数据量)
图片示例:
即由不同的起始点逐次的向下遍历
dfs又名暴搜,故名思意,就是十分暴力的穷尽所有的可能性,然后进行查找,看是否存在我们需要的情况
dfs的遍历方式由上图可见,即树形搜索。我们先寻找一个起点(这个起点可以是遍历所有情况,也可以是我们已知的,anyway ,然后在去寻找起点后的下一个符合我们需求的点,如果找到,就向下继续重复操作,直到重复到遍历完所有数据,然后再看数据是否符合我们的需要,若需要,则记录下来,接着再退回到上一层,去看其他在之前搜索中没有尝试过的情况,直到重复完所有的可能。
1.记录操作的实现:我们使用bool数组来记录每个节点是否使用过,由于我们全程只使用一个bool数组来记录是否使用过该数据,所以当退回到上一层前时,我们需要重置我们对该层使用的节点的记录。(注意:我们记录的是该数据有没有使用过,而不是在该层中有没有用到);
2.剪枝:所谓剪枝,即删除我们原本树状结构的部分可能性。那么为什么要删除呢,由于我们朴素的dfs是先纵向再横向的方式遍历所有情况,而在纵向遍历的过程中,可能当我们不用遍历完就已经知道该情况不行了,这时我们只需要对条件判断一下,如果不符合直接退回到上一层即可
小模版
bool test[N].....; //检查是否使用过该点
int x[N],y[N]; //记录数据,用于未来输出
void dfs(int n...) //n为当前已经排了几个数,若有其他需要使用的变量,可创建其他变量输入到函数中
{
if(n==k){ //此处k为共要排的数的数量,若满足条件,则停止递归
........... //此处为终止前要执行的指令
return;
}
for(;;;){ //继续递归,若要剪枝则可用if语句判断一下。for语句进入多个平行轮数的递归
........... //此处为数据在进入下一次递归前作出的数据变化
dfs(n+1); //传入变化后的数据
........... //将原本的数据还原,以便于上一层递归平行轮数的递归正常使用数据
}
}
2.BFS(宽度优先搜索)
(先往宽处走)
使用的数据结构:队列
时间复杂度:O(2^h)
使用条件:题目要求寻找一个最小/最短的情况
图示
bfs本质上是对于图进行一层层的搜索,这样做的结果是,BFS 算法找到的路径是从起点开始的 最短 合法路径(按照层的顺序进行查找就是最快的了)。换言之,这条路径所包含的边数最小。在 BFS 结束时,每个节点都是通过从起点到该点的最短路径访问的。
由于我们的bfs算法不需要多次回溯,因此不需要st数组
抽象模板
int d[n][n]; //可以存储当前点到原点的距离(层数)
pair<int ,int> q[n*n]; //队列中点的数量开为平方倍
int bfs(){
int hh=0,tt=0; //初始化
q[0]={0,0}; //初始化第一个坐标
memset(d,-1,sizeof d); //初始化d数组
d[0][0]=0 //初始化起点距离
while(hh<=tt){
auto t=q[h++]; //取出头节点,一次循环至多hh自增一次,而只有当前节点的下一层的数据全部存在q中才会进入新的循环,因此下一轮循环还会进入本层的其余节点(或是无其余节点,直接进入下一层)。故而便达到了依次逐层查询的结果
for(;;;){ //对t所记录的内容进行更改,以达到搜索同层所有尾节点的操作
if(){ //当上方的更改合法时进行后续操作
............ //可以记录一些数据,比如将到起点距离(层数)记录在d中
q[++tt]={x,y}; //让tt自增,再将新的数据记录在q中,从而使下一轮循环中t可以去到下层节点。由此我们也能看出,只有无下一层时,tt才无法自增,循环hh才可能>tt,进而使循环结束
}
}
}
}
下面我们用一个题目来理解最短路问题。
题目链接:844. 走迷宫 - AcWing题库
给定一个 n×m的二维整数数组,用来表示一个迷宫,数组中只包含 0或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。
最初,有一个人位于左上角(1,1) 处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问,该人从左上角移动至右下角 (n,m) 处,至少需要移动多少次。
数据保证 (1,1) 处和 (n,m) 处的数字为 0,且一定至少存在一条通路。
输入格式
第一行包含两个整数 n和 m
接下来 n 行,每行包含 m个整数(0 或 1),表示完整的二维数组迷宫。
输出格式
输出一个整数,表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤1001
输入样例:
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例:
8
代码实现:
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n,m;
int g[N][N]; //存储图
int d[N][N]; //存储图上每个点到起点的距离
PII q[N*N]; //使用数组模拟队列,利用对组来储存坐标(x,y),仍然默认所有数据为0
int bfs(){
int hh=0,tt=0;//hh表示当前使用的为队列中的hh号数据,tt表示队列中总共有多少个数据
q[0]={0,0} //将起点放入队列当中
memset{d,-1,sizeof d}; //初始化距离数组,当的值为-1时,表示该点尚未走过
d[0][0] = 0; //初始化起点到起点的距离
int dx[4]={ -1,0,1,0},dy[4]={0,1,0,-1}; //四向法对坐标点进行变化
while (hh<=tt){ //当队列中仍然存在数据,则可继续bfs
auto t=q[hh++] ; //取出队列中的下一个坐标,并且对hh进行自增表示队列中数据的减少
for(int i=0;i<4;i++){ //向四个方向遍历
int x=t.first+dx[i], y=t.second+dy[i]; //对t的x,y分别进行变化
if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1){ //x和y的坐标必须合法且当前点必须非墙,且当前点未走过(若先一步走过则说明当前不是最短路,则没有更新的必要)
d[x][y]=d[t.first][t.second]+1; //当前点到原点的距离为上个点的距离+1
q[++tt]={x,y}; //对tt++,表示后续的可能性+1
}
}
}
return d[n-1][m-1]; //返回到终点(即(n-1,m-1)的距离)
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
cin >> g[i][j]; //利用二维数组来存储图(迷宫)的坐标
cout << bfs() << endl;
}
3.数和图的存储与遍历
图的存储
ps:树是一种特殊的图,而图分为有向图(只能从a->b)和无向图(a<->b),易得无向图是特殊的有向图(a,b间两条路,对于存储无向图,只要将两个点 非别为对方的终点存储一遍即可)
代码实现
//h[N] : 下标存储头节点的名称(头节点是谁,后面表示为H),元素存储最后一个插入到该节点上的节点的编号
//ne[M]: 下标存储该元素的编号,元素存储的为与该节点插入在同一个头节点上的节点。
//e[M] : 下标存储该元素的编号,元素存储该元素是谁
//idx : 插入过程中的计数器,在插入过程中不断跟跟新,且更新前值表示为当前插入节点的编号,跟新后的值为还未插入的节点的编号
int h[N], e[M], ne[M], idx; //初始化变量,栈空间中会自动初始化为0
memset(h, -1, sizeof h); //初始化节点数组(写在函数中)
//实现加入一条边;add(a,b)
//双向边则(a,b) (b,a)
//用数组记录数据时,如果一个数据被替代,则表示原数据被删除
//idx的初始化数据未0所以我们用0来表示第一个被插入的数据
void add(int start,int end){
e[idx] = end; // 将第一个编号并记录到数组e的下标中,并将其名称存储到当前下标所对应的元素
ne[idx] = h[start]; // 将该数组的上一个数组的编号(即为当前h[start]表示的值)记录到ne数组中
h[start] = idx++; // 将头节点(start)记录在h数组的下标中,并将当前头节点连的元素更新
//( 等价于:
// h[start]=idx;
// idx++;
// )
//idx++,会先将idx赋值给h数组,再对idx进行更新,所以每次在插入新数据时使用的h[start]即为更新前的idx。
//在一次插入中,idx更新前的数据(即h[start])为要插入的元素所对应的编号
//注意:节点的名称始终从1开始,因为h[0]要存放-1,用于表示该节点上连接的所有节点均已遍历完毕
//注意:我们的编号均从0开始
//注意ne数组的元素若为h数组初始化的值,则表示该节点无上一个连接同一头节点的节点
//注意:h数组的下标永远不会表示出度为0的节点,e数组中的元素永远不会含有入度为0的元素
}
图的宽度优先遍历
const int N;
int e[N],ne[n],h[n],idx;
bool ts[N]; //ts数组下标表示节点名称,其元素表示该节点有无被遍历过
memset(h,-1,sizeof h);
void add(int start,int end){
e[idx]=end,ne[idx]=h[start],h[start]=idx++;
}
void bfs(){
queue<int> q; //使用对列来进行bfs
q.push(root); //root表示起点
while(q.size()){
int t=q.front();
q.pop();
for(int i=h[t],i!=-1,i=ne[i]){
int j=e[i];
if(ts[j]) q.push(j);
}
}
}
图的深度优先遍历
const int N;
int h[N],e[N],ne[N],idx;
bool st[N];
void add(int a,int t){
e[idx]=t;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs(int u){ //传入起点
st[u]=true;
for(int i=h[u],i!=-1,i=ne[i]){ //当i=-1时,说明该节点连接的节点遍历完毕
int j=e[i];
if(!st[j]) dfs(j); //将每一个节点均向下寻找。
}
}
PS:
在某些问题中,我们不需要遍历图中所有部分,所以我们可以给最外层循环加上条件,但基本得遍历思路不变
4.拓扑排序
概念补充:能拓扑排序的图,一定是有向无环图;如果有环则一定不能拓扑排序。同样的,只要一个图是有向无环图,则该图一定可以拓扑排序。
拓扑排序定义:若一个由图中所有点构成的线性序列 A 满足:对于图中的每条边 (x,y)[向量表示法],x在线性排序A中都出现在 y之前,则称 A是该图的一个拓扑序列。
度的定义:
出度:对于一个点,他指向别的点的边的数量称为出度
入度:对于一个点,别的点指向它的边的数量称为入度
左图:有向有环图 右图:该图的简单图
环:由头节点向后指,最后又会指回头节点的图叫做环
示例:
该图的拓扑排序即为 123
注意 一个有向无环图的拓扑排序不一定唯一
示例:
该图的拓扑排序为123或132
代码实现
给定一个 n个点 m条边的有向图,点的编号是 1 到 n,图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 −1。
若一个由图中所有点构成的序列 A满足:对于图中的每条边 (x,y),x 在 A 中都出现在 y 之前,则称 A 是该图的一个拓扑序列。
输入格式
第一行包含两个整数 n和 m。
接下来 m行,每行包含两个整数 x 和 y,表示存在一条从点 x 到点 y 的有向边 (x,y)。
输出格式
共一行,如果存在拓扑序列,则输出任意一个合法的拓扑序列即可。
否则输出 −1。
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx; //存储图模板(构建双重链表)
int d[N]; //存储点的入度
int q[N]; //模拟队列
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++
}
bool topsort(){ //一股子bfs的味
int hh=0,tt=-1; //hh==head tt==tail 初始化头节点与尾节点
for(int i=1;i<=n;i++){
if(!d[i]) q[++t]=i; //如果该点入度为0 则输入到队列,同时将tt++,即表示尾节点数量,同时将尾节点输入到队列中
}
while(hh<=tt){ //只有存在入度为0的点的图才为有向无环图
int t=q[hh++]; //依次取出度数为0的点,即遍历队列
for(int i=h[t];i!=-1;i=ne[i]){ //遍历链表模板
int j=e[i]; //用j来记录尾节点
d[j]--;
if(d[j]==0) q[++t]=j; //如果该节点的尾节点的度数为1(即除了该节点外无其余节点指向该节点) 则将将该点计入队列。 若不为1,则将该店的入度-1(表示他目前在这个队列中的位置已经在这个点的后方了,但若入度不为0,这说明还有其他的点在可能未在他的前方,当入度为0时,表示所有点均在他的前方,此时我们便可以2让他入队),但若入度尚不为0,则不计入队列。
}
}
return t==n-1; //判断是否所有点均入队,若是,则说明该图存在拓扑序
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
d[b] ++ ;
}
if (!topsort()) puts("-1");
else
{
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
puts("");
}
return 0;
}
稠密图:邻接矩阵
稀疏图:邻接表
n:点数 m:边数
m=n^2--->稠密图-->邻接矩阵
m=n------>稀疏图-->邻接表
eg.
1≤n≤500,1≤m≤10^5^,m近似于n^2^,为稠密图,用邻接矩阵
1≤n,m≤1.5×10^5^,m近似于n,为稀疏图,用邻接表
最短路算法 (不区分有向图与无向图)
考察点:如何将题目抽象为最短路问题,并且将题目内容如何抽象为图
一. 单源最短路———所有边权均为正数
Dijkstar算法
基本思路:
拿到起点,从起点处向下搜索,找出所有与起点可达的点(表示为d[ i ] 不为0,或d[上一个]+w 不为0)中最短的点,然后再将该点作为起点继续向后寻找相连的点,并记录后续点到真起点的距离(此时若一个点的入度不为1,则将其到真起点的距离记录为该点到真起点的最短距离),然后重复该操作直到找到终点,此时终点到起点的距离即为最短距离
朴素Dijkstar算法
解决稠密图 O(n^2) 使用临界矩阵存储稠密图
#include <iostream>
#include <cstring>
using namespace std;
const int N;
int n,m;
int g[N][N]; //临接矩阵存放图,其中第一维为终点,第二维为起点,存放数据为边权
int d[N]; //下标表示点的名称,元素存放该点到起点的距离
bool st[N]; //state:状态
int Dijkstar(){
memset(d,0x3f,sizeof d); //先将所有的边到起点的距离设置为无限大
d[1]=0; //再将起点到自己的距离设置为0
for(int i=0;i<n;i++){ //循环n次,用于穷尽所有的点,所以st始终会使用所有点
int t=-1; //让t表示我们在本轮循环中要寻找的距离起点最近的点的名称
for(int j=1;j<=n;j++){ //遍历所有点
if(!st[j]&&(t==-1||d[t]>d[j])) //j>t;
t=j; //如果该点没用过,且目前尚未找到最短点(t==-1)则,将t标记为j,如果后续存在比j到起点 距离更短的点,则将其t更新
}
st[t]=true; //更新t的状态为使用过
for(int j=1;j<=n;j++){ //遍历所有的点
d[j]=min(d[j],d[t]+g[t][j]);
//d[j]表示目前j到起点的最短距离,如果换路线为先从起点走到t再从t走到j,则更新j到起点的最短距离
//由代码我们不难发现,在该次循环中,我们只能更新与本次选出的最短点t直接相连的点。
//因此存在一种情况:若终点已被所有与他相连的点遍历过,则后续的所有点在执行本轮时一定不会更新终点.
//但是若存在负权边,则可能存在连走两个点比走一个点短的情况,因此存在负权边无法使用Dijkstar算法
}
}
if(d[n]==0x3f3f3f3f) return -1;
return d[n];
}
int main(){
cin>>n>>m;
memset(g,0x3f,sizeof g); //将所有边的权初始化为最大,用于在后面过程中将权重取重边中的最小值
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
}
cout<<Dijkstar();
}
注意
关于初始化及其含义
输入完后,若权重为无穷大(用max表示),则说明该两点间无相连路径。
关于遍历的过程
在第一轮循环中,我们一定会取出起点(唯一距离非max的点),然后在更新d的循环中,我们便会将所有与起点路径的点所对应的d数组的元素全部更新为该点到起点的权重。
(注释:此时d[ j ]=max,d[ t ]=0 若g[ t ] [ j ] 不为max,既可以完成更新,将此时的d[ j ]不再标记为max)
第二轮中,后面的点已经有一部分的d不为无穷大,所以第二轮中取出的点一定是这些点中到起点距离最短的点,然后再进行更新
第三轮中,此时我们就要在与起点直连的点或隔一个点相连的点中寻找距离最短的点,再用它去更新
以此类推,完成Dijkstar算法
存在的问题
Dijkstar算法每次只能更新一个点与他直连的点到起点的距离,但若存在负权边,则可能两条路之和小于一条路径长,这种情况使用Dijkstar算法无法检测到,因此存在负权边无法使用Dijkstar算法。
堆优化版的Dijkstar算法
O(mlogn) 使用数据结构:优先队列 用于解决稀疏图的单源最短路问题
代码实现
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N;
typedef pair<int ,int> PII;
int n,m;
int h[N],e[N*2],ne[N*2],w[N*2],idx;
int d[N];
bool st[N];
void add(int a,int b,int c){
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx++;
}
int Dijkstar(){
priority_queue<PII,vector<PII>,greater<PII>> heap;
memset(d,0x3f,sizeof d);
d[1]=0;
heap.push({0,1});
while(heap.size()){
PII t=heap.top();
heap.pop();
int root=t.second,dist=t.first;
if(st[root]) continue;
st[root]=true;
for(int i=h[root];i!=-1;i=ne[i]){
int j=e[i];
if(d[j]>d[root]+w[i]){
d[j]=d[root]+w[i];
heap.push({d[j],j});
}
}
}
if(d[n]==0x3f3f3f3f) return -1;
return d[n];
}
int main(){
memset(h,-1,sizeof h);
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
cout<<Dijkstar();
}
bellman—ford算法
PS:对于一个图, 若存在负权边,则不一定存在最短路,当负环不在起点到终点的任意一条路径上时,则存在,否则不存在。
时间复杂度: O(nm)
有边数限制(即限制经过多少次边)的最短路问题一般使用BF算法
过程
BellmanFord算法在遍历思路上与Dijkstar算法的不同处在于Dijkstar算法是在每次循环的顺序中寻找到起点距离最短的点,再用它去更新与他相邻的所有点。而BellmanFord算法则是一层一层的更新(即先更新直链起点的点到起点的距离,在更新隔一个点到起点的点到起点的距离),每一次都记录下起点到当前点的最短距离,直到找到最短路径
代码实现
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=510,M=10010;
int n,m,k;
int dist[N],last[N];
struct edge{
int e,ne,w;
} edges[M];
void bellmanFord(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<k;i++){
memcpy(last,dist,sizeof dist);
for(int j=0;i<m;i++){ //遍历了所有的边
d[edges[j].ne]=min(dist[edges[j].ne],last[edges[j].e]+edges[j].w);//在遍历的过程中,我们仅对last[edges[j].e]+edges[j].w<dist[edges[j].ne]的情况进行更新,这时就存在两种情况、
//1.last[edges[j].e]与dist[edges[j].ne]中一者为无穷大一者非无穷大(即我们希望的情况,二者中存在一者已被更新(与起点可达))
//2.last[edges[j].e]与dist[edges[j].ne]均为无穷大但edges[j].w<0,由于我们的无穷大是假无穷大,所以此时也会被更新,但此次更新并不能表示可达(这也是造成后续需要判定<0x3f3f3f3f/2的原因)
}
}
}
int main(){
cin>>n>>m>>k;
for(int i=0;i<m;i++){
cin>>edges[i].e>>edges[i].ne>>edges[i].w;
}
bellmanFord();
if(d[n]>0x3f3f3f3f/2) cout<<"impossible"; //此处之所以大于0x3f3f3f3f/2是因为在改图中存在负权边,若相邻两点间存在负权边,则该点可能会被替换为比0x3f3f3f3f更小一点的数,但是由于我们用0x3f3f3f3f表示的是无穷大,无穷大减去一个数理应还是无穷大,故我们将原本的等于条件放宽到>/2即可
else cout<<d[n];
}
SPFA算法
解决有负权边且图中没有负环的问题
SPFA算法要求图中一定不存在负环
时间复杂度:一般 O(m) 最坏O(nm)
注意
SPFA算法若不被特殊数据卡住,则其效率会明显高于Dijkstar算法,但若题目有意卡住SPFA,则只能使用堆优化版Dijkstar算法
基本思路
SPFA算法的基本思路本质上就是优化版的BellmanFord算法,优于不存在负环,所以我们可以直接删掉last数组。
由代码不难看出,若BellmanFord若想更新下一层数据,必须保证与他直连的上一层数据的dist已被更新,由此,我们便可以用bfs来对BellmanFord算法进行优化
先将起点放入队列,再将起点相连的点放入队列,再用其去更新后续点,由于每次更新时都进行一次比较,因此由上一层所有点将下一层点更新完后,下一层点的所有dist即为最短距离
在这样的一顿操作中我们就保证了SPFA只会更新与起点可达的点,而不需愚蠢的遍历所有的边同时使用min来进行更新判断是否可达,因此不可达的点永远不会被更新(始终为0x3f3f3f3f)
代码实现
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N=100010,M=2*N;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];
void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
int SPFA(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
queue<int> q;
q.push(1);
st[1]=true; //表示当前点是否在队列中
while(!q.empty()){
int j=q.front();
q.pop();
st[j]=false; //表示点已经不在对列中
for(int i=h[j];i!=-1;i=ne[i]){
int k=e[i];
if(dist[k]>dist[j]+w[i]){
dist[k]=dist[j]+w[i];
if(!st[k]) {
q.push(k); //如果该点被更新,则说明他后续的点全部需要被更新,因此他应该在队列中,但如果他已经在队列中,则不需要进行该操作,这一行操作本身就是在应对两个点路径之和小于一个点的路径的情况,但如果全是正权边,则不可能出现走环(向回绕)比直接走路程近的情况。
st[k]=true;
}
}
}
}
return dist[n];
}
int main(){
memset(h,-1,sizeof h);
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
int t=SPFA();
if(t==0x3f3f3f3f) cout<<"impossible";//Bellman_ford算法里最后return-1的判断条件写的是dist[n]>0x3f3f3f3f/2;而spfa算法写的是dist[n]==0x3f3f3f3f;其原因在于Bellman_ford算法会遍历所有的边,因此不管是不是和源点连通的边它都会得到更新;但是SPFA算法不一样,它相当于采用了BFS,因此遍历到的结点都是与源点连通的,因此如果你要求的n和源点不连通,它不会得到更新,还是保持的0x3f3f3f3f。
cout<<t;
}
应用:使用SPFA算法寻找图中是否存在负环
介绍
SPFA查找负环的方法与SPFA寻找最短路最大的去别在于我们不需要对dist数组进行初始化操作,因为我们的目的是寻找负环,若存在负环,则至少两个点相连的边的权为负值,我们只需要找到那个点即可,所以我们最开始将所有的点全部放入队列,由于dist数组的所有数据全部为0,所以只有存在负权边的情况才会将后续点保存到对列中。
若进入到一个负环中,那么我们的代码会一直在换中向后查找,直到运行到我们设置的终点(出现一个点到虚拟起点之间经过了超越总点数数量的边(此处卡了最大,其实对于一个环,经过的边数只要大于环的点数即可认为是负环,但我们此时无法判断负环中有多少点,因此只能用这个方法来卡一个最大(图中环的点数再大不超过环的点数)))
代码实现
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=2010,M=10010;
int n,m;
int h[N],ne[M],e[M],w[M],idx;
int dist[N],cnt[N];
bool st[N];
void add(int a,int b,int c){
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx++;
}
bool SPFA(){
queue<int> q;
for(int i=1;i<=n;i++){
q.push(i);
st[i]=true;//将每个点放入到我们的队列中,这些点就是我们的虚拟起点
}
while(!q.empty()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[t]+w[i]) { //只要相邻的两个边为边即可进入到这个
dist[j]=dist[t]+w[i];//dist的最大值为0(初始化为0,若d+w>d>=0不会更新)。后面若出现负环,则始终会在这个环中查找
cnt[j]=cnt[t]+1;
if(cnt[j]>n) return true;
if(!st[j]) {
q.push(j);
st[j]=true;
}
}
}
}
return false;
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
if(SPFA()) cout<<"Yes";
else cout<<"No";
}
floyd算法
时间复杂度 O(n^3)
介绍
floyd算法基于动态规划的方法,对图中所有节点进行三轮循环( k i j ),在循环中对 i j 两个点进行更新。
其基本思路在于,对于已知可达的两个点 i->j,我们如何来寻找其更短的路?
答案是引入第三个点k,即将原本的路变为i->k->j,如果i->k+k->j小于i->j我们便对i j 间距离进行更新
在使用动态规划,所以我们还是使用我们最熟悉的方式,即遍历所有情况进而对整张图进行更新
代码实现
#include <iostream>
using namespace std;
int n,m,t;
const int N=210,INF=0x3f3f3f3f;
int g[N][N];
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=min(g[i][j],g[i][k]+g[k][j]); //三层循环将图的所有点更新了n次,每次都在使用k去更新
}
}
}
}
int main(){
cin>>n>>m>>t;
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
if (i == j) g[i][j] = 0;
else g[i][j] = INF;
while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
}
floyd();
while(t--){
int s,e;
cin>>s>>e;
if(g[s][e]>INF/2) cout<<"impossible"<<endl; //与BellmanFord算法一样,由于遍历所有边,所以可能存在不可达但变小的可能性
else cout<<g[s][e]<<endl;
}
}
最小生成树问题
必备知识
首先我们需要明确几点
1.生成树是建立在无向图中的,对于有向图,则没有生成树的概念。在此基础上我们便可以明确,所谓生成树,实际上便是在一个图中寻找一个树状结构,且该树要包含图中所有点,而最小生成树即该生成树的边权之和为所有生成树中最小的即可。
2.由1我们不难发现,一个无向图若想存在最小生成树则需要满足该图为连通图.而最小生成树中一定不需要自环
此时该连通块就是我们的最小生成树
朴素版的prim算法
时间复杂度 O(mlogn) 解决稠密图的最小生成树问题
思路
由1我们不难发现,我们只需要先从图中选择任意一点(我们后续称为假根节点),将其放入连通块中,第一轮中(此时连通块只有一个点,即我们第一轮的假根节点)我们向下寻找所有与假根节点相连的点(即与连通块相连的点),然后用这些点与假根节点的距离去更新这些点与连通块的距离。接着我们再拿/剩余的/与连通块相连的点中/与连通块距离(我们认为一个点与连通块中距离最近的点间的距离为带点到连通块的距离)最近的点/作为新的假根节点(此时我们可以确定他一定是最小生成树的一部分),将其和其与连通块相连的边放入连通块中,再拿他去更新剩余未在连通块的所有点,不断循环,直到所有点都在连通块中。
代码实现
#include <iostream>
#include <cstring>
using namespace std;
const int N=510;
int g[N][N];
int dist[N];
bool st[N];
int res;
int n,m;
void prim() {
memset(dist, 0x3f, sizeof dist); //
dist[1] = 0;
for (int i = 0; i < n; i++) {
int t = -1;
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j])) {
t = j;
}
}
if (dist[t] == 0x3f3f3f3f) { //如果我们的t被更新为一个与连通块不连通的点,说明这个图中存在孤立点,即该图无最小生成树
res=dist[t];
return;
}
st[t] = true; //将t放入连通块中
res += dist[t]; //将t在最小生成树对应的边放入连通块中
for (int j = 1; j <= n; j++) {
if (!st[j] && dist[j] > g[t][j]) { //这一步始于Dijkstar算法差异最大的一步,此处我们需要根据连通块距离判断是否更新
dist[j] = g[t][j]; //如果j不在连通块中且j到连通块的距离小于t与j间距离,则更新j到连通块距离
}
}
}
}
int main(){
memset(g,0x3f,sizeof g);
cin>>n>>m;
while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
prim();
if(res!=0x3f3f3f3f) cout<<res;
else cout<<"impossible";
}
Kruskal算法
思路
Kruskal算法采用的是一个极为简单的寻找最小生成树的思路
我们先去寻找一个图中权值最小的一条边,用它来创建我们的最小生成树的雏形,接着我们再去按边权的大小去寻找其他边,只要该边不是我们的雏形中某两点间的重边,我们便将他放到我们的雏形中(注意,在这个过程中,我们的雏形可能不是连通图,但并没有关系,只要最后他是连通图的形式即可 )。
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010,M=2*N;
struct edge{
int a,b,c;
bool operator <(const edge &tmp) const{
>c<tmp.c;
}
}edges[M];
int res;
int n,m;
int cnt;
int p[N];
int find(int a){
if(p[a]!=a) p[a]=find(p[a]);
return p[a];
}
void Kruskal(){
for(int i=1;i<=m;i++){
int a=edges[i].a;
int b=edges[i].b;
a=find(a),b=find(b);
if(a!=b){
p[a]=b;
res+=edges[i].c;
cnt++;
}
}
if(cnt==n-1) cout<<res;
else cout<<"impossible";
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
edges[i].a=a;
edges[i].b=b;
edges[i].c=c;
}
sort(edges+1,edges+m+1);
Kruskal();
cout<<cnt;
cout<<endl<<res;
}