试利用Kruskal算法求出如下所示赋权图中的最小生成树(要求写出求解步骤)，并求此最小生成树的权。
试利用Kruskal算法求出如下所示赋权图中的最小生成树(要求写出求解步骤)，并求此最小生成树的权。
发布时间：2025-05-12 16:35:48
请在 下方输入 要搜索的题目：
推荐参考答案 (
由 快搜搜题库 官方老师解答 )
答案：
参考答案：用Kruskal算法求产生的最小生成树。步骤为:
w(v2,v6) =1,选(v2,v6)
w(v4,v5) =1,选(v4,v5)
w(v1,v6) =2,选(v1,v6)
w(v3,v5) =2,选(v3,v5)
w(v2,v3) =4,选(v2,v3)
最小生成树如图
最小生成树的权w(T)=1+1+2+2+4=10.
相关试题
- 1.试利用Kruskal算法求出如下所示赋权图中的最小生成树(要求写出求解步骤)，并求此最小生成树的权。
- 2.克鲁斯卡尔算法适用于求（ ）的最小生成树
- 3.在用Prim和Kruskal算法构造最小生成树时，前者更适合于（）。
- 4.最小生成树
- 5.从n 个顶点的连通图中选取n-1 条权值最小的边，即可构成最小生成树
- 6.Kruskal 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。
- 7.任何一个非空带权无向连通图（ ）最小生成树。
- 8.Prim算法和Kruskal算法都是贪心算法，但这两种算法都可以求得最小生成树问题得最优解 （ ）
- 9.用Kruskal算法求一个连通的带权图的最小代价生成树，在算法执行的某时刻，已选取的边集合TE＝{(1，2)，(2，3)，(3，5)}要选取下一条权值最小的边，不可能选取的边是（ ）。
- 10.对于含有n个顶点的带权连通图，它的最小生成树是指图中任意一个（ ）。
