最小生成树MST

Kruskal 算法

图的生成树是一棵含有其所有节点的无环联通子图, 加权图的最小生成树(MST) 是一棵权值和最小的生成树.

Kruskal 算法

题目对应 LeetCode 1135. 最低成本联通所有城市, 题目如下: 想象一下你是个城市基建规划者，地图上有 N 座城市，它们按以 1 到 N 的次序编号。

给你一些可连接的选项 conections，其中每个选项 conections[i] = [city1, city2, cost]表示将城市 city1 和城市 city2 连接所要的成本。（连接是双向的，也就是说城市 city1 和城市 city2 相连也同样意味着城市 city2 和城市 city1 相连）。

返回使得每对城市间都存在将它们连接在一起的连通路径（可能长度为 1 的）最小成本。该最小成本应该是所用全部连接代价的综合。如果根据已知条件无法完成该项

Kruskal 算法过程如下:

按照边的权值有效到大排序使用并查集, 在不构成环的情况下把边的两个顶点加入并查集, 并记录当前权值, 如果构成环,舍弃掉改边.当并查集中边的数量为N-1时返回结果. 当所有边都遍历结束但数量不满足N-1时,返回-1

代码如下:

bool cmp(vector<int> &a, vector<int> &b){ return a[2] < b[2]; } class DSU{ public: vector<int> parent; DSU(int n){ parent.resize(n + 1); for(int i = 0; i < n + 1; ++i) parent[i] = i; } int find(int x){ if (parent[x] != x){ parent[x] = find(parent[x]); } return parent[x]; } void _union(int x, int y){ int rx = find(x); int ry = find(y); if (rx != ry){ parent[rx] = ry; } } bool isCircle(int x, int y){ return find(x) == find(y); } }; class Solution { public: int minimumCost(int N, vector<vector<int>>& connections) { sort(connections.begin(), connections.end(), cmp); DSU dsu(N); int cnt = 0; int ret = 0; for(auto& edges: connections){ if(dsu.isCircle(edges[0], edges[1])) continue; else{ dsu._union(edges[0], edges[1]); ret += edges[2]; ++cnt; } if (cnt == N - 1) break; } return cnt == N - 1? ret: -1; } };