关于图论算法

预习了一点图论的算法，记录一下：

我将分为三部分记录：

1.概念&一笔画问题

2.最短路算法

3.最小生成树算法

1st. 一笔画问题

首先明确以下几个概念：

1、欧拉通路：恰好通过图中的每条边仅一次的通路。

2、欧拉回路：是欧拉路径且起点和终点是同一个点。

3、欧拉图：存在欧拉回路的图。

关于一笔画问题的定理：

　　存在欧拉路的条件：图是连通的，且存在0个或2个奇点。 如果存在2个奇点，那么这两个奇点一定是这个图的起点和终点。

　　如果存在欧拉回路的话，就不会有奇点。

其实我们要探究的一笔画问题就是探究是否存在欧拉回路

——“问题来了，怎样求得欧拉路径呢？”

——“用DFS！”

首先确定起点和终点，也就是输入再存储这张图，记录每个点的度。然后找有没有奇点，如果有的话，就将其当成起点或终点。如果没有，就可以从任何一个点开始。

之后就用DFS找到欧拉回路就行了。不多说，直接上代码！

 1 #include<iostream>
 2 #define N 1001
 3 using namespace std;
 4 int g[N][N];//存图
 5 int du[N];//记录每个点的度
 6 int lu[N];//记录最后要输出的点的顺序 
 7 int n,cnt,e;
 8 void dfs_lu(int i)
 9 {
10     for(int j=1;j<=n;j++)
11         if(g[i][j]==1)
12         {
13             g[i][j]=0;
14             g[j][i]=0;
15             dfs_lu(j);
16         }
17     lu[cnt++]=i;
18 }
19 int main()
20 {
21     cin>>n>>e;
22     int x,y;
23     for(int i=1;i<=e;i++)
24     {
25         cin>>x>>y;
26         g[x][y]=1;
27         g[y][x]=1;
28         du[x]++;
29         du[y]++;
30     }
31     int start=5;//如果没有环（即没有奇点）就直接从1开始，当然从任何一个点开始都是可以的！！！ 
32     for(int i=1;i<=n;i++)
33     {
34         if(du[i]%2==1)
35         start=i;//记录起点 
36         break;
37     }
38     cnt=0;
39     dfs_lu(start);
40     for(int i=0;i<cnt;i++)
41     {
42         cout<<lu[i]<<" ";
43     }
44     return 0;
45 }

有欧拉图，就还会有哈密顿图：

定义：

哈密尔顿通路：通过图中每个顶点仅一次的通路。

哈密尔顿回路：通过图中每个顶点仅一次的回路。

哈密尔顿图：存在哈密尔顿回路的图。

其实哈密顿图和欧拉图的区别就是一个是经过所有的边，一个是经过所有的点

其实不准确，因为只要经过所有的边，就一定会经过所有的点，但是经过所有的点不一定经过所有的边，所以他们的区别实际上是：

一个是要经过所有的点且经过所有的边，一个是经过所有的点但不用非要经过所有的边

——————————————————手动分隔线————————————————————————

2nd. 最短路问题

有四种方法，分别是：floyed算法，Dijkstra算法，Bellman-Ford算法，SPFA算法

我们明确一下这些方法各自的最优问题：

对于多源汇最短路问题，最优解是floyed算法

对于单源最短路：

如果所有边权都是正数且是一个稠密图（边数跟点数的平方是一个等级），首选朴素Dijkstra算法

如果所有边权都是正数且是一个稀疏图（边数跟点的个数是一个等级），首选堆优化版的Dijkstra算法

如果存在负权边最好使用SPFA算法

如果存在负权边且限制边数不能超过给定的数k，最好用Bellman-ford算法

1.floyed算法：

首先记录每一条边，设d[i][j]代表从i到j的最短距离，画一个图看看：

对于一整个图，我们都可以将其分解为以上的小部分，从1到3有两种选择，一种是从1到2，再从2到3，还有一种就是直接从1到3，现在我们已知每条边的边权，那就计算一下两条路径那条更短就去哪条

再比如下面的图：

