最优生成树在实际中的应用(2)
时间:2019-10-27 12:04 来源:毕业论文 作者:毕业论文 点击:次
说明了第1.点,我们来说明第2.点.这一点比较简单,由于Kruskal算法中的第(1)步要求所选取的边 是尽可能小的.所以,我们每一次执行时都市选取权最小的边.那么,最后所得到的生成树 的权和自然也是最小的,所以,我们得到的是最优生成树. 说完了理论,下面要做的,就是把理论应用于实际,为我们的现实生活提供一些便利. 我们先来看一个较为简单的例子.现在,假如我们要在五个城市(A,B,C,D,E)之间建造通信网了系统.我们知道,这五个城市两两之间都是可以建立通信系统的,而且,任意两个城市之间的通信系统的建造费用与它们之间的距离成正比.具体的造价为一万元每千米(10000/km).我们把每两个城市之间通信系统的建造费用罗列出来 (责任编辑:qin) |