用Prim算法(一个顶点一个顶点加入生成树)求下图的最小生成树。 (1)从顶点D开始,写出各顶点加入生成树的次序。 (2)画出最终的最小生成树。下面时图像链接https://p.ananas.chaoxing.com/star3/origin/63231706c95613bbf82f56709dff4037.png
时间: 2023-12-17 21:03:02 浏览: 148
PRIM算法,求最小生成树
3星 · 编辑精心推荐
1. 从D点开始,将D加入生成树。
2. 计算D点到其他点的边的权值,选择权值最小的边(比如DC),将C加入生成树。
3. 计算DC点集合外的点到DC集合内的点的边的权值,选择权值最小的边(比如CD和DB中的CD),将CD加入生成树。
4. 计算DCD点集合外的点到DCD集合内的点的边的权值,选择权值最小的边(比如DB和DE中的DB),将B加入生成树。
5. 计算DCDB点集合外的点到DCDB集合内的点的边的权值,选择权值最小的边(比如BD和BE中的BE),将E加入生成树。
6. 计算DCDBE点集合外的点到DCDBE集合内的点的边的权值,选择权值最小的边(比如EA和EF中的EA),将A加入生成树。
7. 计算DCDBEA点集合外的点到DCDBEA集合内的点的边的权值,选择权值最小的边(比如AF中的AF),将F加入生成树。
8. 此时所有点均已加入生成树,得到最小生成树。
最终的最小生成树为:DCDDBEA,权值为20。
阅读全文