显然，对于这张图，我们知道1直接到5是没有路径的，所以它们之间的最短距离d[1][5]=min(d[1][4]+d[4][5],d[1][5])=min(1+3,∞)=4

我们也可以由此得出1到6的最短路径长度，1到3的最短路径长度，因此这种方法可以实现求图上任何两点之间的最短路径长度

所以其实我认为它跟DP是有写相同之处的，比如状态转移：

1 for(int k=1;k<=n;k++)
2     for(int i=1;i<=n;i++) 
3         for(int j=1;j<=n;j++)
4             if(d[i][k]+d[k][j]<d[i][j]){
5                 d[i][j]=d[i][k]+d[k][j];
6             }

相似之处还有就是他们都需要初始化，比如它的初始化就是：

d[ i ][ i ]=0，也就是说自己到自己的距离是0
d[ i ][ j ]= 边权，i 与 j 有直接相连的边，那这条边的长度就是它的边权
d[ i ][ j ]= 0x7f，i 与 j 无直接相连的边，这条边的长度定义为一个超级大的数，只有这样我们才能筛选出最短的那条边

（当然，用memset固然简洁明了，但是在处理0和-1之外的赋值操作时会有意想不到的结果......所以还是老老实实地用循环嵌套吧！！！）

然而，为啥要把k在第一层循环枚举呢，能不能不这样？

答案是否定的，也就是说k一定要在第一层枚举，至于原因，我现在尝试解释一下：

举一个小小的例子：

如果我把k枚举在第三层：

那就相当于我枚举了一次i和j，再诶个枚举k来寻找最小值，那就出现了一个bug：

i=1,j=2,k=3时，f[i][j]>f[i][k]+f[k][j]，所以将f[i][j]更新成5+4=9,

i=1,j=2,k=4时，由于我们还没有枚举过i=4,j=2,k=3的时候，所以f[4][2]=正无穷，也就无法将f[1][2]更新成最小值1+2+4=7

然而后来我就不会再枚举i=1,j=2的情况了，也就永远无法将f[1][2]更新成最小值7了

然而我把k枚举在第一层呢？

显然，一开始的情况与把k枚举在第三层一样，我们得不到最小值7，但是后来我枚举了i=4,j=2,k=3的时候，也就更新了f[4][2]的最小值，后来我还能在枚举i=1,j=2的时候，也就还能再更新f[1][2]的值，因此总能得到最小值

现在我们将这两种方法进行对比，寻找差异：

当将k枚举在第三层的时候，i 和 j 都只能枚举一次循环，后来就不会再回头枚举了，这会导致中间的部分可能还没有更新，从而导致最小解错误的情况。

然而当将k枚举在第一层的时候，对于不同的k我都会枚举i和j，也就是对于两个确定的i和j，都会不只枚举一次，而是n次（因为k会枚举n次），这样总能更新出所有路径的值然后再去修改f[i][j]的值，这样的话一定能得到正确的最小解。

那就直接上题！

输入顶点数 m 和边数 n，任意两点的之间的距离w都<=1000，再输入p，q两点标号，接下来输入m行，每行代表一条边的起点，终点和权值，输出p，q两点之间路径长度的最小

思路就是我刚才说的，直接上代码吧！！

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int d[101][101];  
 6 int main()
 7 {
 8     int n,m,p,q;
 9     cin>>n>>m>>p>>q;
10     for(int i=1;i<=n;i++)
11     {
12         for(int j=1;j<=n;j++)
13         {
14             d[i][j]=1001;
15         }
16     }
17     //初始化将每条边变成一个很大的数 
18     for(int i=1;i<=n;i++)
19     { 
20         d[i][i]=0;
21     }
22     //自己到自己的长度是0 
23     int i,j,len;
24     for(int ha=1;ha<=m;ha++)
25     {
26         cin>>i>>j>>len; 
27         d[i][j]=len;
28         d[j][i]=len;
29     }//输入边的长度 
30     for(int k=1;k<=n;k++)
31     {
32           for(int i=1;i<=n;i++)
33         {
34               for(int j=1;j<=n;j++)
35             {
36                   if(d[i][k]+d[k][j]<d[i][j])
37                 {
38                        d[i][j]=d[i][k]+d[k][j];
39                 }
40             }
41       }
42   }
43       //寻找最短距离 
44        cout<<d[p][q];
45     return 0;
46 }

