考研

　　计算机考研的同学们，文都网校考研频道为大家提供计算机考研知识点，2018考研，你决定好了吗?来和小编一起看一下吧!希望对你们有所帮助!知识是不断的积累起来的，所以大家要赶快行动起来!

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

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

　　二、最短路径

　　最短路径问题是与日常生活密切相关的问题，例如：路线选择、计算机网络路由选择等，同时也是考试重点之一。下面分两种情况讨论了最短路径问题。

　　最短路径算法：

　　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]

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

　　2.Floyd算法

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

　　建议大家重点掌握这两种最短路径算法，并多做习题来巩固。

课程推荐：