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

Question

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

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

1 2 3 4 5 6 7 8 9 10 11

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