| 图论必备算法之一：最小生成树 （易懂至极） | 您所在的位置：网站首页 › kruskal算法例题讲解 › 图论必备算法之一：最小生成树 （易懂至极） |
图论必备算法之一：最小生成树 （易懂至极）
|
前言：
写了2100字，真的很不好写，各位点个赞吧
图论是个极其恶心的东西（除了最小生成树） ——————饮水思源的美西螈 算法介绍：在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集且为无循环图，使得联通所有结点的的 w(T) 最小，则此 T 为 G 的最小生成树。 最小生成树其实是最小权重生成树的简称。 ——————来自《百度百科》 这样一看肯定看不懂（除了一些神犇） 最小生成树，就是求出让整个图联通最少的权值 这么一听，和最短路径有什么区别？
最短路径，意思就是从一个点到另一个点的最短距离 重中之重：这个路径不一定能遍历到所有的点，但最小生成树可以 本蒟蒻感觉到的就这一点，欢迎各位大佬补充 画个祖传小图~
还有一个重点！、 最小生成树只适用于无向图 浅浅推导一下 如果要想遍历整个图，这一条边不能舍
因为这个边如果不走的话那么就遍历不到5号了 接下来进行排序，因为是最小生成树，所以先考虑权值小的边 最小的就是一号到三号，这条边要了
继续往下看，就应该考虑二号到三号了（因为四号到五号确定了。就不再特殊考虑了） 二号到三号此时还并未联通，所以这条边要了
接下来就是二号到一号 重点来力！此时一号到二号已经处于联通状态（间接连通） 所以这条边不要 接下来考虑二号和四号，他们未联通，这条边要了
就差最后一条边了，就是三号到四号，此时三四号也已经联通（间接的间接连通） 所以也不要 整理一下，最后的生成树就是这样的：
如果你一个字一个字地看完了上面的内容，毋庸置疑你已经掌握了最小生成树的其中一种算法的思想(kruskal) 另外一种算法叫prim（因为本蒟蒻不太擅长而且教练也建议用kruskal，所以这篇文章就不做prim的介绍了） 思想理解了代码还不好写？ 确实不太好写 最小生成树需要并查集的思想，之前做过介绍，大家可以看一下并查集不懂的戳这里 并查集优化：启发式合并 以及链式前向星的讲解（因为和这篇文章是一起写的，比较仓促，不明白的随时评论区见） 链式前向星 因为之前讲过链式前向星的内容，这里就不赘述了 按照我们刚才的思想以及和并查集的集合，便可很轻易地写出代码 并查集的几个函数就不多说了直接上了 void make(){ for (int i=1;i=h[y]){ f[y]=x; h[x]+=h[y]; h[y]=0; }else{ f[x]=y; h[y]+=h[x]; h[x]=0; } }接下来就是最重要的函数：kruskal！！！！ 带着大家一步一步地推代码 框架写好： int kruskal(){ }按照我们最小生成树的原理，权值从小到大依次考虑 所以我们先排序 注意这里结构体排序需要写cmp函数 定义一个ans变量，表示最小生成树要的那些边的权值之和，也是最后返回的东西 第二步 循环m条边，每条边都取这条边的起点和终点，然后判断目前两点是否连通 怎么判断呢？ 是的！利用并查集的find函数 寻找到两个点的祖先节点，如果相同，就是联通，则跳过 否则加入这条边 int ans=0; make(); sort(edges+1,edges+1+m); for(int i=1;i |
【本文地址】