当前位置：首页 > news >正文

7.12 卷积 | 最小生成树 prim

news 2025/7/12 11:42:22

在 C++ 中， queue 可以存储 vector ，因为 queue 是一种容器适配器，它可以容纳任何符合要求的元素类型，包括标准容器（如 vector ）。

accumulate()累加求和

accumulate 是 C++ 标准库 <numeric> 里的一个实用工具，专门用来做累加求和

accumulate(vec开始位置, vec结束位置, 0);

eg.(nums.begin(),nums.end(),0)

最小成本的联通所有点

两个算法的相同点：每次都是加min 边

prim 加点法 if(未加点 && 最小边)

每次选最近的村子修路，修好再看其他村子经新路会不会更近，

kruskal 加边法 if(未连通 && 最小边)

lc1584.连接所有点

解决“连接所有点的最小费用”问题的，用Prim算法（一种求最小生成树的算法）

核心思路

把点想象成“城市”，连接点的费用是“修路成本”，目标是用最少成本把所有城市连通。

Prim算法的思路是**“贪心”**：从一个起点出发，每次选当前离已连通区域最近的新城市，把它连进来，直到所有城市连通。

代码

class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
// 定义一个极大值，代表初始“无限远”的距离
const int inf = INT_MAX;

int n = points.size();
int ans = 0;
// 标记点是否已加入“已连通区域”（城市是否已连通）
vector<bool> visited(n,false);
// 记录每个点到“已连通区域”的最小距离（每个城市到当前连通区的最低修路成本）
vector<int> dist(n,inf);
// 选第一个点当起点，它到自己的距离是0（自己和自己连通不要钱）
dist[0] = 0;

// 要把n个点都连通，循环n次（每次连一个新点）
for(int i = 0; i < n;i++){
// 找当前离“已连通区域”最近的点（找最低成本的城市）
int u = -1;
for(int j = 0;j < n;j ++){
// 没访问过，且是当前找到的距离最小的点
if(!visited[j]&&(u ==-1||dist[u] > dist[j])){
u = j; // 选中这个点
}
}
// 把这个点标记为“已连通”（加入修路计划）
visited[u] = true;

// 更新其他未连通点到“已连通区域”的最小距离
for(int j =0; j < n; j++){
if(!visited[j]){
// 计算当前点u和点j的曼哈顿距离（修路成本）
int newDist = abs(points[j][0]-points[u][0]) + abs(points[j][1]-points[u][1]);
// 如果经u连接更便宜，就更新“j到连通区的最小成本”
dist[j] = min(dist[j],newDist);
}
}
}
// 把所有“最小距离”加起来，就是总费用（总修路成本）
return accumulate(dist.begin(),dist.end(),0);
}
};

1. 初始化：选第一个点当起点，记录每个点到“已连通区”的距离（初始时只有起点自己，所以起点距离是0，其他是“无限远”）。
2. 选最近点：每次从“未连通”的点里，挑离“已连通区”最近的点，把它加入连通区。
3. 更新距离：加入新点后，重新算其他未连通点到“新连通区”的距离（因为可能经新点连接更便宜）。
4. 算总费用：把所有点到连通区的最小距离加起来，就是连通所有点的最小总费用。

就像“修路包工头”，每次选最近的村子修路，修好再看其他村子经新路会不会更近，最后把修路的钱全加起来，就是最省钱的方案～