当整个图不是都联通的时候，kruscal算法是不是有问题？

来源：9-3 实现Dijkstra算法

Brook_StudyMachine

2017-09-29

LazyPrim,Prim,Kruscal三个算法对同一个稀疏有权无向图进行最小生成树

0 [(0-5,wt:0.21)]
1 [(1-4,wt:0.32), (1-2,wt:0.32)]
2 [(2-3,wt:0.63), (2-4,wt:0.02), (2-1,wt:0.32)]
3 [(3-2,wt:0.63)]
4 [(4-1,wt:0.32), (4-2,wt:0.02)]
5 [(5-0,wt:0.21)]
components: 2
no path
no path
no path
no path
0 -> 5 -> ok
====================
lazyprim:
mst: [(0-5,wt:0.21)]
mst weight: 0.21
prim:
mst: [(0-5,wt:0.21)]
mst weight: 0.21
kruscal
mst: [(2-4,wt:0.02), (0-5,wt:0.21), (4-1,wt:0.32), (2-3,wt:0.63)]
mst weight: 1.18

可以看到，0和5联通，与其他定点不联通。

lazyprim 和prim 从0开始计算，最小生成树就只有一个edge

而kruscal直接把所有边都加到minHeap里，然后生成一个残缺的最小生成树

写回答

2回答

liuyubobobo

2017-09-29

已采纳

对！我们的算法是建立在联通图上的！最小生成树这个概念本身也是建立在连通图上的！

对于不连通的图，需要先求出其联通分量，然后根据你所要具体求解的问题，在相应的联通分量上运行最小生成树算法。

Brook_StudyMachine

非常感谢！

2017-09-29

共2条回复

Brook_StudyMachine

提问者

2017-09-29

root = 0
for( int i = 0 ; i < graph.V() ; i ++ ){    
    typename Graph::adjIterator adj(graph,i);    
    for( Edge<Weight> *e = adj.begin() ; !adj.end() ; e = adj.next() ) {   
        if( component(root, e->v()) || component(root, e->w()) ) {    
            if ( e->v() < e->w() )
                pq.insert(*e);
        }
    }
    
}

找到解决办法了，创建一个图Component实例，在把edge放入最小堆之前，判断以下是否和root联通（假设root为0），如果联通就放入，不联通就不放，就解决这个问题，和prim算法一样了。

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

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

11187 学习 · 1614 问题

查看课程

相似问题

请问设置算法通常会设置一个常数，怎么设置？有什么用？

回答 1

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

回答 2

为什么对小数据量直接插入排序要比快排更快呢？

回答 1

7-2 两个疑问

回答 1

__partition中while循环实现及算法学习方法的请教

回答 1

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