本文主要是介绍Kruskal算法刷题笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
理论基础：
例题：
卡码网---53：寻宝
题目
题目描述
在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。
不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来。
给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。
输入描述
第一行包含两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。
接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。
输出描述
输出联通所有岛屿的最小路径总距离
笔记：
这道题的总体思路是：先将所有边进行权值排序优先选择权值小的边，然后从权值最小的边开始判断该边左右两点是否为同一个祖先，如果为同一祖先那么联通图中就存在环，否则我们就将这两点加入到联通图中，这里就用到了我们并查集的思路。然后我们将同意联通图中的带权边的权值加起来就是连接所有节点的最小连通子图。
最小生成树问题解决的都是求所给带权有向图中的所有节点的最小连通子图，prim算法是从节点的角度出发，不断选择里最小生成树最近的节点从而达到最小联通子图，而kruskal算法是从边的角度出发，对边的权值进行排序，优先选择权值最小的边加入到最小生成树中，从而构成最小联通子图。
prim算法是将符合条件的点一个一个加入到最小生成树中，kruskal算法是将符合条件的带权边一条一条的加入到最小生成树中。kruskal算法是从所有带权边中寻找符合条件的边加入到最小生成树。
#include<bits/stdc++.h>
using namespace std;struct Edge{int l;int r;int val;
};bool s_rule(const Edge& a, const Edge& b){return a.val < b.val;
}vector<int> father;void init(int n){for(int i = 1; i <= n; i++){father[i] = i;}
}int find(int x){return x == father[x] ? x : father[x] = find(father[x]);
}void join(int u, int v){u = find(u);v = find(v);father[v] = u;
}int main(){int v,e;int res = 0;cin >> v >> e;father = vector<int>(v + 1, 0);vector<Edge> edges;while(e--){int v1, v2, val;cin >> v1 >> v2 >> val;edges.push_back({v1, v2, val});}sort(edges.begin(), edges.end(), s_rule);int n = edges.size();init(v);for(int i = 0; i < n; i++){if(find(edges[i].l) != find(edges[i].r)){join(edges[i].l, edges[i].r);res += edges[i].val;}}cout << res << endl;return 0;
}这篇关于Kruskal算法刷题笔记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
