考研复习重点解析：图的应用 下面介绍一下图的基本应用： 一、最小生成树 1．最小生成树的基本概念 最小生成树：边的权值总和最小的生成树。最小生成树有很多重要的`应用。《计算机学科专业基础综合辅导讲义》中就介绍了最小生成树在城市建设中的应用。 2．最小生成树的性质 最小生成树性质：设 G=(V，E)是一个连通网络，U 是顶点集 V的一个真子集。若(u，v)是 G 中一条“一个端点在 U 中(例如：u∈U)，另一个端点不在 U 中的边(例如：v∈VU)，且(u，v)具有最小权值，则一定存在 G 的一棵最小生成树包括此边(u，v)。 3．构造最小生成树的算法 目前已有不少构造最小生成树的算法，建议大家重点复习两种常用的构造最小生成树的算法：普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。 二、 最短路径 最短路径问题是与日常生活密切相关的问题，例如：路线选择、计算机网络路由选择等，同时也是考试重点之一。《计算机学科专业基础综合辅导讲义》分两种情况讨论了最短路径问题。 最短路径算法： 1．Dijkstra 算法 Dijkstra 算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 定义 G=(V,E)，定义集合 S 存放已经找到最短路径的顶点，集合T 存放当前还未找到最短路径的顶点，即有 T=VS： 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∈VS}，Vj 就是当前求得的一条从 Vs 出发的最短路径的终点。令 S=S∪{Vj} （3）修改从 Vs 出发到集合 VS 上任一顶点 Vk 可达的最短路径长度。假如 D[j]+edges[j][k]D[k]则修改 D[k]为 D[k]=D[j]+edges[j][k] 重复操作(2)(3)共 n1 次。由此求得从 Vs 到图上其余各顶点的最短路径。 2．Floyd 算法 Floyd 算法的核心思想是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 建议大家重点掌握这两种最短路径算法，并多做习题来巩固。《计算机学科专业基础综合辅导讲义同步练习》中一道娱乐中心选址问题就是应用 Floyd 算法来求解的。 三、 拓扑排序 1．拓扑排序基本概念 AOV 网...
