2011年计算机数据结构考研复习重点解析：图的应用

计算机来源：文都教育 2010-12-23　

图是数据结构科目中难度最大的重点章节，在这两年的考试中也作为重点来考查。图这部分内容概念多、算法多、难度大。这就需要大家深刻理解每个知识点，多做练习，抓住规律，才能很好地解答这部分试题。图这部分要求大家掌握图的定义、特点、存储结构、遍历、图的基本应用等内容。图这部分的重点和难点是图的基本应用，这在09年和10年的考试中有所体现。图的基本应用包括：最小生成树、最短路径、拓扑排序、关键路径等。09年考试中重点考查了最短路径的判断与证明。建议大家把图的基本应用作为重点来复习。

下面介绍一下图的基本应用：

一、最小生成树

1．最小生成树的基本概念

最小生成树：边的权值总和最小的生成树。最小生成树有很多重要的应用。《计算机学科专业基础综合辅导讲义》中就介绍了最小生成树在城市建设中的应用。

2．最小生成树的性质最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中一条“一个端点在U中(例如：u∈U)，另一个端点不在U中的边(例如：v∈V-U)，且(u，v)具有最小权值，则一定存在G的一棵最小生成树包括此边(u，v)。

3．构造最小生成树的算法

目前已有不少构造最小生成树的算法，建议大家重点复习两种常用的构造最小生成树的算法：普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。

二、最短路径

最短路径问题是与日常生活密切相关的问题，例如：路线选择、计算机网络路由选择等，同时也是考试重点之一。《计算机学科专业基础综合辅导讲义》分两种情况讨论了最短路径问题。

最短路径算法：

1．Dijkstra算法

Dijkstra算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

定义G=(V,E)，定义集合S存放已经找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点，即有T=V-S ：

Dijkstra算法描述如下：

（1）假设用带权的邻接矩阵edges来表示带权有向图，edges[i][j]表示弧<Vi, Vj>上的权值。若<Vi, Vj>不存在则置edges[i][j]=∞（计算机上用一个允许的最大值代替）。S为已经找到的从Vs出发的最短路径的终点集合，它初始化为空集。那么，从Vs出发到图上其余各顶点（终点）Vi可能达到的最短路径长度的初值为：D[i]=deges[s][i] Vi∈V

（2）选择Vj，使得D[j]=Min{D[i]|Vi∈V-S}，Vj就是当前求得的一条从Vs出发的最短路径的终点。令S=S∪{Vj}

（3）修改从Vs出发到集合V-S上任一顶点Vk可达的最短路径长度。如果D[j]+edges[j][k]<D[k]则修改D[k]为D[k]=D[j]+edges[j][k]

重复操作(2)(3)共n-1次。由此求得从Vs到图上其余各顶点的最短路径。

2．Floyd算法

Floyd算法的核心思想是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

建议大家重点掌握这两种最短路径算法，并多做习题来巩固。《计算机学科专业基础综合辅导讲义同步练习》中一道娱乐中心选址问题就是应用Floyd算法来求解的。

三、拓扑排序

1．拓扑排序基本概念

AOV网是一种可以形象地反映出整个工程中各个活动之间前后关系的有向图。在AOV网中，若不存在回路，则所有活动可排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，那么该序列为拓扑序列。

2．拓扑排序特点：

（1）拓扑序列不是唯一的。

（2）AOV网不一定都有拓扑序列。在AOV网中如果出现了有向环，则意味着某项活动应以自己作为先决条件，这是不对的，工程将无法进行。