——————————————————手动分隔线—————————————————————

2、Bellman-Ford算法

首先明确几个概念：

什么是松弛函数？

现在有一个图，对于边集合 $E$ 中任意边， $w(u,v)$ 表示顶点 $u$ 出发到顶点 $v$ 的边的权值，而 $d[v]$ 则表示从起点 $s$ 到顶点 $v$ 的路径权值， $p=\langle v_0,v_1,...,v_k \rangle$ 表示从顶点 $v_0$ 到顶点 $v_k$ 的路径。

所以松弛函数像刚才我们在讨论floyed算法是所做的操作一样：

若存在边 $w(u,v)$ ，使得：

$d[v] \gt d[u]+w(u,v)$

则更新 $d[v]$ 值：

$d[v]=d[u]+w(u,v)$

其实就是更新成较短的路径的长度呗，这就是三角变换

初始化的操作也是一样的：

$d[a]=0$ $d[v]=\infty ,v \in V - \{a\}$

现在我们将对边集合 $E$ 中每条边都执行一次松弛视为一次迭代操作，现在我们来看迭代次数和图之间的关系（至于为啥要这样以后会说的）

那我们其实不难发现，在一个图中，有时只使用一次松弛操作就可以实现找到最优解，比如下面这张图：

我们如果按照：w(a,b) w(b,c) w(c d) 的顺序进行松弛：

对边 $w(a,b)$ 执行松弛函数，则 $d[b]=d[a]+w(a,b)=1$
对边 $w(b,c)$ 执行松弛函数，则 $d[c]=d[b]+w(b,c)=3$
对边 $w(c,d)$ 执行松弛函数，则 $d[d]=d[c]+w(c,d)=8$

那我们只要通过一次迭代操作就可以得到最优解了！

BUT！

如果我的运气很不好，（实际上是最坏），那一次就解决问题的概率其实不大，所以我至少要进行三次操作（由于过程太麻烦，这里就不过多赘叙）

那么发现规律：

最多要进行m（顶点数）-1 次操作，就能让所有的点确定，

即对于未确定的顶点，每次对边集进行一次操作，都至少会增加一个确定的点！

那现在我来推理一下：

首先进行第一次迭代，那么b点一定会被确定，因为b只能从a点过去。

在第二次迭代的时候，由于我们确定了b点和a点，要不就是从a到b到c，要不就是直接从a到c 所以与a，b构成三角形的点c一定会被确定。

下面依次类推，都至少会确定一个点，证毕。

OK！现在我们就可以进入正题了——谜一样的 Bellman-Ford（转载，不喜勿喷）

但是我们要有一点前提：

就是不能允许负权回路出现，因为如果有负权回路，那么这个最短路就会一直被更新（一直减减减），那就无法在 m-1 次操作内运行出来

（介绍一下啥是负权回路：一个回路上所有边权相加小于零）

因此Bellman-Ford算法就有了另一个作用：

判断图中是否有负权回路出现：

每次更新操作次数，如果操作次数大于m-1次，就可以认定有负权环

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #define INF 2147483647
 4 #define ll long long
 5 using namespace std;
 6 const int maxn=5005;
 7 ll dis[10005];
 8 int from[maxn],to[maxn],len[maxn];
 9 int n,m,s;
10 void bellman_ford()
11 {
12     int k;
13     for(k=1;k<=n-1;k++)
14     {//做n-1次松弛，因为任意两点之间的最短路最多包含n-1条边
15         int flag=0;
16         for(int i=1;i<=m;i++)
17         {
18             if(dis[to[i]]>dis[from[i]]+len[i])
19             {
20                 dis[to[i]]=dis[from[i]]+len[i];
21                 flag=1;
22             }
23         }
24         if(!flag) break;//加不加都行（能省点时间）
25     }
26 }
27  
28 int main()
29 {
30     
31     scanf("%d %d %d",&n,&m,&s);
32     for(int i=1;i<=n;i++)
33     {
34         dis[i]=INF;
35     }
36     dis[s]=0;
37     for(int i=1;i<=m;i++)
38     {
39         scanf("%d %d %d",&from[i],&to[i],&len[i]);
40     }
41     bellman_ford(); 
42     for(int i=1;i<=n;i++)
43     {
44         printf("%d ",dis[i]);//从起点出发到每个点的距离 
45     }
46     return 0;
47 }

