如下图所示,分别用Prim算法和Kruskal算法求出该图最小生成树的求解过程中边的序列。(Prim算法按照从1号结点开始求解,,如(1,2)表示结点1,2之间的边)[img=338x228]17e44ab5fcd830c.png[/img]
Prim:(1,2),(2,3),(2,4),(2,6),(4,5)或者:(1,2),(2,3),(3,4),(2,6),(4,5)Kruskal:(2,3),(2,4),(2,6),(1,2),(4,5),或者:(2,3),(3,4),(2,6),(1,2),(4,5)
举一反三
- 如下图所示,分别用Prim算法和Kruskal算法求出该图最小生成树的求解过程中边的序列。(Prim算法要求从A结点开始求解,,如(A,B)表示结点A,B之间的边)[img=288x288]17e0c9d66109655.png[/img]
- 如下图所示,分别用Prim算法和Kruskal算法求出该图最小生成树的求解过程中边的序列。(Prim算法要求从A结点开始求解,,如(A,B)表示结点A,B之间的边)[img=288x288]17e44a1a9192296.png[/img]
- 关于最小生成树的求解,下面说法正确的是: A: 求解最小生成树的常用算法有Prim算法,Kruskal算法 B: Kruskal算法每次选择一条最小且不会构成回路权边直至构成一个生成树 C: Prim 算法从一个结点的子图开始构造生成树:选择连接当前子图和子图外结点的最小权边,将相应结点和边加入子图,直至将所有结点加入子图 D: 从算法复杂度的角度看,Kruskal算法适用于稀疏图,Prim算法适用于稠密图
- 对于下图所示的网络,请分别用 Prim 算法和 Kruskal 算法构造该网络的最小生成树。[img=335x168]17a38e7f83a4bd6.png[/img]
- 对下列连通图(如下图所示),请分别用Prim和Kruskal算法构造其最小生成树。[img=228x116]17e0ca69ff6c677.png[/img]
内容
- 0
如下图所示的无向带权图,请分别按Prim算法和Kruskal算法求最小生成树。
- 1
最小生成树可用prim和kruskal两种算法求解。( )
- 2
对如图8.36所示的连通图,分别用Prim和Kruskal算法构造其最小生成树。[img=274x239]17d998f628be613.png[/img]
- 3
如下图所示的带权图:(1)按照普里姆算法,从顶点v1出发,生成最小生成树,按生成次序依次写出各条边;(2)按照克鲁期卡尔算法,生成最小生成树,按生成次序依次写出各条边;(3)画出该图最小生成树,并求出它的权值之和。[img=387x175]17e44a231db4817.jpg[/img]
- 4
下列关于最小生成树的说法中,正确的是( )。(1)最小生成树的代价唯一(2)权值最小的边一定会出现在所有的最小生成树中(3)用Prim算法从不同顶点开始得到的最小生成树的形态一定相同(4) Prim算法和Kruskal算法得到的最小生成树的形态总不相同。 A: 仅(1) B: 仅(2) C: 仅(1) (3) D: 仅(2) (4)