本文主要是介绍1135. 最低成本联通所有城市（最小生成树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
想象一下你是个城市基建规划者，地图上有 N 座城市，它们按以 1 到 N 的次序编号。
给你一些可连接的选项 conections，其中每个选项 conections[i] = [city1, city2, cost] 表示将城市 city1 和城市 city2 连接所要的成本。（连接是双向的，也就是说城市 city1 和城市 city2 相连也同样意味着城市 city2 和城市 city1 相连）。
返回使得每对城市间都存在将它们连接在一起的连通路径（可能长度为 1 的）最小成本。该最小成本应该是所用全部连接代价的综合。如果根据已知条件无法完成该项任务，则请你返回 -1。
示例 1：
输入：N = 3, conections = [[1,2,5],[1,3,6],[2,3,1]]
输出：6
解释：
选出任意 2 条边都可以连接所有城市，我们从中选取成本最小的 2 条。
示例 2：
输入：N = 4, conections = [[1,2,3],[3,4,4]]
输出：-1
解释：
即使连通所有的边，也无法连接所有城市。
提示：
1 <= N <= 100001 <= conections.length <= 100001 <= conections[i][0], conections[i][1] <= N0 <= conections[i][2] <= 10^5conections[i][0] != conections[i][1]
思路：题目考查的是最小生成树的权，如果不能形成最小生成树的话，那么返回-1。
方法1:Kruskal算法
1、先了解一下Kruskal算法的步骤：
（1）设一个有n个顶点的连通网络为G（V,E），将所有的边按照权值从小到大排序。
（2）当在G中选择一条具有最小权值的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入到T中；否则，即这条边的两个顶点落在同一个连通分量上，会形成环，则将此边舍去，重新选择下一条权值最小的边；
（3）如此重复下去，直到所有顶点在同一个连通分量上为止。
T就是最小生成树。如果最后T中，不能包含所有顶点，那么就没有办法构成最小生成树。
2、设计算法所用到的数据结构：
采用一个二维数组来存集合T。
如何判断两个顶点是否落在同一个联通分量上：采用并查集来解决。关于并查集的知识，请参考684. 冗余连接。
3、代码实现：
class Solution {
public:static bool cmp(vector<int> a, vector<int> b){return a[2]<b[2];}int find_father(vector<int>&f, int i){while(i!=f[i]){i=f[i];}return i;}int minimumCost(int N, vector<vector<int>>& connections) {int re=0;//T存目标最小生成树，就这个题目本身而言，T不是必须的，就拿一个变量记录找到边的个数就可以了vector<vector<int>>T;//将所有的边按照权值从小到大排序sort(connections.begin(), connections.end(), cmp);vector<int>f(N+1);for(int i=1; i<=N; ++i){f[i]=i;} for(int i=0; i<connections.size(); ++i){int p=find_father(f, connections[i][0]);int q=find_father(f, connections[i][1]);if(p!=q){T.push_back(connections[i]);f[p]=q;re+=connections[i][2];}//找到了N-1条边，也就是说N个顶点都找全了if(T.size()==N-1) return re;}return -1;}
};方法2:Prim算法了解原理即可，原理如下：
（1）设一个有n个顶点的连通网络为G(V,E), T(U, TE)是最小生成树。V中存G的顶点，E中存G的边。U中存T的顶点，TE中存T的边。开始时，V中是全部顶点。U和TE都是空的。
（2）第一次先从V中随便取一个顶点加入到U中。
（3）然后从那些其一个端点已经在U中，另一个端点在U外的所有边中找一条最短的边。并把该边和顶点分别并入TE和U中。如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次之后，把所有n个顶点都并入U中，此时U=V，T是最小生成树。
如果最后T中，不能包含所有顶点，那么就没有办法构成最小生成树。
我也写了一个版本实现prim算法供参考，但时间复杂度偏高，题只能过部分test cases，数据量太大会超时。
想用prim算法AC这道题也不是不可以，得精心设计数据结构和减支吧，不再花费时间研究了。。。
class Solution {
public:int minimumCost(int N, vector<vector<int>>& connections) {int re = 0;unordered_set<int>U{1}, V;//开始将顶点1放入U中for(int i=2; i<=N; ++i){V.insert(i);}unordered_map<int, unordered_map<int, int> >m;//存每一条边和权值，方便查找for(auto x:connections){//初始化mm[x[0]][x[1]]=x[2];m[x[1]][x[0]]=x[2];}for (int cnt = 1; cnt <= N; cnt++){//cnt表示已经找到的顶点数目int smallest = INT_MAX;vector<int>target(3);for (auto it1=U.begin(); it1!=U.end(); ++it1){for(auto it2=V.begin(); it2!=V.end(); ++it2){if(m[*it1].count(*it2) && m[*it1][*it2]<smallest){target = {*it1, *it2, m[*it1][*it2]};smallest = m[*it1][*it2];}}}if (smallest != INT_MAX){re += target[2];U.insert(target[1]);V.erase(target[1]);}else break;}return U.size() == N ? re : -1;}
};
这篇关于1135. 最低成本联通所有城市（最小生成树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