——————————————————手动分割线——————————————————

三、SPFA

思想跟Bellman-Ford算法其实几乎一样，唯一的区别就是人家更牛了！！！

由于我不知道Bellman-Ford要进行多少次迭代，所以要试m-1次，那就很不好，所以SPFA就成功地解决了这个问题：

初始时我们将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时，也就是没法再修改的时候，算法结束。
代码实现：

 1 d = ∞，让队列Q初始化为空
 2 d[S]=0，Q.in(S)//让起点入队
 3 while(!Q.empty())
 4 {
 5     u=Q.out();//让他出队
 6     for(所有的边w(u,v))
 7         if(d[v]>d[u]+len(u,v))//让牵扯到的点全都进队
 8         {
 9             d[v]=d[u]+len(u,v);
10             if(v不在队内) Q.in(v);
11         }
12 }

所以其实他的特点就和BFS挺像，不同的是：

BFS每个点只能遍历一次，但是SPFA可以让某些点在队里队外反复横跳（来回进出）

代码模板如下：（检验有没有负边权）

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <queue>
  6 #include <algorithm>
  7 #define INF 0x3f3f3f3f
  8  
  9 using namespace std;
 10 const int MAXN = 5500;
 11 int n,m,w;
 12 struct Edge
 13 {
 14     int v,w,next;
 15 }edge[MAXN];
 16 
 17 int head[MAXN],dis[MAXN],judge[MAXN],t;
 18  
 19 void Init()
 20 {
 21     memset(head,-1,sizeof(head));
 22     t = 0;
 23 }
 24 void Add_edge(int u,int v,int w)
 25 {
 26     edge[t].v=v;
 27     edge[t].w=w;
 28     edge[t].next=head[u];
 29     head[u]=t++;
 30 }
 31  
 32 bool SPFA()
 33 {
 34     int mark[MAXN];//记录每个点如队列的次数
 35     for(int i= 1;i<=n;i++)
 36     {
 37         mark[i]=0;
 38         dis[i]=INF;
 39         judge[i]=0;
 40     }
 41     queue<int>q;
 42     q.push(1);  //我们只需要判断负环，随便找一个起点就好
 43     dis[1]=0;
 44     judge[1]=1;//入队列
 45     mark[1]++;
 46     while(!q.empty())
 47     {
 48         int u=q.front();
 49         q.pop();
 50         judge[u]=0;//出队列
 51         for(int i=head[u];i!=-1;i=edge[i].next)
 52         {
 53             int v=edge[i].v;
 54             if(dis[v]>dis[u]+edge[i].w)
 55             {
 56                 dis[v]=dis[u]+edge[i].w;
 57                 if(!judge[v])//有关联的通通入列 
 58                 {
 59                     q.push(v);
 60                     mark[v]++;
 61                     judge[v]=1;
 62                 }
 63                 if(mark[v]>=n)//如果不存在负环，那么最多更新n-1次就可以得到最终的答案，因为一次最少更新一个节点，那么如果出现了更新n次，那么就一定出现了负环
 64                     return false;
 65             }
 66         }
 67     }
 68     return true;
 69 }
 70 int main()
 71 {
 72     int T;
 73     scanf("%d",&T);
 74     while(T--)
 75     {
 76         Init();
 77         int u,v,z;
 78         scanf("%d%d%d",&n,&m,&w);//要求有m个正权边，w个负权边 
 79         for(int i = 0;i < m;i ++)
 80         {
 81             scanf("%d%d%d",&u,&v,&z);
 82             Add_edge(u,v,z);
 83             Add_edge(v,u,z);
 84         }
 85         for(int i=0;i<w;i++)
 86         {
 87             scanf("%d%d%d",&u,&v,&z);
 88             Add_edge(u,v,-z);
 89         }
 90         if(!SPFA())
 91         {
 92             printf("YES\n");
 93         }
 94         else
 95         {
 96             printf("NO\n");
 97         }
 98     }
 99     return 0;
100 }

