老师，关于prim的问题

来源：8-3 Prim算法的第一个实现（Lazy Prim）

相信光变成光

2019-01-07

老师，图片一是我的prim的逻辑，图片二是你。箭头所指的部分，是咱们的不同。我的理解是：v在visit函数里已经标记为true了，所以判断就没必要判断v了，判断w就可以啦。这是我的想法，还是我这样做会有漏洞?
图片描述

写回答

1回答

liuyubobobo

2019-01-07

visit(int v)这个函数中的v只是一个名字，和你取出的一条边e调用的e.v()完全不是一回事儿。你可以理解成我们可以把visit(int v)改成visit(int x)。

取出一条边，这条边的两个短点都必须检查，不能保证e.v()已经标记。

liuyubobobo

xs_wang

插入最小堆的边，不一定是“第一个顶点”已经被标记过的。这里的关键是，边中的两个顶点是没有顺序的。比如执行过一次visit(2)，可能会将(2, 4)这条边放进堆中，也将(0, 2)这条边放在堆中。但是从对中取出这两条变得时候，不能保证e.w()这个端点值一个就是没有标记的4，另一个就是没有标记的0。我们只知道e.v()和e.w()肯定有一个被标记了。所以我们要找到没有被标记的那个端点进行visit：）

2019-01-30

共2条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程

相似问题

课件中演示的最小生成树的边是不是选取错误？

回答 2

lazy prim的时间复杂度疑问

回答 1

麻烦请问老师一道Hackerrank上的题，求回复，谢谢

回答 2

老师，关于堆排序的问题

回答 1

关于nlp的问题

回答 1

打开慕课网App查看更多内容