Kruskal(并查集)
数据结构
并查集储存区分节点状态:
未访问
or已访问
边集:根据权重排序
算法思想
每次把权重最小的边的节点标记已访问(加入集合)
//并查集
class joinSet{
private:
vector<int> f, rank;
int n;
public:
joinSet(int _n){
n = _n;
f.resize(n);
for(int i = 0; i < n; i++){
f[i] = i;
}
rank.resize(n, 1);
}
//查找
int find(int x){
return x == f[x] ? x : f[x] = find(f[x]);
}
//加入新元素
bool join(int x, int y){
int fx = find(x), fy = find(y);
if (fx == fy) return false;
//按秩优化
if(rank[fx] > rank[fy]){
swap(fx, fy);
}
rank[fy] += rank[fx];
//元素加入
f[fx] = fy;
return true;
}
};
//边
struct Edge{
int len, x, y;
Edge(int len, int x, int y):len(len), x(x), y(y){}
};
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
//距离函数
function<int(int, int)> dis = [&](int x, int y) -> int{
return abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1]);
};
//边读入
int n = points.size();
vector<Edge> edges;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
edges.emplace_back(dis(i, j), i, j);
}
}
//根据权重排序
sort(edges.begin(), edges.end(), [&](Edge a, Edge b)->int{return a.len < b.len;});
//根据权重逐条边加入
int ans = 0, count = 1;
joinSet js(n);
for(auto& [len, x, y] : edges){
if(js.join(x, y)){
ans += len;
count++;
if(count == n){
break;
}
}
}
return ans;
}
};
Prim算法
数据结构
1.两个容器V
与lowerCost
。
V
根据下标标识
一个节点是否已经被访问。
lowerCost
记录未访问节点集
与已访问节点集
的最近节点距离。这个地方有弯,他记录的是节点集
与节点集
之间最近距离(在不同情境中“最近距离”的概念不同),只有遇到更小距离才会对应更新。
算法思想
每次循环将
未访问节点集
中的一个最近节点
加入已访问节点集
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
int ans = 0;
//建距离图
int n = points.size();
vector<vector<int>> grid(n, vector<int>(n));
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
int distance = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
grid[i][j] = grid[j][i] = distance;
}
}
//两个容器
vector<int> lowerCost(n);
vector<int> visited(n);
//初始化,0加入Vnew
visited[0] = 1;
for(int i = 0; i < n; i++){
if(i == 0) continue;
lowerCost[i] = grid[0][i];
}
//Prim算法
for(int _ = 1; _ < n; _++){
int minIndx = -1;
int minVal = INT_MAX;
//找V最近点
for(int j = 0; j < n; j++){
if(visited[j] == 0 && lowerCost[j] < minVal){
minIndx = j;
minVal = lowerCost[j];
}
}
ans += minVal;
visited[minIndx] = 1;
//更新V与Vnew的最小距离容器
for(int i = 0; i < n; i++){
if(visited[i] == 0 && grid[i][minIndx] < lowerCost[i]){
lowerCost[i] = grid[i][minIndx];
}
}
}
return ans;
}
};
标签:vector,int,最小,len,生成,++,points,节点
From: https://www.cnblogs.com/LuvLetter-whx/p/18530667