1. AI技术聚合首页
  2. IT

acwing算法全总结——搜索与图论

扎眼的阳光 • • IT • 阅读 25

acwing算法全总结——搜索与图论

    • dfs
    • bfs
    • 树与图的深度优先遍历
    • 树与图的广度优先遍历
    • 拓扑排序
    • 最短路问题
      • dijkstra最短路
      • bellman-ford最短路
      • spfa最短路
      • floyd最短路
    • 最小生成树
      • prim最小生成树
      • kruskal最小生成树
    • 二分图

搜索与图论这一章算是对数据结构与算法的进阶提升吧，它相较于栈和队列比较难以实现和想象，本章主要说明dfs（深度优先搜索），bfs（广度优先搜索），树与图的优先遍历以及二分图，最短路问题，目录如下:

dfs

一：dfs深度优先搜索
题目链接：链接:n皇后问题
代码如下：

 /*1.两个return作为递归的结束标志，用来返回，以及树是如何建成的，还有对角线，以及回溯*/
#include<iostream>
using namespace std;
const int N=10;;
int n;
bool row[N],col[N],dg[N*2],udg[N*2];//这是行，列，以及斜边的布尔变量，
char g[N][N];
void dfs(int x,int y,int s){
    if(s>n)return;//s计数，走到尽头退出递归
    if(y==n)y=0,x++;//直接位移到下一行的第一位
    if(x==n){//这里还是一个特判，成功了 才输出
        if(s==n){
            for(int i=0;i<n;i++)cout<<g[i]<<endl;
            cout<<endl;
        }
        return;//输出完退出递归
    }
    g[x][y]='.';
    dfs(x,y+1,s);
    if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n]){//如果行列和对角线都没有皇后
        row[x]=col[y]=dg[x+y]=udg[x-y+n]=true;
        g[x][y]='Q';//那么将这个x y区域变为皇后，并且给行列对角线标记
        /*标记这里说一下，为什么只标记一个dg[x+y]就能包括整个行呢，
        因为无论你在哪一行，推理可得，x+y是不变的，*/
        dfs(x,y+1,s+1);//这里换列，上面的特判换行
        g[x][y]='.';
        row[x]=col[y]=dg[x+y]=udg[x-y+n]=false;//还原
    }
}
int main(){
    cin>>n;
    dfs(0,0,0);//这里是x，y坐标以及标记次数吧
    return 0;
}

关于这道题目，我解释三点：深搜的流程，对角线的处理问题（如何判断行，列，以及斜对角线部分只存在一个皇后），回溯问题。
1.深搜的流程：

这里我用文字简单描述一下：从dfs(0,0,0)进入递归入口–>开始逐渐递归行dfs(x,y+1,z)–>特判一下，if(y== n)时该行处理完毕,更新列坐标并让行++：x++,y=0–>当某个点放入皇后时dfs(x,y+1,z+1),–>if(x== n&&z==n)时，走到最后一行且放满皇后，递归结束
2.如何判断对角线放满皇后：
这里在代码中用了这个条件：if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n])，用图片解释一下可能会更加清晰明了：
3.回溯处理：

 g[x][y]='.';
 row[x]=col[y]=dg[x+y]=udg[x-y+n]=false;//还原

这一行代码的作用是将这四个数组上相应位置的值都设为false，表示当前位置不再有皇后。这样做的目的是在回溯的过程中，撤销之前放置皇后的选择，以便进行下一次的搜索。
那为什么还要进行下一次搜索呢：因为本题是求出所有可能放置八皇后的方法。回溯后才可以进行下一次的重新搜索。

bfs

