《第七章图无答案课件.ppt》由会员分享，可在线阅读，更多相关《第七章图无答案课件.ppt（74页珍藏版）》请在三一办公上搜索。
1、第七章 图,图的定义和术语图的存储结构图的基本操作-遍历应用最小生成树 拓扑排序 关键路径 最短路,7.1图的定义和术语,线性表、树和图：从关系、结构两个角度区分,图Graph;顶点Vertex;序偶;弧Arc;弧头B/弧尾ADigraph;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与B互为邻接点,有向图如A邻接到B无向
2、图顶点的度,如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,C,F,有向图的极大强连通子图称作它的强连通分量
3、。,强连通图、强连通分量(有向图),连通图的一个含有全部顶点的子图,如果连通且极小，则它必是一颗树(边数为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 且 表示从 v 到 w 有一条弧，可代表v认识w 或 v到w有路
4、等)基本操作,图的抽象数据类型定义逻辑结构,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,BFSTraverse(G,v,Visit();/从v起广度优先遍历图G，每个顶点
5、调用一次函数Visit,规则:访问起始顶点v,然后选取与v邻接的未访问的第一个顶点w,访问之，再选取与w邻接的未访问的第一个顶点，访问之。重复进行至当前节点的所有邻接点都被访问过，此时后退到最近访问过的定点，找其下一个未访问的邻接点访问，依次类推。如ABE FCD H说明:一次可遍历所有与v连通的顶点。若尚有顶点未访问(非连通图),则从其开始重复上述过程.对应树的先根遍历。可得深度优先生成树或森林以及连通分量递归描述：访问v,逐个从v未访问的邻接点出发递归遍历.,规则:访问v,访问v的全部未访问的邻接点,再逐个从这些邻接点出发重复.一次可遍历所有与v连通的顶点,若尚有顶点未访问则从其开始重复开
6、始上述过程.如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);/w是v的一个邻接点,返回v的“下一个邻接点”。/若w是v的最后一个邻接点，则返回“-1”。,图的数组表示(p161)(邻接
7、矩阵),图的邻接表表示(p163),有向图的十字链表表示(p164),无向图的邻接多重表表示(p166),7.2 图的存储结构,B,A,C,D,F,E,邻接矩阵:行、列各对应一个顶点,若第i行对应的顶点到第j列对应的顶点有弧相连则Aij=1,否则为0。n*n阶,A B C D E F,ABCDEF,1、图的数组表示-邻接矩阵adjacency matrix,邻接矩阵举例,A,B,E,C,D,无向图的邻接矩阵必为对称阵网的邻接矩阵Aij=wij或,/-图的数组(邻接矩阵)存储表示-typedef char VertexType;#define INFINITY 10000/最大值#define
8、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 struct/图的定义 VertexType vexsMAX_VERTEX_NUM;/顶点信息 AdjMatrix arcs;/邻接矩阵,存储弧信息,静态数组 int vexnu
9、m,arcnum;/顶点数，弧数 GraphKind kind;/图的类型标记 MGraph;/矩阵图,Status CreateGraph(Mgraph,图的创建,Status CreateUDN(Mgraph/无向网需将对称弧加入/END,B,A,C,D,F,E,ABCDEF,邻接矩阵优缺点：,易于求顶点度(区分有/无向图)、求邻接点，易判断两点间是否有弧或边相连,但不利于稀疏图的存储，因弧不存在时也要存储相应信息，且要预先分配足够大空间,小结：,掌握图的概念和基本术语掌握图的邻接矩阵存储，理解优缺点掌握图的深度优先遍历和广度优先遍历的规则会通过遍历求图的连通分量和深度优先、广度优先生成树
10、、生成森林作业：1 5,/-图的数组(邻接矩阵)存储表示-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 st
11、ruct/图的定义 VertexType vexsMAX_VERTEX_NUM;/顶点信息 AdjMatrix arcs;/邻接矩阵,存储弧信息,静态数组 int vexnum,arcnum;/顶点数，弧数 GraphKind kind;/图的类型标记 MGraph;/矩阵图,0 A 1 41 B 0 4 52 C 3 53 D 2 54 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,
12、E,C,D,typedef struct ArcNode int adjvex;struct ArcNode*nextarc;InfoType*info;ArcNode;,typedef struct VNode VertexType data;ArcNode*firstarc;VNode,AdjListMAX_VERTEX_NUM;,typedef struct AdjList vertices;int vexnum,arcnum;GraphKind kind;ALGraph;/邻接表图,Status CreateGraph(ALGraph,邻接表图的创建【补充】,Status Create
13、DN(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,稀疏图用邻接表存储相对节省空间对有向图易求顶点出度与邻接点,但求入度难.若只求入度可引入逆邻接表,也可结合邻接表与逆邻接表引入十字链表对无向图易求度,但边出现两次,为方便边操作可借助多重链表,A B C D E,3,0,3,4,2,0,01234,3、“有向图”的十字链表存储表示【选】,A,B,D,C,E,VexNode:,ArcBo
14、x:,具体邻接点顺序依赖输入顺序和图的创建程序，如逆序,3、“有向图”的十字链表存储表示【选】,typedef struct ArcBox int tailvex,headvex;InfoType*info;struct ArcBox*hlink,*tlink;/指向同弧头/尾的下一弧 ArcBox;,typedef struct VexNode/顶点的结构表示 VertexType data;ArcBox*firstin,*firstout;VexNode;,typedef struct VexNode xlistMAX_VERTEX_NUM;int vexnum,arcnum;OLGrap
15、h;,Status CreateDG(OLGraph G)scanf(/END,4、“无向图”的邻接多重表存储表示【选】,无向图的邻接表存储中，一条边出现两次，分别在两个顶点对应的链表中，对边的操作复杂。为此，将每条边(Vi,Vj)只用一个如下结点表示:顶点表示为：,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*
16、info;EBox;,4、“无向图”的邻接多重表存储表示【选】,typedef struct VexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;AMLGraph;/邻接多重表,typedef struct VexBox VertexType data;EBox*firstedge;/指向第一条依附该顶点的边 VexBox;,7.3图的遍历深度优先遍历,规则:访问v,逐个从v未访问的邻接点出发递归遍历，如此可遍历所有与v连通的顶点.若尚有顶点未访问(不连通),则从其开始重复上述过程.如ABEFCDH.,void DFS(G，v)VisitFunc
17、(v);visitedv=TRUE;for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if（!visitedw）DFS(G，w)；,void DFSTraverse(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主要操作是查找邻接点,当用邻接矩阵存储时查找某顶点的邻接点复杂
18、度为O(n),总复杂度O(n2);当邻接表存储时查找邻接点总复杂度为O(e),总复杂度为O(n+e)DFSTraverse每调用一次DFS所访问的顶点连通这些顶点关联的边构成一个连通分量.只保留走过的边得生成树或生成森林,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顶点对应的链表，画生成树时注意,求图的连通分量
19、、深度优先生成树或生成森林P171,DFSTraverse每调用一次DFS所访问的顶点连同这些顶点关联的边构成一个连通分量.只保留走过的边得生成树或生成森林,7.3 图的遍历广度优先遍历,BFSTraverse(G,v,Visit();,规则:访问v,访问v的各未访问的邻接点,之后逐个从这些邻接点出发重复上述操作。待与v连通的顶点访问毕再从另一顶点出发.如ABEHFCD实现：对各个顶点v：若其尚未访问则访问v,之后v入队。【队顶元素出队，逐个访问其尚未访问的邻接点，没访问完一个便入队】。重复【】中内容到队空,void BFSTraverse(Graph G,Status(*Visit)(int
20、 v)for(v=0;vG.vexnum;+v)visitedv=FALSE;InitQueue(Q);for(v=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入队。【队顶元素
21、出队，逐个访问其尚未访问的邻接点，每访问完一个便入队】。重复【】中内容到队空,每个顶点进一次队,出队时主要操作是查找邻接点,当用邻接矩阵存储时查找某顶点的各邻接点复杂度的为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,
22、f,7,14,8,5,3,16,21,Kuaskal算法直接找权值最小的边,若并入后构成回路则舍弃,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
23、,b,c,d,e,g,f,19,5,14,18,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后
24、代价置0struct VertexType 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号
25、结点并入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-网中应存在一个覆盖全部顶点的序列(全序),在该序列中顶点出现的顺序满足网中的先后关系(偏序)。一个全序就对应一
26、个合法的完整工序,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,
27、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)Pop(S,i);prin
28、tf(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.7prim算法注意画表，多张Kruscal算法，手工执行，直接给答案,a
29、,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,e,f,g,h,k,6,4,5,2,1,1,8,7
30、,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值更新后继ve值,“删除”如此重复,至图空或发现回路.实际是按拓扑序,S
31、tatus 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(汇点)普通顶点v,设W为其后继顶点集合，则 vl(v)=min vl(w)-dut(v,w)|wW 如何保证求v
32、l(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)return ERROR;vl0.G.vexnum-1=veG.vexnum-1;while(!StackEmpty(T)Pop(
33、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,);,栈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,
34、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,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,
35、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算法,迪杰斯特拉算法实现：,设辅助数组D,Dk存储当前所得从源到顶点k的最短路长度finalk标记k号顶点已并入SPvw标记源到v的最短路上w是否出现,for(v=0;vG.vexnum;+v)finalv=FALSE
36、;/最初未得源点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.vexnum;+i)min=INFINITY;for(w=0;wG.vexnum;+w)if(!finalw,迪杰斯特拉算法的实现,for(i=1;iG.vexnum;+i)/重n-1轮,每轮找最小的,并入更
37、新 min=INFINITY;for(w=0;wG.vexnum;+w)if(!finalw/复杂度O(n2),单源单终点问题也是O(n2),void ShortestPath_DIJ(MGraph G,int v0,PathMatrix,作业说明：,邻接表中表节点中存储的是下标非dataPrim算法执行过程看课件拓扑有序序列可能有多个，注意要求关键路径与单源最短路径求法看课件,7.6.2 任意一对顶点间的最短路径,每次以一个顶点为源点调用Dijkstra算法，复杂度O(n3)Floyd算法(复杂度同，但形式简单):D(k)ij表示从i顶点到j顶点的路径中”最短”路径的长度，要求该”最短路径”
38、内部各顶点的标号不超过kD(-1)ij表示i直接到j(内部无顶点)的情况,值G.arcsijD(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)ijk=-1,0,1,2,P(k)ijk=-1,0,1,2,D(-1)ij=G.arcsijD(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 Shor
39、testPath_FLOYD(MGraph G,PathMatrix,作业：,7.11Dijkstra求最短路。7.13Floyd求最短路。按照课件方式写出最终答案两个矩阵,回顾：,掌握图的邻接矩阵、邻接表存储结构定义，会画具体的存储结构图，理解各自的优缺点,会求图的入度掌握图的深度优先遍历和广度优先遍历的规则及算法实现，能写出遍历序列、画生成树或生成森林最小生成树:Prim算法(逐点)Kruskal算法(逐边)拓扑排序:选入度为0的顶点入栈,出栈并“删除”,至最后关键路径:初始化ve为0,找入度0的顶点入栈,出栈,更新其后继ve,“删除”并压入T,至图空或有回路；初始化vl为工期，按拓扑逆序
40、求各顶点的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）强连通分量；,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,ABCDEF,7.7请对7.2图的无向
41、带权图，（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图所示的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:分
42、别利用Dijkstra算法和Floyd算法求最短路径,7.22-23 试基于图的深度/广度优先策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i!=j)。,提示:求一条从顶点 i 到顶点 s 的简单路径,a,b,c,h,d,e,k,f,g,void DFSearch(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 栈顶元素出栈；,
