思路分析:
- 初始化:获取点的数量,并创建两个辅助数组
adjvex
和lowcost
,分别用于记录最小生成树的边信息和每个顶点到最小生成树的距离。 - Prim算法循环:在每一次循环中,选择一个未加入最小生成树的顶点
k
,使得从已加入最小生成树的顶点到k
的距离最小。循环n-1
次,每次选择一个顶点加入最小生成树。 - 找出下一个顶点:遍历所有未加入最小生成树的顶点,选择距离最小的顶点
k
,加入最小生成树,并标记顶点k
已被访问。 - 更新最小生成树信息:更新
lowcost
数组,更新每个顶点到最小生成树的距离。 - 计算总成本:计算最小生成树的总成本,即所有边的长度之和,并返回。
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size(); // 获取点的数量
// 用于存储最小生成树的边信息
vector<int> adjvex(n, 0); // 记录最小生成树的顶点的下标
vector<int> lowcost(n, 0); // 记录从最小生成树中的某顶点到其它顶点的最小权值
// 初始化lowcost数组,将除了第一个点以外的顶点到第一个点的距离记录下来
for(int i = 1; i < n; i++)
lowcost[i] = abs(points[i][0] - points[0][0]) + abs(points[i][1] - points[0][1]);
// 用于记录顶点是否已被访问过
vector<bool> visited(n, false);
// Prim算法的主要循环,构建最小生成树
for(int t = 0; t < n - 1; t++) {
int k = 1, min = INT_MAX;
// 找出lowcost数组中的最小值
for(int i = 1; i < n; i++) {
if(lowcost[i] < min && visited[i] == false) {
min = lowcost[i];
k = i;
}
}
// 标记顶点k已被访问
visited[k] = true;
// 将k顶点到其它顶点的权值设为0,表示已加入最小生成树
lowcost[k] = 0;
// 更新lowcost数组中的值
for(int i = 1; i < n; i++) {
if(i != k) {
// 计算顶点i到顶点k的距离
int close = abs(points[i][0] - points[k][0]) + abs(points[i][1] - points[k][1]);
// 如果顶点i到顶点k的距离小于当前到顶点i的最小权值,则更新相应信息
if(lowcost[i] > close) {
adjvex[i] = k;
lowcost[i] = close;
}
}
}
}
// 计算最小生成树的总成本
int num = 0;
for(int i = 0; i < n; i++) {
num += abs(points[i][0] - points[adjvex[i]][0]) + abs(points[i][1] - points[adjvex[i]][1]);
}
// 返回最小生成树的总成本
return num;
}
};