二:bfs广度优先遍历
题目链接：走迷宫
代码如下：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int g[N][N];//储存地图
int f[N][N];//储存距离
int n,m;
int x,y;
void bfs(int a,int b){//广度优先搜索，先吧每次能走的走完
    queue<PII> q;
    q.push({a,b});//初始坐标，该队列储存每步坐标
    f[0][0]=0;
    while(!q.empty()){
        PII start=q.front();
        q.pop();
        g[start.first][start.second]=1;
        int dx[4]={0,1,0,-1};int dy[4]={-1,0,1,0};//上下左右四个坐标
        for(int i=0;i<4;i++){
             x=start.first+dx[i],y=start.second+dy[i];//走了一步之后的坐标
            if(g[x][y]==0){
                g[x][y]=1;
                f[x][y]=f[start.first][start.second]+1;//继承前一步的不熟再加以
                q.push({x,y});//这个坐标放入队列
            }//如果该坐标为零则可以走
        }}
    cout<<f[n][m];
}
int main(){
    cin>>n>>m;
    memset(g,1,sizeof(g));//先吧数组内部都初始化为1
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
        }
    }
    bfs(1,1);
    return 0;
}

题意我就不多解释了，这里解决一点问题：1.广搜流程：
广搜就是每次遍历所有路径，直至递归结束。以图为例：

！这里每次走一步都把所有的通路条件全部走掉，当有任意一个方法走到终点时，即找到最短路径，这样每次遍历全部可能结果的方式，称为广度优先搜索

树与图的深度优先遍历

树与图的深度优先遍历参考这道题：树的重心
代码如下：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010,M=N*2;
int n;
int h[N];//共有n个节点，即代表有n个头节点，
int e[M],ne[M],idx;
int ans=N;
bool st[N];
void add(int a,int b){//b是新节点，a是头节点
   e[idx]=b,ne[idx]=h[a],h[a]=idx++;
   //这个是邻接表
}
/*我来解释一下这个邻接表，他是以单链表的形式存储的，但是在图中并不是链表的形式，我们用图来模拟一下
比如1->2,1->3,这里1这个顶点连接了2,3这两个顶点，但是储存形式是以链表存储的，但是现实是一个图*/
int dfs(int u){
   st[u]=true;//判断有没有走过
   int size=0,sum=0;
   for(int i=h[u];i!=-1;i=ne[i]){//这个函数从u开始，统计与u相连的顶点个数
       int j=e[i];
       if(st[j])continue;//判断j是否被用过，如果被用过则调到链表的下一个值
       int s=dfs(j);
       /*总得来说，dfs函数是统计与该顶点相连的顶点个数，而sum是统计所有联通块的个数*/
       size=max(size,s);
       sum+=s;
   } 
   size=max(size,n-sum-1);
   ans=min(ans,size);
   return sum+1;//这个重心子顶点包括u
}
int main(){
   cin>>n;
   memset(h,-1,sizeof(h));
   for(int i=0;i<n-1;i++){//n-1个无向边就是n个点
       int a,b;
       cin>>a>>b;
       add(a,b),add(b,a);//因为是无向边，所以要有两条联通线
   }
   dfs(1);
   cout<<ans;
   return 0;
}

这里解决三个问题：
1.树的重心的解释
2.邻接表的创建及含义
3.解题思路以及流程
1.树的重心的解释
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

例如这里，该树的重心为4，当4被删除之后，上面一部分和下面一部分的联通块中点数的最大值最小。
2.邻接表的创建及含义
这里邻接表储存的是每个节点与它相连的节点的个数，例如这个图
节点1与节点3，4相连，那么以1为头节点的链表就储存1，3，4
若要在某个节点插入节点，则需要这一句代码

void add(int a,int b){//b是需链接节点，a是头节点
   e[idx]=b,ne[idx]=h[a],h[a]=idx++;
   //这个是邻接表
}

下面解释一下这个代码

另外

memset(h,-1,sizeof(h));

这一句对所有节点的头节点进行初始化，将每个节点的头节点指向-1（null），对链表进行初始化
3.题目思路
该题的重点即如何找出树的重心
这是一部分代码：

