您可以自由地共享和演绎本文稿, 只需遵守开源协议[CC By 4.0]
如果这篇文章帮助到你, 可以请我喝一杯咖啡~
最小生成树问题
给出一个带权重的无向图,请找出能够维持它连通性的权重之和的最小的一组边。
这个问题被称为“最小生成树”问题,也成为“最小连通子图”问题。
为什么称他为“树”?是因为我们可以很直观地得出“在上述问题的结果中一定不存在环”的结论。无环的图,退化为树。
一个很直观的想法是,既然是最小生成树,那么我们就让它生成一下看看。
Prim算法
我们首先随机选择一个节点作为基础的“树”,然后每次选择距离我们已经有的树最近的且可以直接相连的节点,将它加入树中。
当所有的节点都被加入树中之后,算法结束。 这个算法被称为Prim算法,非常直观。
但是我们仍然有几个细节要讨论:
- 如何确定距离目前的树最近的节点?
我们认为一个节点与树的距离是“节点到树上任意一个节点的最小距离”。找到这个最小节点是非常容易的:以类似于Dijkstra算法的方式即可快速确定。而这一距离的更新只需要在每次新插入节点时更新。 - 这个问题针对的对象是无向图
因此我们需要非常小心地调整邻接表和表示节点访问情况的向量。 - 如果存在着若干个距离相同且都是最小值的节点,该如何处理?
随机选择其一,然后继续遍历
代码
int Prim(const vector<vector<int>> &Graph) {
vector<int> distance(Graph.size(), int(INT_MAX));
unordered_map<int, bool> visited;
int nowPoint = 0;
int res = 0;
while (visited.size() != Graph.size()) {
visited[nowPoint] = 1;
for (int i = 0; i < Graph[nowPoint].size(); i++) {
if (visited.find(i) == visited.end() && Graph[nowPoint][i] != 0) {
distance[i] = std::min(distance[i], Graph[nowPoint][i]);
}
}
int minPoint, minValue = INT_MAX;
for (int i = 0; i < distance.size(); i++) {
if (visited.find(i) == visited.end() && distance[i] < minValue) {
minValue = distance[i];
minPoint = i;
}
}
if (visited.size() == Graph.size()) minValue = 0;
res += minValue;
nowPoint = minPoint;
}
return res;
}
适用情况
Prim算法很明显适用于边稠密的情况,因为它不需要遍历一遍边,只需要遍历一遍节点。