《第八章图GraphsTheeighthchapterGraphs.ppt》由会员分享，可在线阅读，更多相关《第八章图GraphsTheeighthchapterGraphs.ppt（109页珍藏版）》请在三一办公上搜索。
1、第七章图（Graphs),图的基本概念图的存储表示图的遍历 最小生成树活动网络最短路径,图例,结点,边:(v2,v5),图的构成：结点集：V=v1,v2,v3,v4,v5,边集：E=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),图例,有向边V3：始点，v4:终点,图的构成：结点集：V=v1,v2,v3,v4,有向边集：E=,图的概念,图是由顶点(vertex)集合及顶点间的关系集合组成的一种数据结构：Graph(V,E)其中 V=x|x 某个数据对象 是顶点的有穷非空集合；E=|x,y V 是顶点之间关系的有穷集合，也叫做边(edge)的集合。
2、,有向图G1 V1=v1,v2,v3,v4,E1=,无向图G2 V2=v1,v2,v3,v4,v5,E2=,或者 E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),(a)G1=(V1,E1),(b)G2=(V2,E2),图的术语,v3邻接到v4,v4的入度ID(v4)=1,v1的出度OD(v4)=1,性质:入度之和=出度之和=边数,结点的度数:TD(v)=ID(v)+OD(v),v1和v4互为邻接点,v4的度数为2TD(v4)=2,度数之和=边数的二倍（因为每个边“贡献”了两个度数）,子图 设有两个图 G(V,E)和 G(V,E)。若 V V
3、 且 EE,则称 图G 是 图G 的子图。权 某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边,则此图为完全无向图。有 n 个顶点的有向图有n(n-1)条边,则此图为完全有向图。,路径:(1),(简单路径)(2),(环)(3),路径:在图 G(V,E)中,若存在边的序列(vi,vp1)、(vp1,vp2)、.、(vpm,vj)则称顶点序列(vi vp1 vp2.vpm vj)为从顶点vi 到顶点 vj 的路径。,路径长度 非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和,简单路径 若路径上各顶点
4、v1,v2,.,vm 均不互相重复,则称这样的路径为简单路径。回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合,则称这样的路径为回路或环。,连通图与连通分量 在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。,强连通图 在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。,生成树 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。,图的存储结构,邻接矩阵,存储原则:存储结点集和边集的信息.,（1）存储结点集；
5、（2）存储边集：存储每两个结点是否有关系。,图的存储结构,有向图的邻接矩阵,带权图的邻接矩阵,邻接矩阵表示法,在图的邻接矩阵表示中:有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。,#define MAX_VERTEX_NUM 20/最大顶点个数typedef struct VertexType vexsMAX_VERTEX_NUM；/顶点向量 int arcs MAX_VERTEX_NUM MAX_VERTEX_NUM；/邻接矩阵 int vexnum，arcnum；/图的当前顶点数和弧数 MGraph;,容易计算结点的度数;容易判定两个结点间是否有边相连;容易判定结
6、点之间是否有路径相连(计算Am);对于有向图，需要n个单元存储结点数据，n*n个单元存储邻接矩阵；无向图的邻接矩阵是对称的,可以压缩存储;存储量与结点数有关,与边数无关;若边数n2,则邻接矩阵是稀疏矩阵;,邻接表,每个结点拉出一个邻接边链表(以此结点为始点的所有邻接点),所有结点存储与一个表中,以A为始点的边链,以A为终点的边链,邻接表,图的邻接表存储表示,#define MAX_VERTEX_NUM 20 typedef struct ArcNode/单链表结点结构 int adjvex；/该弧所指向的顶点的位置 struct ArcNode*nextarc；/指向下一条弧的指针 InfoT
7、ype*info；/该弧相关信息的指针ArcNode；typedef struct VNode/顶点结构 VertexType data；/顶点信息 ArcNode*firstarc;/指向第一条依附该顶点的弧的指针VNode，AdjListMAX_VERTEX_NUM,Typedef struct/邻接表结构 AdjList vertices；int vexnum，arcnum；/图的当前顶点数和弧数ALGraph；,顶点vi的度恰为第i个链表中的结点数；在有向图中，第i个链表(出边表)中的结点个数是顶点的出度;,邻接表的特点,求入度必须遍历整个邻接表:在所有链表中其邻接点域的值为i的结点的
8、个数是顶点vi的入度。为了求入度的便利,可以建立逆邻接表,即链表为入边表;,设图中有 n 个顶点，e 条边，则用邻接表表示无向图时，需要 n 个顶点结点，2e 个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个顶点结点，e 个边结点。,邻接表,(B,D)边出现在D的边链表中,(B,D)边出现在B的边链表中,如果以边为处理对象,如删除一个边,则需扫描每个结点的边表,找到同一条边.,邻接多重表,将邻接表中代表同一个边的结点合并;边表合并为多重表;在邻接多重表中，每一条边只有一个边结点,为有关边的处理提供了方便。,边结点结构：,mark:记录是否处理过的标记;ivex,jvex:该边的两
9、顶点位置;ilink:指向下一条依附于顶点ivex的边；jlink:指向下一条依附于顶点jvex的边。,mark ivex jverx ilink jlink,typedef emnu unvisited，visited Visited；typedef struct EBox Visited mark；/访问标记 int ivex，jvex；/该边依附的两个顶点的位置 struct EBox*ilink，*jlink；/分别指向依附这两个顶点的下一条边 InfoType*info；/该边信息指针 EBox；,mark ivex jverx ilink jlink,data:存放与该顶点相关的信
10、息，firstedge:指示第一条依附于该顶点的边的指针,顶点结点的结构：,data firstedge,typedef struct VexBox VertexType data；EBox*firstedge/指向第一条依附该顶点的边 VexBox；,typedef struct VexBox adjmulistMAX_VERTEX_NUM；int vexnum，edgenum；/无向图的当前顶点数和边数 AMLGraph;,图的抽象数据类型,ADT Graph 数据对象V：V是具有相同特性的数据元素的顶点集。数据关系R：R=VR VR=|v，wV且P(v，w)，谓词 P(v，w)定义了弧的
11、意义或信息,基本操作P：CreateGraph(&G，V，VR)；初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。DestroyGraph(&G)；初始条件：图G存在。操作结果：销毁图G。,FirstAdjVex(G，v)；初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第一个邻接顶点。若顶点在G中 没有邻接顶点，则返回“空”。,InsertVex(&G，v)；初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中增添新顶点v。DeleteVex(&G，v)；初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的弧。,Next
12、AdjVex(G，v，w)；初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的(排在w之后的)下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。,InsertArc(&G，v，w)；初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添弧，若G是无向的则还增添对称弧。DeleteArc(&G，v，w)；初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧，若G是无向的则还删除对称弧。,DFSTraverse(G，v，Visit()；初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数。操作结果：从顶点v起深度优先遍历图G，并对每个顶
13、点调用函数Visit一次且仅一次。BFSTraverse(G，v，Visit()；初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数。操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。ADT Graph,习题,试分别在邻接矩阵和邻接表表示的图上实现运算FirstAdjVex(G，v)和 NextAdjVex(G，v，w)；试根据邻接矩阵建立图的邻接表表示。画出下图的邻接表表示：,图的遍历,图的遍历：从某个结点出发，访问图的每个结点恰好一次。,1）访问v,访问v的邻接点w1,访问w1的邻接点w2,直至wm的邻接点全被访问过；2）退回最近一个有未访问邻
14、接点的wk,重复1）直至所有与v连通的结点均被访问过。,深度优先从v开始遍历：,图的深度优先遍历,深度优先从v1开始遍历：,为了避免重复访问，设置一个标志顶点是否被访问过的辅助数组 visited：它的初始状态为 0；若顶点 i 被访问，则置 visited i 为 1，防止它被多次访问。,1）访问v；2）依次深度优先从v的未被访问的邻接点遍历，直至所有与v连通的结点均被访问过。,深度优先从v开始遍历：,void DFSTraverse(Graph G，Status(*Visit)(int v)/对图G作深度优先遍历。VisitFunc=Visit;/使用全局变量VisitFunc，使DFS不
15、必设函数指针参数 for(v=0；vG.vexnum；+v)visitedv=FALSE;/访问标志数组初始化 for(v=0；vG.vexnum；+v)if(!visitedv)DFS(G，v)；/对尚未访问的顶点调用DFS,void DFS(Graph G，int v)/从第v个顶点出发递归地深度优先遍历图G。visitedv=TRUE；VisitFunc(v)；/访问第v个顶点 for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G，w)；/对v的尚未访问的邻接顶点w递归调用DFS,算法分析,void DFS(Gr
16、aph G，int v)/从第v个顶点出发递归地深度优先遍历图G。visitedv=TRUE；VisitFunc(v)；/访问第v个顶点 for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G，w)；/对v的尚未访问的邻接顶点w递归调用DFS,每个结点最多调用一次,每个结点一次,循环工作量：寻找结点v的邻接点,时间复杂度：访问每个结点的时间：O(n);寻找每个结点的所有邻接结点工作量;设图中有 n 个顶点，e 条边。如果用邻接表表示图，沿 Firstedge link 链可以找到某个顶点 v 的所有邻接顶点 w。无向图有
17、 2e 个边结点，有向图有e个边，所以扫描边的时间为O(e);时间复杂度为O(n)+O(e)=O(n+e);如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n)+O(n2)=O(n2).,广度优先遍历,基本思想访问v1;访问v1的邻接点w1,w2,wm;依次访问w1,w2,的未被访问的邻接点，如此进行下去，直至访问完所有结点。,算法的实现需要设置一个数组visited标记结点是否访问过；设置一个队列纪录当前层访问的结点以备访问下一层结点。,取一个结点未访问结点v,访问v，标记，入队；（访问 v的所有邻接点）：取队头元素，每次取v的下一个
18、未访问的邻接点访问，标记并入队；重复2,直至队列空；如果图中仍然有未访问的结点，重复1，直至所有结点均已标记为访问过。,基本思想访问v1;访问v1的邻接点w1,w2,wm;依次访问w1,w2,的未被访问的邻接点，如此进行下去，直至访问完所有结点。,void BFSTraverse(Graph G，Status(*Visit)(int v)/按广度优先非递归遍历图G。/使用辅助队列Q和访问标志数组visited。for(v=0；vG.vexnum；+v)visitedv=FALSE；InitQueue(Q)；/置空的辅助队列Q,for(v=0；vG.vexnum；+v)if(!visitedv)
19、/v尚未访问 visitedv=TRUE；visit(v)；EnQueue(Q，v)；/v入队列 while(!QueueEmpty(Q)DeQueue(Q，u)/队头元素出队并置为u for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w)if(!Visitedw)/w为u的尚未访问的邻接顶点 visitedw=TRUE;Visit(w);EnQueue(Q,w);/if/while/if/BFSTraverse,复杂度与深度优先相同,图的连通性,对于连通的无向图，从一个结点出发可以访问所有结点；结点与遍历时通过的边构成图的生成树；,深度优先生成树,广度优先生
20、成树,对于不连通的无向图，则需从多个顶点出发访问；结点与遍历时经过的边构成生成树林。,深度优先生成森林,voidDFSTraverse(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)；,void DFS(Graph G，int v)visitedv=TRUE；VisitFunc(v)；for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visited
21、w)DFS(G，w)；,每次循环生成一棵树,void DFSForest(Graph G，CSTree/建立以p为根的生成树/DFSForest,T,q,p,void DFSForest(Graph G，CSTree/建立以p为根的生成树/DFSForest,T,q,p,第一次生成的树,上次生成的树,新生成的根结点,建立生成树,void DFSTree(Graph G，int v，CSTree*p=GetVex(G,w)，NULL，NULL；if(first)T-lchild=p；first=FALSE；else q-nextsibling=p；q=p；DFSTree(G,w,q)；/if/D
22、FSTree,T,p,q,最小生成树,问题：设在n个城市间建立通信网络，要求建设费用尽可能低。,模型：n个结点的图，结点连线的权表示建设两点间通信线路的费用。在此网络的生成树中找出建设费用最小的生成树。,最小生成树,设G是一个带权的无向图（网络），则G的生成树可能有多个，生成树各边的权之和称为生成树的权。网络G的具有最小权的生成树称为G的最小生成树。,模型：n个结点的图，结点连线的权表示建设两点间通信线路的费用。求此网络的最小生成树。,应用：设在n个城市间建立通信网络，要求建设费用尽可能低。,Prim算法,假设N=(V，E)是连通网，T=(U,TE)表示下列算法构造的N上最小生成树。算法从U=
23、u0(u0V)，TE=开始;重复执行下述操作,直至U=V为止：在所有 uU，vV-U的边(u，v)E中找一条权最小的边(u，v)，将v并入U，同时边(u，v)并入集合TE。,设N有n个结点.则算法结束时,T中必有n个结点,n-1条边.在2中,如果有相同权的边,可任选一条,故最小生成树不唯一.,例:求下图的最小生成树,初始状态:U=v0,循环:对于每个结点viU，在vi与U中所有结点的邻接边中找出权最小的边ei=(vi,uk),并在这些边ei中求出权最小的边,设为(vi,uk).将uk并入U,(vi,uk)并入构造中的生成树。,MST性质,定理:假设N=(V，E)是一个连通网,T=(U,TE)是
24、正在构造的生成树,若(u，v)是一条端点分别在U和V-U,并具有最小权值的边，则必存在一棵包含T和边(u，v)的最小生成树。,证明:用反证法.设任何包含T的最小生成树均不包含边e=(u,v).设T是一颗这样的树.将e加到T中必然得到一条回路:u,w1,wk,v,u 其中必然存在边e=(wp,wp+1),wpU,wp+1 U 去掉边e后打开回路,又形成一颗生成树T,因为W(e)=W(e),故T是一颗包含T和e的最小生成树.矛盾!,Prim算法的实现,需要设置一个数组closedge,纪录当前每个结点viU到达U的最小权边(vi,uk)的信息,即closedegei为(uk,minimumW(vi
25、,uk)|uk U)struct VertexType adjvex；VRType lowcost；closedge MAX_VERTEX_NUM,初始状态:U=v0 closedge0=(v0,0);/0表示相应结点属于U closedgei=(v0,W(vi,v0),在closedge中选择最小权的边。假设vk U是closedge中具有最小权边的结点,则置 closedgeklowcost=0,即将vk并入 U 修改closedge:对于vj U,只需考虑可能出现的新边(vj,vk)是否具有更小的权 closedgej=min closedgej.lowcost,W(vj,vk),循环：
26、,void MiniSpanTree_PRIM(MGraph G，VertexType u)/用普里姆算法从第u个顶点出发构造网G的最小生成树T，/输出T的各条边。假设用邻接矩阵存储G.k=LocateVex(G，u)；for(j=0；j0)边 printf(closedgek.adjvex,G.vexsk);/输出生成树的边 closedgek.lowcost=0;/第k个顶点并入U集 for(j=0;jG.vexnum;+j)if(G.acrskj.adjclosedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;/for/MiniSpanTree,时
27、间复杂度：O(n)+O(n2)=O(n2),Kruskal算法,假设连通网N=(V，E)，使用Kruskal构造最小生成树的算法：最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V，)，图中每个顶点自成一个连通分量在E中选择代价最小且顶点落在T中不同的连通分量上的边，将此边加入到T中；重复上述过程2，直至所有顶点都在同一连通分量上为止。,克鲁斯卡尔算法构造最小生成树的过程,Kruskal算法可以用堆来实现。设e是图的边数，则构造最小生成树的总时间代价是O(elog e).,可见，Prim算法适合于边数多的图，而Kruskal算法适合于边数少(en2)的图。,拓扑排序,一个工程(proj
28、ect)可分为若干个称作活动(activity)的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。,计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。,C1 高等数学 C2 程序设计基础 C3 离散数学 C1,C2 C4 数据结构 C3,C2 C5 高级语言程序设计 C2 C6 编译方法 C5,C4 C7 操作系统 C4,C9 C8 普通物理 C1 C9 计算机原理 C8,这样的工程流程图可以用一个有向图表示：,结点表示活动，
29、有向边(u,v)表示u必须先于v完成。这种图称为顶点表示活动的网（Activity on Vertices Nextwork），或者AOV网络.,AOV网是否存在有向环可以通过检查有向图是否存在一个拓扑排序，即将所有子工程排成线性序后所有的约束条件均满足：如果(u,v)是边，则v必然排在u之后。,AOV活动能够顺利进行的条件是不存在有向环;,工程能否顺利进行呢?,上述AOV网的一个拓扑排序是：C1,C2,C3,C4,C5,C6,C8,C9,C7如果一个学生每学期只能修一门课，则必须按照上述顺序进行。,拓扑序列：对于有向无环图（Directed Acyclic Graphs DAG）G=（V，E
30、），V里顶点的线性序列称作一个拓扑序列，如果该顶点序列满足：若在有向无环图G中从顶点Vi到Vj有一条边，则在序列中顶点Vi必在顶点Vj之前。,如果AOV网络存在一个拓扑序列，则该AOV网络中必定不会出现有向环，拓扑序列表示活动的一种顺序进行方式；相反，如果不存在拓扑序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。,拓扑排序方法：(1)在有向图中选一个没有前驱的顶点输出；(2)从图中删除该顶点和所有以它为始点的边。(3)重复上述两步，直至 全部顶点均已输出，排序完成；当前图中不存在无前驱的顶点，则有向图中存在环。,v5,v6-v1-v4-v3-v2-v5,如何在计算机中实
31、现?使用一个存放顶点入度的数组(indegree)，入度为零的顶点即为没有前驱的顶点。输出顶点及删除以它为始点的边的操作，则可以用终点的入度减1来实现。采用邻接表作有向图的存储结构。为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。,使用这种栈的拓扑排序算法可以描述如下：(1)初始化数组indegree;(2)建立入度为零的顶点栈;(3)当入度为零的顶点栈不空时,重复执行 从顶点栈中退出一个顶点,并输出之;从AOV网络中找到从这个顶点发出的边,边的终顶点入度减一;如果边的终顶点入度减至0,则该顶点进入度为零的顶点栈;(4)如果输出顶点个数少于AOV网络的顶点个数,则报告网络中存
32、在有向环。,栈:,C4C2,Status TopologicalSort(ALGraph G)/有向图G采用邻接表存储结构。若G无回路，则输出/G的顶点的1个拓扑序列并返回OK，否则ERROR。FindInDegree(G，indegree)；/对各顶点求入度indegree0.vernum-1 InitStack(S)；for(i=0；iG.vexnum；+i)if(!indegreei)Push(S，i)/建零入度顶点栈,s入度为0者进栈 count=0；/对输出顶点计数,while(!StackEmpty(S)Pop(S，i)；printf(i，G.verticesi.data)；+co
33、unt；/输出i号顶点并计数 for(p=G.verticesi.firstarc；p；p=p-nextarc)k=p-adivex；/对i号顶点的每个邻接点的入度减1 if(！(-indegreek)Push(S，k)；/若入度减为0，则入栈/for/while if(countG.vexnum)return ERROR；/该有向图有回路 else return OK；/TopologicalSort,复杂度分析,Status TopologicalSort(ALGraph G)/有向图G采用邻接表存储结构。若G无回路，则输出/G的顶点的1个拓扑序列并返回OK，否则ERROR。FindInD
34、egree(G，indegree)；/对各顶点求入度indegree0.vernum-1 InitStack(S)；for(i=0；iG.vexnum；+i)if(!indegreei)Push(S，i)/建零入度顶点栈,s入度为0者进栈 count=0；/对输出顶点计数,O(e),O(n),while(!StackEmpty(S)Pop(S，i)；printf(i，G.verticesi.data)；+count；/输出i号顶点并计数 for(p=G.verticesi.firstarc；p；p=p-nextarc)k=p-adivex；/对i号顶点的每个邻接点的入度减1 if(！(-ind
35、egreek)Push(S，k)；/若入度减为0，则入栈/for/while if(countG.vexnum)return ERROR；/该有向图有回路 else return OK；/TopologicalSort,循环次数:结点i的出度,循环次数:n次,因为每个结点入栈,出栈一次,总数:,分析算法：对有n个顶点和e条弧的有向图而言，建立求各顶点的入度的时间复杂度为O(e)；建零入度顶点栈的时间复杂度为O(n)；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈，出一次栈，入度减1的操作在WHILE语句中总共执行e次，所以，总的时间复杂度为O(n+e)。,用边表示活动的网络,在无有向环的带
36、权有向图中 用有向边表示一个工程中的各项活动(Activity)用边上的权值表示活动的持续时间(Duration)用顶点表示事件(Event)则这样的有向图叫做用边表示活动的网络，简称AOE(Activity On Edges)网络。,事件v7：活动a8,a9完成，a11可以开始,源点,汇点,关键路径,对AOE-网有待研究的问题是：(1)完成整项工程至少需要多少时间?(2)哪些活动是影响工程进度的关键?,事件8发生的条件：a10完成,并且 a11完成。,a11完成的时间：v7最早发生的时间+4,关键路径,事件8发生的时ve(8)：Maxve(6)+dut(a10),ve(7)+dut(a11)
37、,ve(4)：Maxve(1)+dut(),ve(2)+dut(),ve(i)：事件Vi 发生的最早可能时间dut(a):活动a需要的时间,ve(j)是从源点v0 到顶点vj 的最长路径长度，即vj最早的发生时间。ve(j)=ve(i)+dut()|是一个活动 j=1,2,n-1,从源点到汇点的最长路径叫做关键路径(Critical Path)。关键路径上的活动称为关键活动，即关键活动是不按期完成会影响整个工程进度的活动。,汇点v(n-1)最早发生的时间是源点v0到汇点的最长路径长度。,对于一个事件vi,el(i)表示不影响整个工程进度前提下事件vi最迟发生的时间：,vl(6)+dut()vl
38、(8)=ve(8),vl(4)+dut()vl(6)vl(4)+dut()vl(7),vl(i)=vl(j)-dut()|是一个活动 i=n-2,1,0,对于一个活动a=,e(a)=ve(i)是它最早可能开始的时间 l(a)=vl(j)-dut()是它最迟开始的时间 e(a)=l(a)的活动称为关键活动.,由此可以得到求AOE关键活动的算法.求el(i),i=1,2,n-1;求ev(i),i=n-2,1,0;对于每个活动a=,如果e(a)=l(a),则a为关键活动.,计算ev数组,ve(j)=ve(i)+dut()|是一个活动 j=1,2,n-1计算ve(j)需要先计算vj所有先驱结点最早发生
39、时间.,方法:在拓扑排序过程中计算ve.1.初始化ve:ve0.vexnum-1=0;2.在排序中,当结点i排序输出时,修改i的每个直接后继结点j的最早发生时间vej:if(r=vei+dut()vej)vej=r;当j的所有前驱已经排序时,vej便是所求的值.,data firstarc,Status TopologicalOrder(ALGraph G，Stack/i号顶点入T栈并计数 for(p=G.verticesi.firstarc；p；p=p-nextarc)j=p-adjvex；/对i号顶点的每个邻接点的入度减1 if(-indegreej=0)Push(S，j)；/若入度减为0
40、，则入栈 if(vei+*(p-info)vej)vej=vei+*(p-info)；/for*(p-info)=dut()/while if(countG.vexnum)return ERROR；/该有向网有回路 else return OK；/TopologicalOrder,求数组vl,vl(i)=vl(j)-dut()|是一个活动 i=n-2,1,0,类似地,计算vli需要先计算结点i的所有后继的vl值.,计算方法:当逆拓扑序输出一个结点 j时,修改vlj:对于 j的每个直接后继k,if(r=vlk-dut()vlj)vlj=r;,Status CriticalPath(ALGraph
41、 G)/G为有向网，输出G的各项关键活动。if(!TopologicalOrder(G，T)return ERROR；/初始化顶点事件的最迟发生时间 vl0.G.vexnum-1=veG.vexnum-1；/按拓扑逆序求各顶点的vl值 while(!StackEmpty(T)for(Pop(T,j),p=G.verticesj.firstarc；p；p=p-nextarc)k=p-adjvex；dut=*(p-info)；/dut if(vlk-dutvlj)vlj=vlk-dut；/for,输出关键活动,for(j=0；jnextarc)k=p-adjvex；dut=*(p-info)；ee
42、=vej；el=vlk-dut；tag=(ee=e1)?*：；printf(j，k，dut，ee，el，tag)；/输出关键活动/CriticalPath,在拓扑排序求vei和逆拓扑有序求vli时,所需时间为O(n+e),求各个活动的ek和lk时所需时间为O(e),总时间复杂度仍然是O(n+e)。,最短路径,问题的提出：一位旅客要从A城到B城他希望选择一条途中中转次数最少的路线；他希望选择一条途中所花时间最短的路线；他希望选择一条途中费用最小的路线；,这些问题均是带权图上的最短路径问题。,边上的权表示一站边上的权代表距离边的权代表费用,设G是带权有向图，称路径上的第一个顶点为源点(Source
43、)，最后一个顶点为终点(Destination)；一条路经的长度是路径上边的权之和；最短路径问题：如果从图中某一顶点出发到达另一顶点的路径可能不止一条，如何找到一条长度最小的路径。,单源最短路径问题：设G是带权(=0)有向图，给定一个顶点v，求v到其余顶点的最短距离。,最短路径的Dijkstra算法,Dijkstra算法基本思想:按路径长度的递增次序，逐步产生最短路径.设源点为v0首先求出v0为源点长度最短的一条最短路径，即具有最小权的边;求出源点到各个顶点下一个最短路径：设其终点是u，则v0到u的最短路径或者是边，或者由一条已求得的最短路径（v0v)和边构成；重复2直到从顶点v0到其它各顶点
44、的最短路径全部求出为止。,例：求v0其他各点的最短路径用S表示已求出最短路径的结点集初始状态：S=v0,第一条最短路径：(v0,v2)S=v0,v2,求下一条最短路径：先求v0到其他顶点vi的只经过S结点的路径：,v0-v1:v0-v3:(v0,v2,v3)60v0-v4:(v0,v4)30v0-v5:(v0,v5)100,第二条最短路径：(v0,v4)，S=v0,v2,v4,第一条最短路径：(v0,v2)S=v0,v2,求下一条最短路径：先求v0到其他顶点vi的只经过S结点的路径：,v0-v1:v0-v3:(v0,v2,v3)60,(v0,v4,v3)50v0-v5:(v0,v5)100,(
45、v0,v4,v5)90,第二条最短路径：(v0,v4)，S=v0,v2,v4,第三条最短路径：(v0,v4,v3)，S=v0,v2,v4,v3,第四条最短路径：(v0,v4,v3,v5)，S=v0,v2,v4,v3,v5,用S表示当前找到最短路径的终点集；引入一个辅助数组D,Dj表示当前找到的从源点v0到终点vi 的途径S的最短路径的长度。初始状态：S=v0若从源点v0到顶点vi有边，则Di为该边上的权值；若从源点v0到顶点vi 没有边，则Di为+,一般情况下，,Dijkstra算法,初始化S：S0=1;S1.n-1=0；初始化D:Dj=G.arcsv0vj;在D中选择最小的路径长度Dk,并将
46、vk加入S；修改数组D:Dj=minDj,Dk+arcsvkvj;重复3，4,n-1次，直至求得v0到所有顶点的最短路径,此外,增设一个数组P记录v0到各点的最短路径：若v0，w1,wk,v是v0到v的最短路径，则Pv=wk,Pwk=w(i-1),Pw1=v0.,void ShortestPath_DIJ(MGraph G，int v0，int/for,Dv0=0；Sv0=TRUE;/初始化，v0顶点属于S集/开始主循环，每次求得v0到某个/顶点v的最短路径，并加v到S集。for(i=1;iG.vexnum;+i)/其余G.vexnum-i个顶点 min=INFINITY；/当前所知离v0顶点
47、的最近距离 for(w=0；wG.vexnum；+w)if(!Sw)/w顶点在VS中 if(Dwmin)v=w；min=Dw；/w顶点离v0顶点更近 Sv=TRUE；/离v0顶点最近的v加入S集,for(w=0；wG.vexnum；+w)/更新当前最短路径及距离,min=Dv if(!Sw&(min+G.arcsvwDw)/修改Dw和Pw Dw=min+G.arcsvw；Pw=v；/if/for/ShortestPath_DIJ,时间复杂度：O(n2),Dijkstra算法要求图上的权是非负数，否则结果不正确；Dijkstra算法同样适用于无向图，此时一个无向边次相当于两个有向边。,求每对顶点
48、间的最短距离,问题的提法：已知一个各边权值均大于0的带权有向图，对每一对顶点 vi vj，求出vi 与vj之间的最短路径和最短路径长度。算法一：以每个顶点为源点，运行Dijkstra算法。,Floyd算法思想：先求只经过顶点v0的最短路径，再求只经过v0，v1的最短路径，一直到可以经过所有的顶点。一般地，设P1=(vi,vk),P2=(vk,vj)是只经过v0，.,v(k-1)的最短路径，则vi到vj的只经过v0,vk的最短路径或者是已求得的只经过v0,v(k-1)的最短路径，或者是P1+P2.,定义一个n阶方阵序列：D(-1),D(0),D(n-1).其中 D(-1)ij=G.arcsij；
49、D(k)ij=min D(k-1)ij，D(k-1)ik+D(k-1)kj,k=0,1,n-1D(0)ij是从顶点vi 到vj,中间顶点是v0的最短路径的长度,D(k)ij是从顶点vi 到vj,中间顶点的序号不大于k的最短路径的长度,D(n-1)ij是从顶点vi 到vj 的最短路径长度。,void ShortestPath_FLOYD(MGraph G，int&pathvexnum，int&Dvexnumvexnum)/用Floyd算法求有向网G中各对顶点v和w之间的最短路径（Pvw/是相应路径上w前一顶点的顶点号）及其带权长度Dvw。for(v=0；vG.vexnum；+v)/矩阵D与pat
50、h初始化 for(w=0；wG.vexnum；+w)Dvw=G.arcsvw；if(v!=w)&(DvwINFINITY)/从v到w有直接路径 pathvw=v；else pathvw=0；/v到w无路径,for(k=0；kG.vexnum；+k)for(v=0;vG.vexnum;+v)for(w=0;wG.vexnum;+w)if(Dvk+DkwDvw)Dvw=Dvk+Dkw;pathvw=pathkw;/缩短路径长度，经过k到w,时间复杂度：O(n3).,Floyd算法支持无向图；Floyd算法 支持负权值，但不支持含有负权值构成的回路。,本章重点内容,图的定义和术语；图存储结构：邻接矩
