知识卡片

普通读书笔记卡 · 5654.d.1.f.4.l · 生成模型:未记录

最轻跨割边扩展生成树

理解等级:中级

在连通无向加权图中,从任意根开始维护已加入集合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)。

    参考来源

    - 位置:《算法技术手册》第6章《最小生成树算法》(spine1583;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1546.html;u170-ch06-013)。 - 结论依据:170全文及03313伪代码与执行状态实读。 - 原始内容:Prim算法告诉我们如何从一个图中构造一个MST,这个方法使用一种贪心的策略,每一步,这个算法都朝着解前进,但是不会推翻之前的决定。在扩展一棵树T时,Prim算法每次添加一条边,直到生成MST(可以证明这是最小的)。它随机选择一个开始顶点s∈V,将s添加到一个集合S中,那么生成树T的根节点将会是s。 - 位置:《算法技术手册》第6章《解决方案》(spine1583;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1546.html;u171-ch06-013)。 - 结论依据:171的03314–03315以inQueue标记顶点是否留在堆中,key[v]记录当前最轻连接边,并在改进时调用decreaseKey;堆实现仍需高效定位顶点才能保证对数更新。代码无条件写key[0],空图需单独处理。 - 原始内容:inQueue[],这个数组在顶点从优先队列中取出时被更新。在另外一个优化实现版本中,我们维护一个外部数组key[],记录队列中每一个顶点的优先级键值,这个值使得我们不需要从优先队列中寻找给定的顶点。 例6-9:基于二叉堆的Prim算法实现 - 位置:《算法技术手册》第6章《结论》(spine1584;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1547.html;u172-ch06-013)。 - 结论依据:172给出斐波那契堆 Prim 的 O(E+V log V) 摊销时间;它依赖相应堆操作的摊销界,常数和实现复杂性可能影响实际表现。稠密图上数组或矩阵 O(V²) 方案也值得比较。 - 原始内容:斐波那契堆来实现优先队列。这样性能将会提升到O(E+V*log V),相比二叉堆实现而言,性能获得了相当大的提升。 - 位置:《算法技术手册》第6章《分析》(spine1585;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1548.html;u173-ch06-013)。 - 结论依据:173对无向邻接表的边扫描按两条邻接项计数,至多 O(E) 次键更新;加上各顶点的出队与堆操作得到 O((V+E) log V),前提是堆可高效定位并降低指定顶点的键。 - 原始内容:decreaseKey操作将需要O(log q)的时间,q是优先队列中顶点的数目,q将会小于|V|。这个操作最多需要执行2*|E|次,在这种情况下,每一个顶点都会从优先队列中删除,图中的每一条边都会被访问两次。因此总性能是O((V+2*E)*log n)或者O((V+E)*log V)。