老师，关于prim的问题

Question

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

Answer 1

liuyubobobo 2019-01-07 16:44:42

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

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

• xs_wang #1

  我也有相同疑问。
  图是无向图，adjIterator 以已标记点进行迭代，插入最小堆的边，它的第一个顶点是已经被标记过的，语句 if( !marked[e.v()] ) 中 e.v() 取得是第一个顶点，所以 marked[e.v()] 为 true，执行完 mst.push_back( e ) 后可直接执行 visit( e.w() ) ，程序结果也是一样的。
  不知道说的对不对，请bobo老师指教。

• liuyubobobo 回复 xs_wang #2

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