for(int i=h[u];i!=-1;i=ne[i]){//这个函数从u开始，统计与u相连的顶点个数
       int j=e[i];
       if(st[j])continue;//判断j是否被用过，如果被用过则调到链表的下一个值
       int s=dfs(j);
       /*总得来说，dfs函数是统计与该顶点相连的顶点个数，而sum是统计所有联通块的个数*/
       size=max(size,s);
       sum+=s;
   } 
   size=max(size,n-sum-1);
   ans=min(ans,size);
   return sum+1;//这个重心子顶点包括u

size：表示当前顶点 u 的子树中的最大子树大小。在深度优先搜索 (DFS) 的过程中，size 会不断更新，以记录与顶点 u 相邻的子树中节点数量的最大值。

s：表示与当前顶点 u 相邻的顶点 j 的子树大小。在代码中，s 的值通过递归调用 dfs 函数来计算。

sum：表示当前顶点 u 的子树中所有子树大小的总和。在代码中，sum 的值会随着对与顶点 u 相邻的顶点进行递归调用 dfs 函数而累加。
这个可以从上图看出：

树与图的广度优先遍历

题目链接：图中点的层次
ac代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1000010;
int h[N],ne[N],e[N],idx;//邻接表数据结构
int dist[N];//储存距离
int st[N];//标记是否走过
int n,m;
void add(int a,int b){
 e[idx]=b;ne[idx]=h[a];h[a]=idx;idx++;
}
void bfs(){
  memset(dist,0x3f,sizeof(dist));
  queue<int> q;
  q.push(1);
  dist[1]=0;
  st[1]=1;
  while(!q.empty())
  {
      int t=q.front();
      q.pop();
      for(int i=h[t];i!=-1;i=ne[i])//h数组相当于地址，t是步数，从第一步开始
      {
          int j=e[i];//再由e数组转化出来实际值
          if(!st[j])
          {
              dist[j]=dist[t]+1;//每次遍历所有与t结点相连的结点，更新结点距离
              q.push(j);
              st[j]=1;
          }
      }
  }
  
}
int main(){
   cin>>n>>m;
   memset(h,-1,sizeof(h));
   for(int i=0;i<m;i++){
       int a,b;cin>>a>>b;
       add(a,b);
   }
   bfs();
   cout<<(dist[n]==0x3f3f3f3f?-1:dist[n]);
   return 0;
}

思路就是先用邻接表储存结点，之后以每个结点为头指针去更新相连结点的距离，最后求出dist[n],即终点距离。

拓扑排序

题目链接：拓扑排序
ac代码：

#include<iostream>
//注意拓扑序是基于深搜实现的
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
/*拓扑序的存在条件：有向无环图，若一个由图中所有点构成的序列 A
满足：对于图中的每条边 (x,y)，x在 A中都出现在 y之前，则称 A
是该图的一个拓扑序列。*/
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(){//手写模拟队列
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++){
        if(!d[i]) q[++tt]=i;//如果入度为1，那么将他存进队列，先将结点为1的入队，到时候根据队列顺序输出
    }
    while(hh<=tt){//当队列不为空
       int t=q[hh++];//把队头元素提取出来，处理完h++，就表示用过这个数了
       //将每一次队头元素提取进去
       for(int i=h[t];i!=-1;i=ne[i]){//处理一个链表时队列不为空，则继续，这一次处理能把所有的数都解决      
           int j=e[i];
           if(--d[j]==0)//先减一下入度再去判断
           q[++tt]=j;//入队，入队后就不为空，则继续进行循环
       }
        
    }
    return tt==n-1;//相等则无环，不等就有环
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);//将输入存入邻接表
        d[b]++;//d数组储存的是当前点位的入度
        
    }
    if(!topsort())cout<<"-1";//无环输出-1；
    else{
        for(int  i=0;i<n;i++)cout<<q[i]<<" ";//循环打印对内数组
        cout<<endl;
    }
    return 0;
}//队列的输出

这道题理解了拓扑序的定义其实就不难，每次把入度为0的点入队，再在for循环邻接表的时候不断更新入度，最后按顺序输出即可。

最短路问题

