力扣1584. 连接所有点的最小费用
题目
题目解析及思路
题目要求返回最小生成树
最小生成树模版题
法一：prim
主要思想是每次找离树最近的顶点，将其加入树种，并更新其他所有点到该点的距离
代码
class Solution {
public:int minCostConnectPoints(vector<vector<int>>& points) {int n = points.size();int res = 0;int st = 0;vector<vector<int>> g(n,vector<int>(n));//建图for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){int dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);g[i][j] = g[j][i] = dist;}}//存每个点到集合的最近距离vector<int> lowcost(n,INT_MAX);//已经加入集合的点不用再看vector<int> v(n);//从任意一个点开始即可，因为所有点最终都会进入集合，这里st = 0v[st] = 1;//初始化lowcost，目前只有st一个点for(int i=0;i<n;i++){if(i == st) continue;lowcost[i] = g[i][st];}//枚举所有店for(int i = 1;i<n;i++){//t为下一个放进集合的点的下标int t = -1;//minv为下一个放进集合的点的权值int minv = INT_MAX;//枚举所有点for(int j=0;j<n;j++){//找到lowcost最小的那个if(v[j] == 0 && lowcost[j] < minv){t = j;minv = lowcost[j];}}//标记，并在res中加入权值v[t] = 1;res += minv;//更新其他没进入集合的点到集合的距离for(int j=0;j<n;j++){if(v[j] == 0 && lowcost[j] > g[j][t]){lowcost[j] = g[j][t];}}}return res;}
};
法二：kruskal
与prim不同，kruskal是每次找最短的边，看该边的两端是否已经联通，如果没有就连接，要用并查集
代码
class Djset{
public://并查集p数组vector<int> parent;//记录树的大小vector<int> size;//存权值之和vector<int> len;int num;Djset(int n) : parent(n),rank(n),len(n,0),size(n,1),num(n){for(int i=0;i<n;i++){parent[i] = i;}}int find(int x){if(x != parent[x]){parent[x] = find(parent[x]);}return parent[x];}//将x和y两点加入集合，权值为lengthint merge(int x,int y,int length){//找双亲int rootx = find(x);int rooty = find(y);//如果没连接if(rootx != rooty){parent[rooty] = rootx;//更新集合的大小size[rootx] += size[rooty];//更新总权值len[rootx] += len[rooty] + length;//只有当全部点加入集合才返回总权值，否则都是-1if(size[rootx] == num) return len[rootx];}return -1;}
};struct Edge{int start;int end;int len;
};
class Solution {
public:int minCostConnectPoints(vector<vector<int>>& points) {int res = 0;int n = points.size();Djset ds(n);vector<Edge> edges;//把所有边信息加入结构体数组for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){Edge edge = {i, j, abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])};edges.emplace_back(edge);}}//根据权值排序sort(edges.begin(),edges.end(),[](const auto& a,const auto& b){return a.len < b.len;});//每次找一条边加入集合for(auto& e:edges){res = ds.merge(e.start,e.end,e.len);//只有当所有点都入图res才不是-1//才会returnif(res != -1) return res;}return 0;}
};
