while循环里要判断两个顶点是否同色，那在visit里面就不用判断是不是横切边了吧，反正从堆里取出来的时候还会被判断

Question

RT

Answer 1

liuyubobobo 2017-07-16 03:45:53

在 while 循环中每次选择了一条边e，并且通过if判断保证了后续处理的这条边e的两个端点一定不是同色的。之后选择了一个未被访问过的端点，在 visit 函数中查看这个端点的所有邻边。这些邻边中除了e之外，可能还有其他的边和这个端点同色，所以在 visit 中，使用这个if判断，可以提前将不符合要求的边剔除，优化算法。

如果没有这个if，算法确实是正确的。但是注意：我们的 Prim 算法在初始化的时候创造了一个最小堆，这个最小堆我们定义其容量最大为图中边的个数：

LazyPrimMST(Graph &graph):G(graph), pq(MinHeap<Edge<Weight>>(graph.E())){
    
    ...

}

如果在 visit 中删除这个 if 判断，不仅仅算法时间性能不优，从空间的角度，我们的最小堆中放入的边，有可能远远大于图中的边的个数。预估在这种情况下最小堆中最多会存入多少条边也是一个麻烦的事情（但不是不可以，可以想想看：））。但是我们现在的代码，可以保证，在最小堆中的边数不会超过图中的总边数：）

• 提问者 易萧 #1

  非常感谢！

• tobeabee #2

  老师，你说的空间上的”远远大于图中的边的个数“应该最多就是两倍吧，因为同一条边可能被存进去两次

• liuyubobobo 回复 tobeabee #3

  是的：）