对如图8.36所示的连通图，分别用Prim和Kruskal算法构造其最小生成树。[img=274x239]17d998f628be613.png[/img]
采用Prim算法求解最小生成树的过程如图8.36.1所示。[img=750x425]17d998fb5f6aad7.png[/img]（2）采用Kruskal算法求解最小生成树时首先要对边进行由小到大进行排序，本题对边进行排序的结果是：[tex=12.286x1.286]OQgKMR50lemAktVCJCWrOC7JUrc8KQHIs5Bab4bA1bt1OJBekZX26vdshr2GILCM[/tex] [tex=28.286x1.286]4+v4SEaZRMwqLA9H6VcbHjtPJdlSyQYpBYrzITfyXss1WOomvJkKX2LXKape5/Nl5gw7QmjYEyN4iDQoiG7yPQh1TvcYQsmq36Ji7FukLRdFFuirVOC5+QT8DHiDjFUb[/tex][tex=7.357x1.286]8aORJrPaMIcHR4OgZexhvw8RrrMMaKkEXmpgOB7QGXY=[/tex]（D，G） 6、。根据Kruskal算法，构造最小生成树的过程如图[img=761x440]17d9997625b2cf6.png[/img]
举一反三
- 对下列连通图（如下图所示），请分别用Prim和Kruskal算法构造其最小生成树。[img=228x116]17e0ca69ff6c677.png[/img]
- 对于下图所示的网络，请分别用 Prim 算法和 Kruskal 算法构造该网络的最小生成树。[img=335x168]17a38e7f83a4bd6.png[/img]
- 对如图1所示的图，写出其邻接矩阵。画出用Kruskal算法构造其最小生成树的每步结果（只要求用图表示即可）。[img=238x203]17af780c2955764.png[/img]
- 【填空题】Prim算法和Kruskal算法是构造连通图最小生成树的两个典型算法，其中()算法适合于求稀疏图的最小生成树
- 智慧职教: 用Prim算法和Kruskal算法构造图的最小生成树，所得到的最小生成树（)
内容
- 0
用Prim和Kruskal两种算法构造图的最小生成树，所得到的最小生成树可能是不同的。
- 1
用Prim算法和Kruskal算法构造图的最小生成树，所得到的最小生成树可能相同，也可能不同。（ ）
- 2
用Prim算法和Kruskal算法构造图的最小生成树，所得到的最小生成树可能相同，也可能不同。（ ） A: 错 B: 对
- 3
构造最小生成树主要有两种算法：Prim算法和Kruskal算法。()
- 4
如下图所示,分别用Prim算法和Kruskal算法求出该图最小生成树的求解过程中边的序列。(Prim算法要求从A结点开始求解,,如(A,B)表示结点A,B之间的边)[img=288x288]17e0c9d66109655.png[/img]