还有就是找最短路径的：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N = 2030, M = N * 50;        //N为顶点数，M为边数
//数组构造邻接表, n为定点数，m为边数
int n, m
int h[N], e[M], w[M], ne[M], idx;       
int dist[N];
queue<int> q;
bool st[N];

// 添加一条边a->b，边权为c
void add_edge(int a,int b,int c)
{
    //e[idx]指的是编号为idx的边的去向为何处，h[a]存储的是从a出发的所有边的单链表表头
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

void spfa()  // 求1号点到n号点的最短路距离
{
    memset(dist, 0x3f, sizeof dist);    //0x3f代表最大值，最小值可用0xcf
    dist[1] = 0;
    q.push(1);
    st[1] = true;

    while (q.size())        //while循环控制出队
    {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])        //for循环控制入队+更新
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
            //  cnt[j] = cnt[t] + 1;             // 用于判断是否存在负环
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            //  if(cnt[j] >= n) return true;    // 用于判断是否存在负环
            }
        }
    }
}

int main()
{
    memset(h,-1,sizeof(h));
    ...            //需先通过add_edge函数，采取邻接表的方式构造好图
    spfa();
}

——————————————————手动分隔线————————————————————————

四、Dijkstra算法

设起点为s，dis[v]表示从起点s到点v的最短路径，path[v]表示v的前驱结点（便于最后输出路径）

首先初始化：dis[v]等于正无穷（或是一个超大的数），dis[s]等于0（其实任何一个结点到自己的距离都初始化为0），path[s]=0（也就是起点没有前驱）

然后在所有点中找到dis最短的（即到原点距离最近的），并将其标记成已经确定的最短路径。（这里视作u）

接着通过for循环找到所有与u相连的、未被确定为最短路径的点v，通过三角变换，更新新的路径：

1     if(dis[u]+w[u][v]<dis[v]) 
2     {
3         dis[v]=dis[u]+w[u][v];//进行更新 
4         path[v]=u;//记录前驱 
5     }

但是用这玩意有个前提：没有负权边（很好理解对吧）

