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

Question

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里，然后生成一个残缺的最小生成树

Answer 1

liuyubobobo 2017-09-29 11:40:08

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

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

• 提问者 Brook_StudyMachine #1

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

• 提问者 Brook_StudyMachine #2

  非常感谢！

Answer 2

提问者 Brook_StudyMachine 2017-09-29 12:04:08

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算法一样了。