最短路问题有多种求解方法，本图用来展示他们的适用场景以及时间复杂度

dijkstra最短路

1.直接按顶点顺序处理，没有用到邻接表
2.处理了重边和自环
题目链接：dijkstra求最短路1
ac代码:

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=510;
int n,m;
int g[N][N];//用作输入，从i~j的距离
int dist[N];//dist数组是从1到n这个点的路径
bool st[N];//检查是否处理过 
int dijkstra(){
   memset(dist,0x3f,sizeof dist);//每个距离初始化为最大值
   dist[1]=0;
   for(int i=0;i<n-1;i++){
       int t=-1;
       for(int j=1;j<=n;j++){
           if(!st[j]&&(t==-1||dist[t]>dist[j])){//当st【j】没有被访问
           //而且最短路比当前路径还大，那么
               t=j;//用于记录当前阶段中距离起始点最近的尚未访问过的节点
           }
       }
       for(int j=1;j<=n;j++){//找到一次最短路，刷新所有路径
       dist[j]=min(dist[j],dist[t]+g[t][j]);
       }
       st[t]=true;
   }
   if(dist[n]==0x3f3f3f3f)return -1;
   return dist[n];
}
int main(){
   cin>>n>>m;
   memset(g,0x3f,sizeof g);
   while(m--){
       int a,b,c;
       cin>>a>>b>>c;
       g[a][b]=min(g[a][b],c);//如果有重复边（重边和自环）那么取最小值
   }
   cout<<dijkstra();
   return 0;
}

在内部循环中，它先找到了所有点到起点最近的那个点，之后去更新所有路径到这个最近点的距离，走一步算一步。
堆优化版的dijkstra最短路：dijkstra最短路11
ac代码：

#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10;
int n,m;
int h[N],w[N],e[N],ne[N],idx;//构造邻接表，w数组储存距离
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++;
    /*还是一样，e数组储存b这个值，w数组储存两个值之间的
    距离，其他的和普通邻接表相同*/
}
int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;//起点坐标为零
    priority_queue<PII,vector<PII>,greater<PII>>heap;//声明小根堆
    heap.push({0,1});//将起点坐标入堆
    while(heap.size()){
        auto t=heap.top();//堆顶（最小值）放入t中开始处理
        heap.pop();//删除堆顶元素
        int ver=t.second,distance=t.first;
        if(st[ver])continue;//该点已被使用，进行下一次循环
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[ver]+w[i]){
                //如果最短路比当前路径还大，那么替换
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});//距离和坐标入怼
                
            }
        }
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    return dist[n];
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<dijkstra();
    return 0;
}

堆优化版的dijkstra最短路引入了邻接表和小根堆，它在处理方面有一些区别：主要体现在对节点的选取和松弛操作的方式上。

  1. 节点选取方式：

    • 普通 Dijkstra 算法：在每一轮迭代中，从尚未确定最短路径的节点中选取距离源节点最近的节点作为当前处理节点。
    • 堆优化版 Dijkstra 算法：通过使用优先队列（通常是最小堆）来存储尚未确定最短路径的节点，并且在每一次选择当前处理节点时，选取优先队列中具有最小距离值的节点。这样可以保证每次选取的节点是当前距离源节点最近的节点，并且通过堆的性质，加速了节点的选取过程。

  2. 松弛操作：

    • 普通 Dijkstra 算法：在每一次迭代中，对所有与当前处理节点相邻的节点进行松弛操作，即尝试更新它们的最短距离值。
    • 堆优化版 Dijkstra 算法：在节点选取时，只对具有最小距离值的节点进行松弛操作，即只对优先队列中的顶部节点进行松弛。这样可以减少不必要的松弛操作，提高了算法的效率。

bellman-ford最短路

