数据结构（Java语言描述） 案例11 城市间公路网建设最经济方案.docx
版权申诉
5星 · 超过95%的资源 162 浏览量
2022-07-14
04:00:27
上传
评论 1
收藏 43KB DOCX 举报 
《数据结构（Java 描述）》课程案例
——案例 11 城市间公路网建设最经济方案
11.1 案例描述
有 6 个城市（A、B、C、D、E、F），已知城市间拟建公路的建设费用，如图 11-1
所示，要建设一个连接 6 个城市的交通网，使得任意两个城市间都可以直接或间接
互达，使总的费用最少。请问：如何建造 6 个城市间的公路网？
图11-1 城市间公路建造费用图
11.2 算法分析
把问题“城市间公路网建设最经济方案”中的城市看作顶点，拟建设的公路看
成边，拟建设公路的费用作为权值，构造一个无向带权图。求“城市间公路网建设
最经济方案”，就是求无向带权图的最小生成树，可以应用普里姆算法或克鲁斯卡尔
算法来完成，我们选择普里姆算法来完成这项工作。
11.3 算法实现
public class Example2 {
static final int maxWeight = 10000;//权值无穷大
public static void prim(AMGraph<Character> g, MinSpanTreeNode[]
minSpanTree)throws Exception {
int n = g.getNumOfVertices(); //图中顶点个数
int minCost; //最小权值
int[] lowCost = new int[n]; //最小代价数组
int k = 0;
for (int i = 1; i < n; i++) {
资源评论
狗头君思考人生2023-01-10非常有用的资源，有一定的参考价值，受益匪浅，值得下载。
2201_757725452023-06-28资源很受用，资源主总结的很全面，内容与描述一致，解决了我当下的问题。
