关于最小生成树的问题：设G=（V，E）是无向连通带权图，即一个网络。E中每条边（v，w）的权为c[v][w]。若G的一个子图G’是一棵树且包含...
5星
- 浏览量: 0
- 大小:None
- 文件类型：None
简介：
本文探讨了最小生成树问题，针对给定的无向连通带权图G=(V,E)，旨在寻找一棵包含所有顶点的最轻边集，构建一个既连接所有节点又总权重最小的树结构。
设G=（V，E）是无向图联通带权图，即一个网络。E中每条边（v，w）的权为c[v][w]。如果G的一个子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权值总和称为该生成树的耗费。在所有生成树中，耗费最小的生成树被称为最小生成树。采用贪心策略可以直接求得给定网络的最小生成树。
实验方法： 使用贪婪法设计本问题的解决方案。
编程任务： 给定网络图，求其最小生成树。
输入格式：
节点个数和给定网络图的邻接矩阵表示方法，其中权值为65535表示两个节点间没有连接。否则数字表示节点间的权值。
输出格式：
输出最小生成树包括的所有边的总耗费。
示例输入：
1
9 59 69 96 11 72 100 17 43 28
9
示例输出：
106
全部评论 (0)
还没有任何评论哟~
