力扣1584.连接所有点的最小费用

力扣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 = 0 v[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两点加入集合，权值为length int 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; //只有当全部点加入集合才返回总权值，否则都是-1 if(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 //才会return if(res != -1) return res; } return 0; } };