生成树
Prim：从一颗小树长大
思路和Dijkstra基本一致，唯一不同就是dist记录的是与集合的距离而非与起点的距离 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44// Leetcode 1584 连接所有点的最小费用
// points = [[0,0],[2,2],[3,10],[5,2],[7,0]] 求坐标轴上这几个点的最小生成树的路径和
struct Node{ // 用来在优先队列里用
int node;
int dis;
bool operator>(const Node& ano) const {
return this->dis > ano.dis;
}
};
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size(); // 节点数
vector<vector<int>> graph(n, vector<int>(n, INT_MAX));
for (int i = 0; i < n; ++i){ // 建图
for (int j = 0; j < i; ++j){
graph[i][j] = abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1]);
graph[j][i] = graph[i][j];
}
}
priority_queue<Node, vector<Node>, greater<Node>> pq;
vector<int> dist(n, INT_MAX);
pq.push(Node({0, 0})); // 从0开始， 0到0的距离是0
int ret = 0;
while(!pq.empty()){
Node cur = pq.top(); pq.pop();
// 跟Dijkstra一样，但人家遇到终点直接可以break
// 因为采用优先队列的方式，队列里会有重复，第一次接触的肯定是最优解，后面
// 重复的都是大于最优解的，直接跳过，或者你用一个数组，存储对应节点最优dist
// 每次存储比较取最小值，但是空间浪费太大了，不如这样好
if(dist[cur.node] == 0) continue;
dist[cur.node] = 0;
ret += cur.dis;
for(int i=0; i<n; ++i){
if(dist[i] > graph[cur.node][i]){
dist[i] = graph[cur.node][i];
pq.push(Node({i, graph[cur.node][i]}));
}
}
}
return ret;
}
};
Kruskal
利用并查集的思想 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66// Leetcode 1584 连接所有点的最小费用
// points = [[0,0],[2,2],[3,10],[5,2],[7,0]] 求坐标轴上这几个点的最小生成树的路径和
class UFSet{
public:
UFSet(int _n):count(_n), parent(_n, -1){}
int getCount(){return count;}
void unite(int a, int b){
int f1 = find(a);
int f2 = find(b);
if(f1 == f2) return;
if(parent[f1] < parent[f2]){
parent[f1] += parent[f2];
parent[f2] = f1;
}else{
parent[f2] += parent[f1];
parent[f1] = f2;
}
-- count;
}
bool isConnected(int a, int b){
return find(a) == find(b);
}
private:
int find(int pos){
if(parent[pos] < 0) return pos;
return parent[pos] = find(parent[pos]);
}
int count; // 连通集的个数
vector<int> parent;
};
struct Edge{
int from;
int to;
int weight;
bool operator>(const Edge& ano) const {
return this->weight > ano.weight;
}
};
class Solution {
public:
// 都不用建图，直接把边放进去就行了
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size();
UFSet ufs(n);
priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
for(int i=0; i<n; ++i){
for(int j=0; j<i; ++j){
int weight = abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1]);
pq.push(Edge({i, j, weight}));
}
}
int res = 0, cnt = 0;
while(!pq.empty() && cnt<n-1){
Edge cur = pq.top(); pq.pop();
if(ufs.isConnected(cur.from, cur.to) == false){ // from和to是图节点名，这里直接以points顺序的下标来表示
ufs.unite(cur.from, cur.to);
res += cur.weight;
++cnt;
}
}
return res;
}
};