知识卡片
最轻跨割边扩展生成树
在连通无向加权图中,从任意根开始维护已加入集合S;为每个未加入顶点记录来自S的最轻连接边,每次选择全局最轻的跨割边,将新顶点并入并更新候选。割性质保证这样的选择可扩展为最小生成树。
Prim比较单条连接边,不像Dijkstra比较从源点累计的路径距离;最小生成树可以包含负权边。断开图不能得到覆盖所有顶点的一棵树,需要分别处理连通分量形成森林。
171的03314–03315以inQueue标记顶点是否留在堆中,key[v]记录当前最轻连接边,并在改进时调用decreaseKey;堆实现仍需高效定位顶点才能保证对数更新。代码无条件写key[0],空图需单独处理。
172给出斐波那契堆 Prim 的 O(E+V log V) 摊销时间;它依赖相应堆操作的摊销界,常数和实现复杂性可能影响实际表现。稠密图上数组或矩阵 O(V²) 方案也值得比较。
173对无向邻接表的边扫描按两条邻接项计数,至多 O(E) 次键更新;加上各顶点的出队与堆操作得到 O((V+E) log V),前提是堆可高效定位并降低指定顶点的键。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 最轻跨割边扩展生成树
- · 解决方案
- · 结论
- · 分析
原书出处 · 4 处
- · 查看原书依据
Prim算法告诉我们如何从一个图中构造一个MST,这个方法使用一种贪心的策略,每一步,这个算法都朝着解前进,但是不会推翻之前的决定。在扩展一棵树T时,Prim算法每次添加一条边,直到生成MST(可以证明这是最小的)。它随机选择一个开始顶点s∈V,将s添加到一个集合S中,那么生成树T的根节点将会是s。
- · 查看原书依据
inQueue[],这个数组在顶点从优先队列中取出时被更新。在另外一个优化实现版本中,我们维护一个外部数组key[],记录队列中每一个顶点的优先级键值,这个值使得我们不需要从优先队列中寻找给定的顶点。 例6-9:基于二叉堆的Prim算法实现
- · 查看原书依据
斐波那契堆来实现优先队列。这样性能将会提升到O(E+V*log V),相比二叉堆实现而言,性能获得了相当大的提升。
- · 查看原书依据
decreaseKey操作将需要O(log q)的时间,q是优先队列中顶点的数目,q将会小于|V|。这个操作最多需要执行2*|E|次,在这种情况下,每一个顶点都会从优先队列中删除,图中的每一条边都会被访问两次。因此总性能是O((V+2*E)*log n)或者O((V+E)*log V)。