考研复习重点解析：图的应用 下面介绍一下图的基本应用： 一、最小生成树 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}，V