完整代码：

  1 #include<iostream>    
  2 #include<cstring> 
  3 #include<cstdio>  
  4 using namespace std;   
  5 const int maxn=101;
  6 int judge[maxn];//记录这个点是否已经用过了 
  7 int a[maxn][maxn];//表示两个点之间的距离 
  8 int dis[maxn];//到起点的距离 
  9 int path[maxn];//前驱 
 10 int n,m,start; 
 11 const int chaojida=99999; 
 12 void init()//准备操作 
 13 {
 14     cin>>n>>m>>start;
 15     int x,y,len;
 16     for(int i=1;i<=n;i++)
 17     {
 18         for(int j=1;j<=n;j++)
 19         {
 20               if(j==i) a[i][j]=0;
 21               else a[i][j]=chaojida;
 22           }
 23     }
 24     //第一步：初始化
 25     //将所有的距离（出自己以外）都设为一个超级大的数，自己到自己的距离是0 
 26     for(int i=1;i<=m;i++)
 27     {        
 28         cin>>x>>y>>len;
 29         a[x][y]=len;
 30         a[y][x]=len;
 31     }
 32     //读取输入的信息，用给出的条件（起点，终点和距离）更新原始数组 
 33 } 
 34 void dijkstra(int s)
 35 {
 36     for(int i=1;i<=n;i++)  
 37     { 
 38         dis[i]=chaojida;//目前，每个点到起点的距离都超级大 
 39         judge[i]=false;//都还没被用过 
 40     }//初始化 
 41     dis[s]=0;//还是初始化（起点到自己的距离是0 
 42     for (int i=1;i<=n;i++)
 43     {
 44         int mind=chaojida;  
 45         int k;//用来记录准备放入集合1的点
 46         for(int j=1;j<=n;j++)  //查找集合2中d[]最小的点
 47         {
 48             if((!judge[j])&&(dis[j]<mind))
 49             { 
 50                 mind=dis[j];//更新最小值，以供后面比较 
 51                 k=j;//最小的点是k 
 52             }
 53             if(mind==chaojida)  
 54             {
 55                 break; //更新结点求完了
 56             }
 57             judge[k]=true;
 58         }//  加入集合1
 59         for(int j=1;j<=n;j++)  //修改集合2中的d[j]
 60         {
 61             if((!judge[j])&&(dis[k]+a[k][j]<dis[j]))
 62             { 
 63                 dis[j]=dis[k]+a[k][j];
 64                 path[j]=k;
 65             }
 66         }
 67     }
 68 }    
 69 void search(int x)
 70 {
 71     if(x!=start) 
 72     {
 73         search(path[x]);
 74     }
 75     cout<<x<<' ';
 76 }//便于最后输出前缀
 77 void write()
 78 {
 79     cout<<start<<"到其余各点的最短距离是："<<endl; 
 80     for(int i=1;i<=n;i++)
 81     {
 82         if(i!=start)
 83         {
 84             if(dis[i]==chaojida) cout<<i<<"不可达！"<<endl;
 85             else
 86             {
 87                 cout<<i<<"的最短距离："<<dis[i] <<",依次经过的点是：";
 88                 search(path[i]);
 89                 cout<<i<<endl;         
 90             } 
 91         }        
 92     }
 93 }//输出应题目要求 
 94 int main()
 95 {
 96     init();
 97     dijkstra(start);
 98     write();
 99     return 0; 
100 }

正好凑成一百行！！！

————————————————————纯手动分隔线——————————————————————

3rd. 最小生成树算法

众所周知，有N个点，用N-1条边连将所有的点连接成一个连通块，形成的图形只可能是树，没有别的可能。（哈哈哈，这就不用解释了吧）

所以我们就引出了最小生成树的概念：

有一个n个点的图，这个图有至少n-1条变。现在要从里面挑出n-1条边，使其连接所有的点，而且这些边权之和是最小的，这就是最小生成树。

一. Prim算法

我们可以通过染色的方式跟好的理解一下：

初始时我们将所有点都染成蓝色（蓝色代表还没有被选中，白色代表已经被选入生成的树中），我们每次都会将一个点选入最小生成树，这个点有以下几个前提：

1.未被选中过、2.与上一个选中的点相连且边权是上一个点连接的所有边中最短的。

这样一直选，直到所有的点都被选中为止

算法描述：
以1为起点生成最小生成树，min[v]表示蓝点v与白点相连的最小边权。
MST表示最小生成树的权值之和。
a）初始化：min[v]= ∞(v≠1); min[1]=0;MST=0;
b）for (i = 1; i<= n; i++)
1.寻找min[u]最小的蓝点u。
2.将u标记为白点
3.MST+=min[u]
4.for 与白点u相连的所有蓝点v
if (w[u][v]<min[v])
min[v]=w[u][v];
c）算法结束： MST即为最小生成树的权值之和

代码实现：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int juzhen[101][101];              //邻接矩阵
 6 int minn[101];                //minn[i]存放蓝点i与白点相连的最小边权
 7 bool judge[101];                  
 8 //judge[i]=True，表示顶点i还未加入到生成树中
 9 //judge[i]=False，表示顶点i已加入到生成树中 
