需要在某个城市的n个居民区之间铺设煤气管道,则在这n个居民区之间只要铺设n-1条管道即可。假设任意两个居民区之间都可以架设管道,但由于地理环境的不同,所需经费不同。选择最优的施工方案能使总投资尽可能少,这个问题即为求网的“最小生成树”。
2021-12-22 18:27:43 2KB 管道铺设最佳路径选择
1
【问题描述】 有一个快递小哥,准备所辖区域的n 个点派送快递,设这 n 个点间两两都有道路通行,小哥从某一派送点出发只需要走n-1条道路就可以走完n个点,但由于路况差异,每条道路所需的时间不同。选择最佳的送货路径使总路径时间最短,这个问题即为求网的“最小生成树”。 【基本要求】 网采用邻接矩阵为存储结构,以顶点对(i,j)的形式输出最小生成树的边。 【测试数据】 自行设计。 【实现提示】 可选用Kruskal 算法或Prim 算法来求网的最小生成树,无论哪一个算法都要选好恰当 的辅助数据结构,以存放边或顶点的集合。
2021-11-26 19:13:07 4KB 最佳路径选择
1