设无向图G，用普里姆算法构造最小生成树。要求画出其最小生成树，并给出该最小生成树上边的集合。[img=213x210]17e0c986060189d.png[/img]
举一反三
- 设无向图G(如右图所示),给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。[img=152x130]17e44a101d9d726.png[/img]
- 将下面的图采用普里姆算法构造其最小生成树,并给出算法思想。
- 叙述普里姆(Prim)算法的思想，并画出下图的最小生成树。[img=317x277]17e0ce4786954ee.png[/img]
- 求图的最小生成树有两种算法，普里姆算法适合于求稠密图的最小生成树
- 如下图所示的带权图：(1)按照普里姆算法，从顶点v1出发，生成最小生成树，按生成次序依次写出各条边；(2)按照克鲁期卡尔算法，生成最小生成树，按生成次序依次写出各条边；(3)画出该图最小生成树，并求出它的权值之和。[img=387x175]17e44a231db4817.jpg[/img]