第七章图--无答案.ppt

《第七章图--无答案.ppt》由会员分享，可在线阅读，更多相关《第七章图--无答案.ppt（75页珍藏版）》请在三一文库上搜索。

1、第 七 章 图,第七章 图,图的定义和术语 图的存储结构 图的基本操作-遍历 应用最小生成树 拓扑排序 关键路径 最短路,7.1图的定义和术语,线性表、树和图：从关系、结构两个角度区分,图Graph;顶点Vertex;序偶;弧Arc;弧头B/弧尾A Digraph;Undigraph;无序对(A,B):;Edge 网NetWork:弧或边含权的图,分有向网DN、无向网UDN (无向)完全图:边数最大的无向简单图,满足e=n*(n-1)/2 有向完全图:弧数最大的有向简单图, e=n*(n-1) 稀疏图(如enlogn) 稠密图,B,E,C,B,B,C,子图Subgraph,邻接点:无向图如A与

2、B互为邻接点,有向图如A邻接到B 无向图顶点的度,如TD(A)=2； 有向图分入/出度,度为两者之和 ID(A)=1,OD(A)=2,TD(A)=3,路径、简单路径、回路(环)、路径长度,术语,若无向图G中任意两个顶点之间都有路径相通，则称此图为连通图。 如能找到一条含全部顶点的路径则说明是连通图,无向图中的极大连通子图称作此图的连通分量。 极大指顶点尽量多,顶点连同其关联的边构成连通分量. 图本身连通则连通分量唯一,是自身,B,A,C,D,F,E,B,A,C,D,F,E,连通图,连通分量 (无向图),若任意两顶点间都存在一条有向路径，则称此有向图为强连通图。,A,B,E,C,F,A,B,E,

3、C,F,有向图的极大强连通子图称作它的强连通分量。,强连通图、强连通分量(有向图),连通图的一个含有全部顶点的子图,如果连通且极小，则它必是一颗树(边数为n-1)，称该树为原连通图的生成树。 破圈法可得生成树,对非连通图，由各个连通分量的生成树组成的集合称为此非连通图的生成森林。,B,A,C,D,F,E,生成树与生成森林（无向图）,注:树是含边数最小的连通图(n-1);图中若边少于n-1则必不连通；若图连通则至少含n-1条边；若图中多于n-1条边则必然含有回路。含n-1条边的连通图必然是树,ADT Graph 数据对象V：若干顶点组成的集合 数据关系R：R=VR VR| v,wV 且 表示从

