切分定理
Prim 同样是解决最小生成树问题的另一种解法, 但和 Kruskal 有所不同, Prim 基于的是切分定理.
1.切分: 切一刀把图分为两个不重叠且非空的节点集合, 这个操作称为切分, 被切中到的边, 称为 [横切边].
2.切分定理: 对于任意一种 [切分], 其中权重最小的那条 [横切边] 一定是构成最小生成树的一条边.
3.如何理解切分定理: 假设一刀下去, 节点集合分为两个阵营, 这两个阵营之间存在多个”藕断丝连”的权重边, 如果我们想要将这两个 [阵营] 以最小的代价联合起来, 那么我们一定取的是最小的那个藕断丝连的权重边
4.Prim 算法的思想: 基于切分定理, 我们随机从某一个节点开始进行切分 [该节点] 与 [剩余其他的节点图], 比如首个节点 A 有两个和 [剩余其他节点图] 的两个权重边, 比如 AF=1 和 AB=6, 那么我们就取1这个权重边顺便将第B这个节点记录进来, 所以我们有了一个未完成的最小生成树 AB=6; 然后从AB出发再去找和 [剩余其他节点图] 的切分, 也就是所有权重边, 继续选最小的
5.对于产出最小生成树的过程, 我们反复地找新的节点的邻边加入横切边的集合, 就可以得到新的切分的所有横切边; 对于重复边, 我们可以用一个 inMST 数组辅助, 防止重复计算横切边
6.我们求横切边之后, 还需要找动态地找权重最小的边, 需要维护一个动态队列
7.Prim算法的做法:
class Prim {
private:
priority_queue<vector<int>> q;
vector<int> bool;
int weightSum = 0;
// graph定义[from, to, weight]
vector<vector<int>> graph;
inMST[0] = True;
};
class Solution {
public:
struct cmp {
bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second;
}
};
int minimumCost(int n, vector<vector<int>>& connections) {
// 建图: 对每个点存储pair <节点, 边权重>
vector<vector<pair<int, int>>> edges(n + 1);
for (auto connection: connections) {
edges[connection[0]].emplace_back(connection[1], connection[2]);
edges[connection[1]].emplace_back(connection[0], connection[2]);
}
// pair边权重排序
// auto cmp = [](pair<int, int>&a, pair<int, int>&b) -> bool {return a.second > b.second; };
// 存储横向边的优先队列
// priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)>pq(edges[1].begin(), edges[1].end(), cmp); //o(n)建堆
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp>pq; //o(n)建堆
for (int i = 0; i < edges[1].size(); ++i) {
pq.push(edges[1][i]);
}
vector<bool>visited(n + 1, 0);
visited[1] = true;
int connectNum = 1
int ans = 0;
while (!pq.empty()) {
while (!pq.empty() && visited[pq.top().first])
pq.pop();
if (!pq.empty()) {
connectNum++;
visited[pq.top().first] = true;
ans += pq.top().second;
for (auto point:edges[pq.top().first]) {
if (!visited[point.first])
pq.emplace(point);
}
}
if (connectNum == n)
return ans;
}
return -1;
}
};
转载请注明来源, from goldandrabbit.github.io
