图图的应用.ppt

第7章 图 主要内容 7.4　图的应用 7.4.1 图的连通性问题----最小生成树 普里姆（Prim）算法 克鲁斯卡尔（Kruskal）算法 7.4.2 有向无环图的应用 关键路径 7.4.3 最短路径问题 求一结点到其余各顶点的最短路径－迪杰斯特拉(Dijkstra)算法 求任意一对顶点间的最短路径－弗洛伊德算法 7.4.1图的连通性问题 生成树 判断练习 判断练习 最小生成树 普里姆算法－－加点法 普里姆算法 普里姆算法见： 克鲁斯卡尔算法 图示 克鲁斯卡尔算法的练习 7.4.3 最短路径 (Shortest Path) 1.求某一顶点到其余各顶点的最短路径 迪杰斯特拉（Kijkstra）算法 2.求任意一对顶点间的最短路径 弗洛伊德（ Floyd ）算法 迪杰斯特拉（Kijkstra）算法 问题的提法： 给定一个带权有向图D与源点 v，求从 v 到D中其它顶点的最短路径。限定各边上的权值大于或等于0。 Dijkstra算法----贪心 首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。 课后作业 P245面4题 所有顶点对之间的最短路径 赋权有向图所有顶点对之间的最短路径问题: 给定一个赋权有向图G=(V,E),其中每一条边u,v的权a[u][v]是一个非负实数. 要求对任意的顶点有序对u,v找出从顶点u到顶点v的最短路径长度. Floyd算法的基本思想: 设V={1,2, … n}, 设置一个n× n矩阵c, 初始化时c[i][j]=a[i][j]。 然后, 在矩阵c上做n次迭代。经k次迭代之后，c[i][j]的值是从项点i到顶点j,且中间不经过编号大于k的顶点的最短路径长度。在c上做第k次迭代时，用下面公式计算： c[i][j]=min{c[i][j] , c[i][k] +c[k][j]} void Floyd (AdjMatrix g, WeightType dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM], VertexSet path[MAX_VERTEX_NUM][MAX_VERTEX_NUM]) { //g＿带权有向图的邻接矩阵表示//path－vi到vj的当前最短路径 //dist－vi到vj的当前最短路径长度 for (i=0;ig.vexnum;i++) for (j=0;jg.vexnumn;j++) { InitList(path[i][j]); dist[i][j]=g.arcs[i][j].adj;//初始化dist[][] if(dist[i][j]INFINITY){ //若有边，则在path中保存路径信息 AddTail(path[i][j], g.vertex[i]); AddTail(path[i][j], g.vertex[j]);}} for(k=0;ig.vexnum;k++) for(i=0;jg.vexnum;i++) for(j=0;jg.vexnum;j++) { if (dist[i][k]+dist[k][j]dist[i][j] ){ dist[i][j]=dist[i][k]+dist[k][j]; path[][]=JoinList(path[i][k],path[k][j]); } } } 拓扑序列 AOV-网：用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网（Activity On Vertex Network），简称为AOV-网。 如225面表7-2 课程关系，用顶点表示课程，弧表示先决条件，则表7－2可用一个有向无环图表示。见图 拓扑序列 拓扑序列：在有向图G=（V，{E}）中， V中顶点的线性序列（vi1,,vi1,,vi3,…，vin）称为拓扑序列。 此序列必须满足：对序列中任意两个顶点vi、vj，在G中有一条从vi到vj的路径，则在序列中vi必排在vj之前。 拓扑序列 方法： （1）从有向图中选一个无前驱的顶点输出； （2）将此顶点和以它为起点的弧删除； （3）重复（1）、（2），直到不存在无前驱的顶点； （4）若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。 关键路径 AOE-网：在有向图中，用顶点表示事件，用弧表示活动，弧的权值表