4、v 到 w 有一条弧，可代表v认识w 或 v到w有路等) 基本操作 ,图的抽象数据类型定义逻辑结构,CreatGraph( / 按定义(V, VR) 构造图G,DestroyGraph( / 销毁图G,结构的建立和销毁,插入或删除顶点、弧,InsertVex( /在图G中增添新顶点v。,DeleteVex(/ 删除G中顶点v及其相关的弧。,InsertArc( /在G中增添弧，若G是无向的，则还增添对称弧,DeleteArc( /在G中删除弧，若G是无向的，则还删除对称弧,遍 历,DFSTraverse(G, v, Visit(); /从顶点v起深度优先遍历图G,对每个顶点执行一次Visit,

5、BFSTraverse(G, v, Visit(); /从v起广度优先遍历图G，每个顶点调用一次函数Visit,规则:访问起始顶点v,然后选取与v邻接的未访问的第一个顶点w,访问之，再选取与w邻接的未访问的第一个顶点，访问之。重复进行至当前节点的所有邻接点都被访问过，此时后退到最近访问过的定点，找其下一个未访问的邻接点访问，依次类推。如ABE FCD H 说明:一次可遍历所有与v连通的顶点。若尚有顶点未访问(非连通图),则从其开始重复上述过程.对应树的先根遍历。可得深度优先生成树或森林以及连通分量 递归描述：访问v, 逐个从v未访问的邻接点出发递归遍历.,规则:访问v,访问v的全部未访问的邻接

6、点,再逐个从这些邻接点出发重复.一次可遍历所有与v连通的顶点,若尚有顶点未访问则从其开始重复开始上述过程.如ABEHFCD 对应树层序遍历,可得广度优先生成树/森林,可得连通分量,实现?,对顶点的访问操作,LocateVex(G, u); / 若G中存在顶点与u”相等”，则返回该顶点在图中“位置”(下标或指针),GetVex(G, v); / 返回G中顶点v的值。,PutVex(/为G中顶点v赋值value。,对邻接点的操作,FirstAdjVex(G, v); /返回G中顶点v的“第一个邻接点”。若该顶点 /在 G 中没有邻接点，则返回“空”。,NextAdjVex(G, v, w); /

7、w是v的一个邻接点,返回v的“下一个邻接点”。 /若w是v的最后一个邻接点，则返回“-1”。,图的数组表示(p161)(邻接矩阵),图的邻接表表示(p163),有向图的十字链表表示(p164),无向图的邻接多重表表示(p166),7.2 图的存储结构,B,A,C,D,F,E,邻接矩阵:行、列各对应一个顶点,若第i行对应的顶点到第j列对应的顶点有弧相连则Aij=1,否则为0。n*n阶,A B C D E F,A B C D E F,1、图的数组表示-邻接矩阵adjacency matrix,邻接矩阵举例,A,B,E,C,D,无向图的邻接矩阵必为对称阵 网的邻接矩阵Aij=wij或,/-图的数组(

8、邻接矩阵)存储表示- typedef char VertexType; #define INFINITY 10000 /最大值 #define MAX_VERTEX_NUM 20 /最大顶点个数 typedef enumDG, DN, UDG, UDN GraphKind;/图类型 typedef struct ArcCell / 弧的定义 VRType adj; /邻接数,0/1或w/。VRType为int/double InfoType *info; /弧的附加信息数组 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struc

9、t / 图的定义 VertexType vexsMAX_VERTEX_NUM; /顶点信息 AdjMatrix arcs; / 邻接矩阵,存储弧信息,静态数组 int vexnum, arcnum; / 顶点数，弧数 GraphKind kind; / 图的类型标记 MGraph; /矩阵图,Status CreateGraph(Mgraph ,图的创建,Status CreateUDN(Mgraph /无向网需将对称弧加入 /END,B,A,C,D,F,E,A B C D E F,邻接矩阵优缺点：,易于求顶点度(区分有/无向图)、求邻接点，易判断两点间是否有弧或边相连,但不利于稀疏图的存储，

10、因弧不存在时也要存储相应信息，且要预先分配足够大空间,小结：,掌握图的概念和基本术语 掌握图的邻接矩阵存储，理解优缺点 掌握图的深度优先遍历和广度优先遍历的规则 会通过遍历求图的连通分量和深度优先、广度优先生成树、生成森林 作业：1 5,/-图的数组(邻接矩阵)存储表示- typedef char VertexType; #define INFINITY 10000 /最大值 #define MAX_VERTEX_NUM 20 /最大顶点个数 typedef enumDG, DN, UDG, UDN GraphKind;/图类型 typedef struct ArcCell / 弧的定义 VR

11、Type adj; /邻接数,0/1或w/。VRType为int/double InfoType *info; /弧的附加信息数组 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct / 图的定义 VertexType vexsMAX_VERTEX_NUM; /顶点信息 AdjMatrix arcs; / 邻接矩阵,存储弧信息,静态数组 int vexnum, arcnum; / 顶点数，弧数 GraphKind kind; / 图的类型标记 MGraph; /矩阵图,0 A 1 4 1 B 0 4 5 2 C 3 5 3

12、 D 2 5 4 E 0 1 F 1 2 3 ,B,A,C,D,F,E,顶点数组(头结点),邻接点链表,无向图中每条边出现两次,n个顶点e条边需n个头结点和2e个表结点,2、邻接表存储表示,1 4,2,3,0 1,2,0 1 2 3 4,A B C D E,邻接表举例,A,B,E,C,D,typedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode;,typedef struct VNode VertexType data; ArcNode *firstarc; VNode, AdjLis

13、tMAX_VERTEX_NUM;,typedef struct AdjList vertices; int vexnum, arcnum; GraphKind kind; ALGraph; /邻接表图,Status CreateGraph(ALGraph ,邻接表图的创建【补充】,Status CreateDN(ALGraph /邻接点与输入逆序排列P164,正序? /邻接点顺序依赖输入顺序和创建程序，“不给”默认正序 Return OK； /思考无向网的创建有何不同？,1 4,2,3,0 1,2,0 1 2 3 4,A B C D E,邻接表说明：,A,B,E,C,D,稀疏图用邻接表存储相对

14、节省空间 对有向图易求顶点出度与邻接点,但求入度难.若只求入度可引入逆邻接表,也可结合邻接表与逆邻接表引入十字链表 对无向图易求度,但边出现两次,为方便边操作可借助多重链表,A B C D E,3,0,3,4,2,0,0 1 2 3 4,3、“有向图”的十字链表存储表示【选】,A,B,D,C,E,VexNode:,ArcBox:,具体邻接点顺序依赖输入顺序和图的创建程序，如逆序,3、“有向图”的十字链表存储表示【选】,typedef struct ArcBox int tailvex, headvex; InfoType *info; struct ArcBox *hlink,*tlink;/

15、指向同弧头/尾的下一弧 ArcBox;,typedef struct VexNode / 顶点的结构表示 VertexType data; ArcBox *firstin, *firstout; VexNode;,typedef struct VexNode xlistMAX_VERTEX_NUM; int vexnum, arcnum; OLGraph;,Status CreateDG(OLGraph G) scanf( /END,4、“无向图”的邻接多重表存储表示【选】,无向图的邻接表存储中，一条边出现两次，分别在两个顶点对应的链表中，对边的操作复杂。为此，将每条边(Vi,Vj)只用一个如

16、下结点表示: 顶点表示为：,0 1 2 3,A B C D,A,B,D,C,e1,e2,e3,e4 将边看作有向的，如A-B,typedef struct Ebox VisitIf mark; / 访问标记 int ivex, jvex; /该边依附的两个顶点的位置 struct EBox *ilink,*jlink;/指向对应顶点为i,j的下一边 InfoType *info; EBox;,4、“无向图”的邻接多重表存储表示【选】,typedef struct VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AMLGraph; / 邻

17、接多重表,typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一条依附该顶点的边 VexBox;,7.3图的遍历深度优先遍历,规则:访问v,逐个从v未访问的邻接点出发递归遍历，如此可遍历所有与v连通的顶点.若尚有顶点未访问(不连通),则从其开始重复上述过程.如ABEFCDH.,void DFS(G，v) VisitFunc(v); visitedv=TRUE; for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w) if（!visitedw）DFS(G，w)； ,void DFSTrav

18、erse(Graph G, Status (*Visit)(int v) VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); /visited数组和VisitFunc函数为全局,每个顶点调用一次DFS,DFS主要操作是查找邻接点,当用邻接矩阵存储时查找某顶点的邻接点复杂度为O(n),总复杂度O(n2);当邻接表存储时查找邻接点总复杂度为O(e),总复杂度为O(n+e) DFSTraverse每调用一次DFS所访问的顶点连通

19、这些顶点关联的边构成一个连通分量.只保留走过的边得生成树或生成森林,a,b,c,h,d,e,k,f,g,a,c,h,k,f,e,d,b,g,a,b,c,d,e,f,g,h,k,2,3,4,5,6,0,7,0,7,0,8,0,7,8,1,2,3,8,5,5,4,7,注意邻接点的顺序作题时若未给出则默认为正序,实际上应依赖创建程序和输入顺序。若给出存储结构则以所给为准。如上例既非正序也非逆序,如h、k顶点对应的链表，画生成树时注意,求图的连通分量、深度优先生成树或生成森林P171,DFSTraverse每调用一次DFS所访问的顶点连同这些顶点关联的边构成一个连通分量.只保留走过的边得生成树或生成森

20、林,7.3 图的遍历广度优先遍历,BFSTraverse(G, v, Visit();,规则:访问v, 访问v的各未访问的邻接点,之后逐个从这些邻接点出发重复上述操作。待与v连通的顶点访问毕再从另一顶点出发. 如ABEHFCD 实现：对各个顶点v： 若其尚未访问则访问v,之后v入队。 【队顶元素出队，逐个访问其尚未访问的邻接点，没访问完一个便入队】。重复【】中内容到队空 ,void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v)visitedv = FALSE; InitQueue(Q); for ( v

21、=0; vG.vexnum; +v ) if ( !visitedv) ,Visit(v);visitedv = TRUE; EnQueue(Q, v); while (!QueueEmpty(Q) DeQueue(Q, v); for(w=FirstAdjVex(G,v); w=0;w=NextAdjVex(G,v,w) if ( ! visitedw ) /注意NextAdjVex返回值约定 Visit(w); visitedw=TRUE; EnQueue(Q, w); ,对各个顶点v： 若其尚未访问则访问v,之后v入队。【队顶元素出队，逐个访问其尚未访问的邻接点，每访问完一个便入队】。重

22、复【】中内容到队空,每个顶点进一次队,出队时主要操作是查找邻接点,当用邻接矩阵存储时查找某顶点的各邻接点复杂度的为O(n),总复杂度O(n2); 当用邻接表存储时查找邻接点复杂度为O(e),总复杂度为O(n+e),7.4.3 最小生成树P173,假设要在 n 个城市之间建立通讯联络网，不同城市间建立通讯设施的代价不同，如何在最节省经费的前提下建立这个通讯网？ 即找权值之和最小的极小连通子网，问题转换为在连通网中找一颗生成树，最小生成树,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,Kuaskal算

23、法直接找权值最小的边,若并入后构成回路则舍弃,Kruskal算法求最小生成树：,设N=(V,E)是连通网,求最小生成树 令T=(V,),各顶点自成一连通分量 在E中找代价最小的边,若该边的顶点落在不同连通分量上，则将其并入,依次类推至所有顶点到一个连通分量上 总O(eloge)，与n无关，适合稀疏图,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,7,12,18,19,Prim算法是逐个顶点并入，再据顶点找最小边；,普里姆Prim算法求最小生成树：,a,b,c,d,e,g,f,19,5,14,18,

24、27,16,8,21,3,a,e,12,d,c,b,7,a,a,a,19,14,18,0,e,12,e,e,8,16,0,d,3,d,d,7,21,0,c,5,0,e,0,g,d,0,f,0,设U代表已并入最小生成树中的顶点的集合，最初任选一点放入U。之后找U到U最小边，将对应新顶点并入，共N-1轮即可 从顶点u0开始,令U=u0, 初始化u0到其余各顶点距离 找最小的边输出,并入新顶点,赋0+更新表使U到非U距离更小。如上重复n-1次,构造下表对应的数组,每个元素对应一个顶点,元素取值是当前轮从U到该点最小边的信息(出发点下标和代价),顶点被并入U后代价置0 struct VertexTyp

25、e adjvex; /出发点名称 VRType lowcost; /代价 closedgeMAX_VERTEX_NUM;,a,a,a,19,14,18,0,e,12,e,e,8,16,0,d,3,d,d,7,21,0,c,5,0,e,0,d,0,void MiniSpanTree_Prim(MGraph G, VertexType u) /用普里姆算法从u出发求网G(邻接矩阵表示) 最小生成树,输出各边 k=LocateVex (G, u); closedgek.lowcost = 0; /将u并入U,赋0 for ( j=0; jk closedgek.lowcost=0; /将k号结点并入

26、U，赋0 for(j=0;jG.vexnum;+j)/据k号结点更新数组元素代价 if (G.arcskj).adjclosedgej.lowcost closedgej=G.vexsk,G.arcskj.adj; ,将初始点u并入U,初始化表;之后找小边并入,赋0+更新重复,复杂度为O(n2),与边数无关，适合稠密图,7.5.1 拓扑排序,AOV-网:顶点表示活动,弧表示活动间先后(依赖)关系的有向图. AOV-网用以表示工程或系统的施工计划，可据此判断工程是否可以顺利进行 AOV-网中应存在一个覆盖全部顶点的序列(全序),在该序列中顶点出现的顺序满足网中的先后关系(偏序)。一个全序就对应一

27、个合法的完整工序,B,D,A,C,由某个集合上的一个偏序得到该集合上的一个全序,该操作称为拓扑排序。若得到一个含全部顶点的拓扑有序序列(全序)则说明工程可顺利开展,不存在则说明图中存在有向回路,不合理,何谓拓扑排序,ABCD或ACBD均是含全部顶点的拓扑有序序列(DAG图),B,D,A,C,不存在含全部顶点的拓扑有序序列, 存在有向回路BCDB,从有向图中选取一没有前驱的顶点并输出之；,重复上述两步，至图空(得一全序)或图不空但不存在无前驱的顶点(得一有向环)。,从图中“删除”此顶点及所有从其出发的弧,如何进行拓扑排序,a,b,c,g,h,d,f,e,a,b,c,h,d,g,f,e,B,D,A

28、,C,A,入度0顶点入栈,出栈并据此更新入度,零入度者入栈重复至栈空,3、拓扑排序算法的实现,将入度为0的顶点入栈,出栈并据此更新入度,如此重复,Status TopologicalSort(ALGraph G) /G用邻接表存储,若G无回路则输出拓扑有序序列,返OK, 否则返ERROR. FindInDegree(G,indegree);/求各顶点入度存入数组indegree InitStack(S); for(i=0;iG.vexnum;+i) if(!indegreei) Push(s,i); count=0; /用以对输出的顶点进行计数 while (!StackEmpty(S) Po

29、p(S,i); printf(G.verticesi.data); +count; if(countG.vexnum)return ERROR; else return OK;,for(p=G.verticesi.firstarc;p!=NULL;p=p-nextarc) k=p-adjvex; - -indegreek; /更新入度 if(!indegreek) Push(S,w);/新的入度为零的顶点入栈 ,最初求入度O(e); 第一波顶点入栈O(n)；若为DAG图则每个顶点入栈、出栈各一次,O(n);入度减1的操作执行e次,故总复杂的度O(n+e),作业：,7.7 prim算法注意画表，

30、多张 Kruscal算法，手工执行，直接给答案,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,7,12,18,19,作业：,9 对下图执行教材中的拓扑排序算法，写出得到的拓扑有序序列,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,7.5.2 关键路径,AOE网：顶点表示状态，弧表示活动，弧权表示完成活动所需时间。用以估算工程的完成时间 问:最短工期多长？哪些活动是影响工期的“关键活动”,a,b,c,d

31、,e,f,g,h,k,6,4,5,2,1,1,8,7,2,4,4,源点,汇点,1,7,4,关键路径(长度最长的路径)决定工期 关键活动:工程正常开展最早开始时间等于最迟开始时间的活动 ee(act) =ve(头) 与 el(act)=vl(尾) - dur(act),ve(源点)=0. 对普通顶点v,设W为其前驱顶点集则 ve(v)=max ve(w)+dut(w,v) | wW 如何保证求ve(v)时ve(w)已经求出？,关键活动求取求各点最早到达时间ve(x),a,b,c,d,e,f,g,h,k,6,4,5,2,1,1,8,7,2,4,4,实现:各顶点ve初始化为0,找无前驱顶点,据其ve

32、值更新后继ve值, “删除”如此重复,至图空或发现回路.实际是按拓扑序,Status TopologicalOrder(ALGraph G，Stack ,各点ve初始化为零,无前驱顶点入栈,出栈并据其更新后继ve,“删除”重复,0,0,0,0,0,0,0,0,0,6,4,5,7,11,5,7,15,14,18,a,b,c,d,e,f,g,h,k,6,4,5,2,1,1,8,7,2,4,4,找无前驱顶点,据其ve值更新后继ve, “删除”重复,用栈实现的拓扑排序序列为:a - d - f - c - b - e - h - g - k,关键活动求取求最晚到达时间vl(x),vl(汇点)=ve(汇

33、点) 普通顶点v,设W为其后继顶点集合，则 vl(v)=min vl(w)-dut(v,w) | wW 如何保证求vl(v)时vl(w)已求出？,a,b,c,d,e,f,g,h,k,6,4,5,2,1,1,8,7,2,4,4,1,7,4,各顶点vl初始化成工期，按拓扑逆序(T的出栈顺序)逐个更新该元素的vl,关键活动:调用函数求Ve,按拓扑逆序求Vl,求ee/el并输出,Status CriticalPath(ALGraph G) /求个顶点最晚到达时间计入全局数组vl,同时输出各活动的最早、迟时间等信息 InitStack(T); if(!TopologicalOrder(G,T)retur

34、n ERROR; vl0G.vexnum-1=veG.vexnum-1; while(!StackEmpty(T) Pop(T,j); for(p=G.verticesj.firstarc; p!=NULL; p=p-nextarc) k=p-adjvex; dut=*(p-info); /对应活动的持续时间 if( vlk-dut nextarc) k=p-adjvex; dut=*(p-info); ee=vej; el=vlk-dut/活动的最早/迟开始时间 if(ee=el) printf(j,k,dut,ee,el, ); else printf(j,k,dut,ee,el, );

35、,栈T: a - d - f - c - b - e - h - g - k,a,b,c,d,e,f,g,h,k,6,4,5,2,1,1,8,7,2,4,4,1,7,4,0,0,0,0,0,0,0,0,0,6,4,5,7,11,5,7,15,14,18,18,18,18,18,18,18,18,18,18,16,14,8,6,6,10,8,0,7,各顶点vl初始化成工期，按拓扑逆序(T的出栈顺序)逐个更新该元素的vl,0,6,4,5,7,7,15,14,18,18,14,16,10,7,8,6,6,0,0,0,0,6,4,5,7,7,7,15,14,14,16,0,2,3,6,6,8,8,7,

36、10,0,2,3,0,2,6,3,0,2,6,6,3,0,2,8,6,6,3,0,2,8,8,6,6,3,0,2,7,8,8,6,6,3,0,2,10,7,8,8,6,6,3,0,2,16,10,7,8,8,6,6,3,0,2,14,16,10,7,8,8,6,6,3,0,2,e,e,作业题1：7.10 求关键活动,单源最短路径,每一对顶点之间的最短路径,7.6 最短路径（P187）,集合S存放已找到最短路的顶点 将源并入S,初始化源到V-S中各顶点的最短路径 在V-S中找长度最小的顶点并入S,据此更新 再找再更新,共重复n-1轮,7.6.1单源最短路径-Dijkstra算法,迪杰斯特拉算法实

37、现：,设辅助数组D,Dk存储当前所得从源到顶点k的最短路长度 finalk标记k号顶点已并入S Pvw标记源到v的最短路上w是否出现,for(v=0;vG.vexnum;+v) finalv=FALSE;/最初未得源点v0到v的最短路 for(w=0;wG.vexnum;+w) pvw=FALSE;/最短路最初为空,不含任何顶点 Dv=G.arcsv0v; /根据v0更新 if(DvInFINITY)pvv0=TRUE;pvv=TRUE;/更新路径 Dv0=0; finalv0=;,初始化:初始化各数组,源点并入并更新,每次循环都找距离最小新顶点并入S，更新，重复n-1轮,for(i=1;iG

38、.vexnum;+i) min=INFINITY; for(w=0;wG.vexnum;+w) if(!finalw ,迪杰斯特拉算法的实现,for(i=1;iG.vexnum;+i)/重n-1轮,每轮找最小的,并入更新 min=INFINITY; for(w=0;wG.vexnum;+w) if(!finalw /复杂度O(n2),单源单终点问题也是O(n2),void ShortestPath_DIJ(MGraph G,int v0,PathMatrix ,作业说明：,邻接表中表节点中存储的是下标非data Prim算法执行过程看课件 拓扑有序序列可能有多个，注意要求 关键路径与单源最短路

39、径求法看课件,7.6.2 任意一对顶点间的最短路径,每次以一个顶点为源点调用Dijkstra算法，复杂度O(n3) Floyd算法(复杂度同，但形式简单): D(k)ij表示从i顶点到j顶点的路径中”最短”路径的长度，要求该”最短路径”内部各顶点的标号不超过k D(-1)ij表示i直接到j(内部无顶点)的情况,值G.arcsij D(0)ij表i到j中间可含0号顶点;D(2)ij表示i到j中间可含0、1、2号顶点; D(n-1)ij意味着什么？ D(k)ij=minD(k-1)ij , D(k-1)ik+D(k-1)kj ,Floyd算法求任意顶点间的最短路,D(k)ij k=-1,0,1,2

40、,P(k)ij k=-1,0,1,2,D(-1)ij=G.arcsij D(k)ij=minD(k-1)ij, D(k-1)ik+D(k-1)kj . k=0,1,n-1,Pijk表示i到j最短路中k号顶点是否出现,7,6,5,Floyd算法,void ShortestPath_FLOYD(MGraph G, PathMatrix ,作业：,7.11Dijkstra求最短路。 7.13Floyd求最短路。 按照课件方式写出最终答案两个矩阵,回顾：,掌握图的邻接矩阵、邻接表存储结构定义，会画具体的存储结构图，理解各自的优缺点,会求图的入度 掌握图的深度优先遍历和广度优先遍历的规则及算法实现，能写

41、出遍历序列、画生成树或生成森林 最小生成树:Prim算法(逐点) Kruskal算法(逐边) 拓扑排序:选入度为0的顶点入栈,出栈并“删除”,至最后 关键路径:初始化ve为0,找入度0的顶点入栈,出栈,更新其后继ve, “删除”并压入T,至图空或有回路；初始化vl为工期，按拓扑逆序求各顶点的vl 最短路径:Dijstra算法(Dv+finalv+Pvw); Floyd算法(Dkij+Pijk) 推荐习题:1 3 4 5 7 9 10 11 13/ 22 23 24,7.1已知如右图所示的有向图，请给出该图的,（1）各顶点的入/出度；,（2）邻接矩阵；,（3）邻接表、逆邻接表、十字链表,（4）强

42、连通分量；,1,2,4,5,3,6,推荐习题,7.3-5给定一个图或者图的邻接矩阵，求其某顶点出发的深度优先遍历或广度优先遍历序列，并给出其深度/广度优先生成森林,d,f,g,h,e,c,b,a,4,9,4,5,6,3,6,2,7,5,5,5,5,3,A B C D E F,7.7请对7.2图的无向带权图， （1）写出它的邻接矩阵，并按普里姆算法求其最小生成树 （2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树,d,f,g,h,e,c,b,a,4,9,4,5,6,3,6,2,7,5,5,5,5,3,9.对下图执行教材中基于栈的拓扑排序算法，写出得到的拓扑有序序列,7.10对于题7.3图所示

43、的AOE网络，计算各活动弧的e(ai)和e(aj)函数值，各事件（顶点）的ve(vi)和vl(vj)函数值；列出各条关键路径。,a,A,B,C,D,F,G,I,H,E,J,w,k,1,1,3,3,3,2,4,4,6,6,6,6,7,8,5,8,11,4,10,9,9,21,10,12,7.11/13:分别利用Dijkstra算法和Floyd算法求最短路径,7.22-23 试基于图的深度/广度优先策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i!=j)。,提示: 求一条从顶点 i 到顶点 s 的简单路径,a,b,c,h,d,e,k,f,g,void DFSear

44、ch( int v, int s, char *PATH) / 从第v个顶点出发递归地深度优先遍历图G， / 求得一条从v到s的简单路径，并记录在PATH中 visitedv = TRUE; /访问第 v 个顶点 Append(PATH, v);/第v个顶点加入路径 for (w=FirstAdjVex(v); w!=0; w=NextAdjVex(v) ) if (w=s) found = TRUE; Append(PATH, w); else if (!visitedw) DFSearch(w, s, PATH); if (!found) Delete (PATH);/从路径上删除顶点 v ,7.24 试利用栈的基本操作编写，按深度优先搜索策略遍历一个强连通图的非递归形式的算法。算法中不规定具体的存储结构，而将图Craph看成是一种抽象的数据类型,void DFS（G，v） 访问顶点 v ;顶点 v 入栈； while(栈不空) if（找到第一个与栈顶元素邻接的、未访问的顶点 w） 访问顶点 w ;顶点 w 入栈； else 栈顶元素出栈； ,