最小生成树2（Kruskal算法）

最小生成树2（Kruskal算法）

Kruskal算法：

1：按照边的权值的顺序从小到大查看一遍，如果不产生圈（重边也算），就把当前这条边加入到生成树中，基本算法证明和prim一样

2：如何判断是否产生负圈，假设现在要把连接顶点u和顶点v的边e加入到生成树中，如果加入之前u和v不在同一个联通分量里，那么加入e也不会产生负圈，反之，如果u和v在同一个连通分量里，那么一定会产生圈，可以使用并查集高效的判断是否属于同一个连通分量

PS：Kruskal算法耗时在于其对边的排序，算法复杂度为O（|E|log|V|）

struct node{ int u,v,w;} edge[max_v*max_v];bool cmp(node a,node b){ if(a.w<=b.w) return true; return false;}int find(int x){ if(x!=father[x]) return find(father[x]); return x;}int kruskal(int n,int m){ sort(edge,edge+m,cmp); int x,y,res=0; for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。