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

lhf2018kaoyan

图是数据结构科目中难度最大的重点章节，在这两年的考试中也作为重点来考查。图这部分内容概念多、算法多、难度大。这就需要大家深刻理解每个知识点，多做练习，抓住规律，才能很好地解答这部分试题。图这部分要求大家掌握图的定义、特点、存储结构、遍历、图的基本应用等内容。图这部分的重点和难点是图的基本应用，这在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]表示弧上的权值。若不存在则置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]