1.判断负权回路
2.处理边数限制
题目链接：有边数限制的最短路
ac代码：

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=510,M=10010;
struct Edge{
   int a,b,c;
}edges[M];
int n,m,k;
int dist[N];//存每个顶点到起点距离
int last[N];//更新前距离存在last里
void bellman_ford(){
   memset(dist,0x3f,sizeof dist);
   dist[1]=0;//初始化起点距离
   for(int i=0;i<k;i++){//遍历每个顶点
       memcpy(last,dist,sizeof dist);//先复制原数组在last里，避免被更新
       for(int j=0;j<m;j++){
           auto e=edges[j];
           dist[e.b]=min(dist[e.b],last[e.a]+e.c);//为了避免串联，更新

       }
   }
   
}
int main(){
   cin>>n>>m>>k;
   for(int i=0;i<m;i++){
       int a,b,c;
       cin>>a>>b>>c;
       edges[i]={a,b,c};
   }
   bellman_ford();
   if(dist[n]>0x3f3f3f3f/2)puts("impossible");
   else
   cout<<dist[n];
   return 0;
}

这里提醒两个点：
1.

memcpy(last,dist,sizeof dist);

先将源dist数组的值复制到last数组中，避免发生串联，就是避免将要更新的数组使用之前已经更新的数组进行更新，从而让他还是用原数组进行更新。
2.为什么这里的判断条件为 if(dist[n]>0x3f3f3f3f/2)puts(“impossible”) 呢？因为在之前的更新中，原点到该点的距离会被不断更新，从而使两端距离略小于最大值。

spfa最短路

题目链接：spfa求最短路
ac代码：

#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=100010;
int n,m;
int h[N],w[N],e[N],ne[N],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.size()){
       int t=q.front();//先存入t中
       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];
               if(!st[j]){//更新完将当前最短路入队
                   q.push(j);
                   st[j]=true;
               }
           }
       }
   }
   return dist[n];//返回最短路
}
int main(){
   cin>>n>>m;
   memset(h,-1,sizeof h);
   while(m--){
       int a,b,c;
       cin>>a>>b>>c;
       add(a,b,c);
   }
   int t=spfa();
   if(t==0x3f3f3f3f)cout<<"impossible";
   else cout<<t;
   return 0;
}

spfa算法用来处理存在负权边的最短路问题，它用队列来优化路径的松弛操作，能减少不必要的处理。
同时稍微修改代码，也可以用来判断是否存在负环：

#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=100010;
int n,m;
int h[N],w[N],e[N],ne[N],idx;
int dist[N],cnt[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;
    for(int i=1;i<=n;i++){
        st[i]=true;
        q.push(i);//全部入队，当找到一个最短路的时候，就false一下
    }
    while(q.size()){
        int t=q.front();//先存入t中
        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];
                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);
    }
    int t=spfa();
    if(t)cout<<"Yes";
    else cout<<"No";
    return 0;
}

floyd最短路

题目链接：floyd求最短路

floyd最短路也叫用来处理多源汇最短路。用于求解图中所有节点对之间的最短路径。下面是这个算法的基本思路：

  1. 初始化距离矩阵： 首先，我们需要有一个距离矩
    阵 d[][]，其中 d[i][j] 表示节点 i 到节点 j 的
    距离。如果节点 i 和节点 j 之间有直接的边相连，则
    d[i][j] 为边的权重；否则，d[i][j] 为一个表示无穷大的值。

  2. 核心算法： Floyd-Warshall 算法采用了动
    态规划的思想。它通过逐步更新距离矩阵来找到所
    有节点对之间的最短路径。

  3. 三重循环： 外层循环 for (int k = 1; k<= n; k ++ )
    表示考虑所有可能经过节点 k 的路径。内层两个循环
    for (int i = 1; i <= n; i ++ ) 和 for (int j = 1; j <= n; j ++ ) 则用于更新距离矩阵中节点 i 到节点 j 的最短路径。

  4. 状态转移方程： 在每次迭代中，我们检查经过节点 k 是
    否可以缩短节点 i 到节点 j 的路径长度。我们更新
    d[i][j] 为 d[i][k] + d[k][j]，如果这个值比原来
    的 d[i][j] 更小的话，即表示我们找到了更短的路径。

  5. 最终结果： 当所有的节点都考虑了作为中间节点
    的可能性后，距离矩阵中存储的就是所有节点对之间的最短路径长度。

