“最小代价通信网”案例实现与分析

摘要：《数据结构》是一门理论性和逻辑性较强的专业基础课程。而图论算法则是数据结构课程中的重难点部分。文章以“最小代价通信网”案例为例，详细介绍了图论算法通过具体案例学习的具体过程，并对案例的实现过程进行了详细分析，从而说明了案例学习法在数据结构课程中的重要性。通过案例可以更好的掌握算法涉及的理论知识，更全面深刻的理解算法思想。同时通过算法在实际问题中的应用及程序的实现，获得学习的成就感和兴趣。

关键词：数据结构；图论；算法；案例；最小代价通信网

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2013）17-4034-03

1736年，当Euler在访问俄罗斯的哥尼斯堡时，他发现著名的Konigsberg七桥”问题。在经过一年的研究之后，29岁的欧拉提交了《哥尼斯堡七桥》的论文，圆满解决了这一问题，同时开创了数学新一分支——图论[1]。事实上，图论算法不仅是《数据结构》课程中重要的知识点，甚至在计算机科学中都扮演着十分重要的角色，它给很多问题都提供了一种简单而系统的建模方式，从而将问题转化为图的问题并加以解决。

图论算法是《数据结构》课程中的重难点部分，主要有最小生成树、最短路径、拓扑排序和关键路径等算法，理论性较强、概念多，学习难度较大，学习完之后，普遍存在能够看得懂数据结构和算法描述，却难于根据实际问题动手设计数据结构及算法的问题[2]。可以借助案例学习法，通过具体案例的引入及详细实现过程的分析，继而引出数据结构中的抽象概念，帮助算法的理解和掌握，并进一步培养解决实际问题的能力。

图论算法的典型案例主要有：最小代价通信网、交通咨询系统、课程编排问题等，分别针对于最小生成树、最短路径、拓扑排序算法的学习。下面以“最小代价通信网”案例为例，详细介绍案例的实现过程及注意事项。

1 “最小代价通信网”案例

1.1 案例描述

“最小代价通信网”案例描述如下：假设要在n个城市之间建立通信网络，则连通n个城市只需要n-1条线路。如何在最节省经费的前提下建立这个通信网？数据结构中，可以用连通网来表示n个城市以及n个城市之间可能铺设的通信线路，其中网中各顶点表示城市，边表示城市之间的线路，边的权值表示铺设此线路相应的代价。

1.2 案例分析

该案例是最小生成树算法的典型应用，通过该案例的实现可以掌握图的最小生成树的概念，并领会构建最小生成树的两个经典算法——Prim算法和Kruskal算法。

对于n个顶点的连通网可以建立多棵不同的生成树，每一棵都可以表示一个通信网。要选择其中最小的一棵，使得总费用最低，实际上就是构造连通网的最小代价生成树的问题。在一个具有几个顶点的连通图G中，如果存在子图G'包含G中所有顶点和一部分边，且不形成回路，则称G'为图G的生成树，代价最小生成树则称为最小生成树。一棵生成树的代价就是树上各边的代价之和[3]。

此问题可以转化为已知无向连通网（图1），求其（图2）最小代价生成树的问题。而求最小生成树可以用Prim算法或者是Kruskal算法。此处以Prim算法为例详细介绍该案例的求解过程。

Prim算法思想如下：假设N=（V，E）是一个具有n个顶点的连通网，T=（U，TE）是所求的最小生成树，其中U是T的顶点集，TE是T的边集。算法从U={u0}（u0∈V），TE={ }开始，重复执行以下操作：在所有u∈V，v∈V-U的边（u，v）∈E中找一条代价最小的边（u0，v0）并入集合TE，同时v0并入U，直到U=V为止。此时TE中必有n-1条边，则T为N的最小生成树。

1.3 案例实现与分析

此案例的实现需要附设一个edges数组，记录从顶点集U到V-U的代价最小的边。每条边的信息包括边的起始顶点、终点和权值。从顶点u出发，利用Prim算法构造最小生成树的算法描述如下：

1）初始化edges数组，记录顶点u到网中其余顶点的代价最小的n-1条边。

2）将顶点u加入到U中。

3）当U不等于V时，重复以下操作：

从edges数组中选择一条代价最小的边。

将该边的终点加入到U中。

调整edges数组，使它始终记录顶点集U到V-U的代价最小边。

2 结论

通过最小代价通信网案例的具体实现，可以深刻的掌握最小生成树的概念，领会求最小生成树的算法Prim算法的思想，同时通过算法在实际问题中的应用及程序的实现，获得学习的成就感和兴趣。由此可见案例学习法在数据结构课程中的重要性。

参考文献：

[1] Bondy J A， Murty U S R. 图论及其应用[M].吴望名，李念祖，吴兰芳，等，译.北京：科学出版社，1984.

[2] 杨迎.《数据结构》案例式教学中的基本案例研究[J].中国科技纵横，2011（9）：146.

[3] 严蔚敏，吴伟民.数据结构：C语言版[M].北京：清华大学出版社，1997.