Prim算法
设G=(V,E)是连通带权图，V={1,2,…,n}。构造G的最小生成树的Prim算法的基本思想是：
(1)置S={1}
(2)只要S是V的真子集，就作如下的贪心选择
选取满足条件i ∈ S，j ∈ V-S，且c[j]最小的边，将顶点j添加到S中。一直到S=V时为止。
(3)选取到的所有边恰好构成G的一棵最小生成树。
2022-01-02 10:10:17
235KB
1
[问题描述]
某省自从实行了畅通工程计划后，终于修建了很多路。不过路多了也不好，
每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案 5
要比另一些方案行走的距离要短很多。这让行人很困扰。现在，请你设计程序计 算出要使这些城镇互通的最小路程长度。
2021-12-29 23:03:30
4KB
1
最小生成树问题在经济学中的应用在现实生活中，最小生成树有很高的实用价值。正确地理解掌握如何构造连通图的
最小生成树问题，将会给我们带来巨大的经济效益和社会效益。随着最小生成树理论与
算法的发展与完善，其在现实生活中的应用越来越广泛。求最小生成树问题能在很多经
济学问题中得到很好的应用。
2021-12-28 22:11:00
40KB
1
贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择,也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题也能产生整体最优解或者是整体最优解的近似解。本文首先介绍了贪心算法的核心、特点及算法本身存在的问题，接下来介绍了前人已经研究出来的成果，包括哈夫曼编码、单源最短路径、最小生成树等。然后结合实践，研究了多处最优服务次序问题、删数问题、汽车加油问题、最优合并问题、会场安排问题等。最后用代码实现其中的两个问题，对贪心算法的具体实现方法做了详细说明。
2021-12-26 17:01:19
313KB
1
程序要求：
1城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。
2表示城市间距离网的邻接矩阵（要求至少10个城市，20条边）
3最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。
2021-12-24 23:16:21
4KB
1