这个算法的时间复杂度为 O(n^3)，其中 n 是节点
的数量。Floyd-Warshall 算法适用于有向图或无向
图，可以处理带负权边但不能处理带负权环的图。

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=210,INF=1e9;
int n,m,Q;
int d[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++){//循环三次求最短路
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
}
int main(){
    cin>>n>>m>>Q;
    for(int i=1;i<=n;i++){//这个是邻接矩阵的初始化方法
        for(int j=1;j<=n;j++){
            if(i==j)d[i][j]=0;
            else d[i][j]=INF;
    }
}
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        d[a][b]=min(d[a][b],c);//根据输入每次更新距离
    }
    floyd();//floyd算法进行最短路刷新
    while(Q--){
        int a,b;
        cin>>a>>b;
        int t=d[a][b];//储存距离在进行判断
        if(t>INF/2) cout<<"impossible"<<endl;//边权可能为负，所以除以2
        else cout<<t<<endl;
    }
    return 0;
}

最小生成树

prim最小生成树

题目链接;prim算法求最小生成树
注意：树是一个无环图，且各个节点之间相连
ac代码：

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=510;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int prim(){
   memset(dist,0x3f,sizeof dist);
   dist[1]=0;//日常初始化
   int res=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]))//如果j坐标没有被访问过，那么检查距离并比价大小
           t=j;
           
       }
           if(dist[t]==0x3f3f3f3f)return 0x3f3f3f3f;
           res+=dist[t];
           st[t]=true;
           for(int j=1;j<=n;j++){
               dist[j]=min(dist[j],g[t][j]);
           }
       
   }
   return res;
}
int main(){
   cin>>n>>m;
   memset(g,0x3f,sizeof g);//日常初始化
   while(m--){
       int a,b,c;
       cin>>a>>b>>c;
       g[a][b]=g[b][a]=min(g[a][b],c);
   }//以邻接矩阵存图
   int t=prim();
   if(t==0x3f3f3f3f)cout<<"impossible"<<endl;
   else cout<<t<<endl;
   return 0;
}

关于最小生成树的定义是这样的：最小生成树（Minimum Spanning Tree，MST）是一个连通无向图中的一棵生成树，它的边权值之和最小。换句话说，给定一个连通无向图，最小生成树是包含所有顶点并且边权值之和最小的树形子图。

kruskal最小生成树

题目链接：kruskal求最小生成树
ac代码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
int p[N];//保存并查集
struct E{
   int a,b,w;
}edg[2*N];
int res=0;//储存权值和
int n,m;
int cnt=0;//记录联通边
int find(int a){//并查集找祖宗节点函数
   if(p[a]!=a)p[a]=find(p[a]);
   return p[a];
   
}
bool cmp(E E1, E E2) {
   return E1.w < E2.w;
}

void kruskal(){
   for(int i=1;i<=m;i++){
       int pa=find(edg[i].a);
       int pb=find(edg[i].b);
       if(pa!=pb){//两个祖宗结点不一样，即不在一个集合中,这也直接保证图中不存在环
           res+=edg[i].w;
           p[pa]=pb;
           cnt++;
           
       }
   }
}

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;
       edg[i]={a,b,c};
}
   sort(edg+1,edg+m+1,cmp);
   kruskal();
   //如果保留的边小于-1，则不能排序
   if(cnt<n-1){
       cout<<"impossible";
       return 0;
   }
   cout<<res;
   return 0;
}

二分图

二分图以及最小生成树的补充会放在后续更新

版权声明：本文为博主作者：shix .原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/2302_80729149/article/details/137374177

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
扎眼的阳光的头像扎眼的阳光普通用户
0
上一篇 2024年4月22日
下一篇 2024年4月22日

相关推荐