10 int n,i,j;
11 int main()
12 {
13     cin>>n;
14     for(i=1;i<=n;i++)
15     {
16         for(j=1;j<=n;j++)
17         {
18             cin>>juzhen[i][j]; 
19         }
20     }
21     memset(minn,0x7f,sizeof(minn));   //初始化为maxint
22     minn[1]=0;
23     memset(judge,1,sizeof(judge));//初始化为True，表示所有顶点为蓝点
24     for(i=1;i<=n;i++)
25     {
26         int k=0;
27         for(j=1;j=n;j++)  //找一个与白点相连的权值最小的蓝点k
28         {
29             if(judge[j]&&(minn[j]<minn[k]))
30             {
31                 k=j;
32             }
33         }
34         judge[k]=false;              //蓝点k加入生成树，标记为白点
35         for(j=1;j<=n;j++)         //修改与k相连的所有蓝点
36         {
37             if(judge[j]&&(juzhen[k][j]<minn[j]))
38             {
39                 minn[j]=juzhen[k][j];
40             }
41         }
42     }       
43     int sum=0;
44     for(i=1;i<=n;i++) //累加权值 
45     {
46         sum+=minn[i];
47     }
48     cout<<sum;
49     return 0;
50 }

_______________________________纯手动分隔线——————————————————————

最后一个算法：

二、Kruskal算法

（Tips：需要了解并查集算法，可自行去看下一个博客——并查集）

Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。直到选取了n-1条边为止。

当然，体现并查集思想的地方就是首先将每一个点看作一个集合，再将选中的那条边的两个顶点合并成一个集合，下次的找遍的时边时候判断边的两个顶点是不是在集合里就行了。

算法描述:

1、初始化并查集。father[x]=x。

2、tot=0

3、将所有边用快排从小到大排序。

4、计数器 k=0;

5、for(i=1; i<=M; i++) //循环所有已从小到大排序的边

if 这是一条u,v不属于同一集合的边(u,v)(因为已经排序，所以必为最小)

begin

①合并u,v所在的集合，相当于把边(u,v)加入最小生成树。

　②tot=tot+W(u,v)

③k++

④如果k=n-1,说明最小生成树已经生成，则break;

end;

6. 结束，tot即为最小生成树的总权值之和。

代码实现：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,m,tot=0,k=0;//n端点总数，m边数，tot记录最终答案，k已经连接了多少边 
 6 int fat[10001];//记录集体老大 
 7 struct node
 8 {
 9     int from,to,dis;//结构体储存边 (起点，终点，边权） 
10 }edge[10001];
11 bool cmp(const node &a,const node &b)//sort排序
12 {
13     return a.dis<b.dis;
14 }
15 int father(int x)//并查集的一部分 ，查找两个元素他们的老大是不是一样的
16 //（具体并查集内容可见下一个博客----并查集 ） 
17 {
18     if(fat[x]!=x)
19     return father(fat[x]);
20     else return x;
21 }
22 void unionn(int x,int y)//加入团体，并查集的一部分 
23 {
24     fat[father(y)]=father(x);
25 }
26 int main()
27 {
28     scanf("%d%d",&n,&m);//输入点数，边数 
29     for(int i=1;i<=m;i++)
30     {
31         scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].dis);//输入边的信息 
32     }
33     for(int i=1;i<=n;i++) fat[i]=i;//自己最开始就是自己的老大 （初始化） 
34     sort(edge+1,edge+1+m,cmp);//按权值排序（kruskal的体现） 
35     for(int i=1;i<=m;i++)//从小到大遍历 
36     {
37         if(k==n-1) break;//n个点需要n-1条边连接 
38         if(father(edge[i].from)!=father(edge[i].to))//假如不在一个团体 
39         {
40             unionn(edge[i].from,edge[i].to);//加入 
41             tot+=edge[i].dis;//记录边权 
42             k++;//已连接边数+1 
43         }
44     }
45     printf("%d",tot);
46     return 0;
47 }

代码那么那么详细，我就不解释了

就先记录到这吧，以后还会加一些题之类的，会日臻完善

拜拜！

相关阅读:
vue3与vue2的区别
 MySQL开篇:简单的库操作,表操作,数据类型
 【Mysql】 InnoDB引擎深入- 内存结构之ChangeBuffer | Log Buffer
UEFI之HOB详解
 【数据结构与算法】常见排序算法（Sorting Algorithm）
mysql字符集浅谈
 windows安装VMware虚拟机(附带CentOS7部署)
tslib库的移植
 细讲如何解决Idear中使用@Test时提示Junit不存在问题
 算法学习笔记——对数器
原文地址：https://www.cnblogs.com/zch061023/p/16070289.html