数据结构与算法（C 语言版）.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 应 用 例11-6 假设要在n个城市之间建立通信网络，而连通n个城市一般只需要n?1条线路。由于n个城市中的每两个城市之间都可建立一条线路，因此最多可有n(n?1)/2条线路可供选择，本问题的关键就是如何在这些可能的n(n?1)/2条线路中选择n?1条线路，使得建立这个通信网的成本最低。 n个城市及其可能设置的通信线路可用连通网来表示，其中网的顶点表示城市，边表示两城市之间的线路，边的权值表示相应的代价。由于具有n个顶点的连通网包含多棵不同的生成树，每一棵生成树都可能是一个通信网且总代价不同，因此该问题的解决就要通过构造连通网的最小代价生成树来完成。 例11-6 最小代价生成树的构造有多种算法，其中大多数算法利用了最小生成树的MST性质，该性质描述为：假设N = (V, {E})是一个连通网，U是顶点集V的一个非空子集，若(u, v)是一条具有最小权值（代价）的边，其中u∈U，v∈V?U，则必存在一棵包含边(u, v)的最小生成树。 上述性质可用反证法来证明。假设网N的任何一棵最小生成树都不包含(u, v)，设T是连通网上的一棵最小生成树，当将边(u, v)加入到T中时，由生成树的定义，T中必存在一条包含(u, v)的回路。另外，由于T是生成树，则在T上必存在另一条边(u, v)，其中u∈U，v∈V?U，且u和u之间，v和v之间均有路径相通，删去边(u, v)，便可消除上述回路，同时得到另一棵生成树T。因为(u, v)的代价不高于(u, v)，所以T的代价亦不高于T，T是包含(u, v)的一棵最小生成树。由此与假设矛盾。 下面介绍的普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法，就是两个利用MST性质构造最小生成树的算法。 应 用 最小代价生成树 1. 普里姆（Prim）算法 假设N = (V, {E})是连通网，TE是N上最小生成树中边的集合。算法从U = {u0}（u0∈V），TE = {}开始，重复执行下述操作：在所有u∈U, v∈V?U的边(u, v)∈E中找一条代价最小的边(u0, v0)并入集合TE中，同时v0并入U中，直至