图的定义和术语

第七章图7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径1精选课件第七章图在线性结构中，数据元素之间是一对一的线性关系，除第一个数据元素和最后一个数据元素之外，每个数据元素只有一个直接前驱和一个直接后继。在树型结构中，数据元素之间是一对多的层次和分支的关系，除根结点外，每个数据元素都只有一个直接前驱〔即双亲结点〕，但每个数据元素都可能有多个直接后继〔即孩子结点〕。然而在图型结构中，数据元素之间的关系是任意的，是多对多的关系，既图中任意两个结点之间都可能相关。2精选课件7.1图的定义和术语图中的数据元素通常称为顶点。图G由两个集合V和E组成，通常记为G＝(V，E)其中，V是图中顶点的有穷非空集合，E是V中顶点间的边的有穷集。

除此之外，也通常将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。假设E(G)为空，那么图G只有顶点而没有边。图可分为无向图和有向图两类。3精选课件7.1图的定义和术语无向图：图中的每条边都是无方向的。在无向图中，一条无向边是由两个顶点组成的无序对，通常用圆括号表示。例如〔vi，vj〕表示一条无向边，在无向图中，〔vi，vj〕和〔vj，vi〕是两条相同的无向边。〔无向〕完全图：任意两个顶点之间都有一条无向边的无向图。〔无向〕完全图是含有n个顶点和n(n-1)/2条边的无向图。4精选课件7.1图的定义和术语如以下图G是一个无向图BCAFED图G可记作：G＝〔V，E〕，其中V＝{A,B,C,D,E,F}E={(A,B),(A,E),(B,F),(B,E),(C,F),(C,D),(D,F)}假设(vi，vj)是一条无向边，那么称顶点vi和vj互为邻接点，或称vi和vj相邻接；同时称边(vi，vj)依附于顶点vi和vj，或称边(vi，vj)与顶点vi和vj相关联。5精选课件7.1图的定义和术语有向图：图中的每条边都是有方向的。在有向图中，一条有向边是由两个顶点组成的有序对，通常用尖括号表示。例如<vi，vj>表示一条有向边，vi是边的起始点，vj是边的终点。因此，<vi，vj>和<vj，vi>是两条不同的有向边。有向边也称为弧，边的起始点称为弧尾，终点称为弧头。6精选课件7.1图的定义和术语如以下图G是一个有向图ABECF图G可记作：G＝〔V，E〕，其中V＝{A,B,C,D,E,F}E={<A,B>,<A,E>,<B,C>,<C,F>,<F,A>,<F,B>,<E,C>}假设＜vi,vj＞是图中的一条有向边，那么称顶点vj是vi的领接点，或称顶点vi邻接到vj，或顶点vj邻接自顶点vi，并称弧＜vi,vj＞依附于顶点vi和vj，或称弧＜vi,vj＞与顶点vi和vj相关联。7精选课件7.1图的定义和术语有向完全图：任意两个顶点之间都有一对相向的有向边的有向图。即含有n个顶点和n(n-1)条弧〔有向边〕的有向图。ABECF1597211132权：与图的边或弧相关的数。这些权可以表示从一个顶点到另一个顶点的距离或者消耗。网：弧〔或边〕带权的图称为网。8精选课件7.1图的定义和术语子图：给定图G1=〔V1，E1〕、图G2=〔V2，E2〕，假设V1是V2的子集，E1是E2的子集，那么称G1是G2的子图。例：ABECF图GAB图G1CF图G3E图G2CE图G49精选课件7.1图的定义和术语无向图中顶点v的度：指的是和v相关联的边的数目，通常记为D(v)。BCAFED例：在右图中D(B)=D(F)＝

3D(A)=D(C)

=D(D)=D(E)=2结论无向图中：顶点的度之和=边数的两倍10精选课件7.1图的定义和术语有向图中顶点v的度分为入度和出度。顶点v的入度：以顶点v为终点的有向边的数目，记为ID(v)；顶点v的出度：以顶点v为起始点的有向边的数目，记为OD(v)；有向图中顶点v的度那么定义为该顶点的入度和出度之和，即D(v)＝ID(v)十OD(v)。11精选课件7.1图的定义和术语例：在下面的有向图中ID(A)=1；OD(A)=2;D(A)=3ID(C)=1；OD(C)=1;D(C)=3ABECF结论有向图中：顶点入度之和=顶点出度之和=弧数12精选课件7.1图的定义和术语在无向图G中，假设存在一个顶点序列〔vp,vi1,…，vin，vq〕，使得(vp，vil)，(vi1,vi2)，…，(vin，vq)均属于边集E(G)，那么称顶点vp到vq存在一条路径。假设G是有向图，那么路径也是有向的，它由E(G)中的有向边＜vp，vil＞,＜vil，vi2＞,…，＜vin，vq＞组成。路径长度：该路径上边的数目。序列中顶点不重复出现的路径称为简单路径。起点和终点相同(vp＝vq)的路径称为回路。假设一条路径上除了vp和vq可以相同外，其余顶点均不相同，那么称此路径为简单回路或简单环。13精选课件7.1图的定义和术语例如：在有向图G中：〔A,B,C,F〕是图G的一条路径，它是由有向边序列<A,B>,<B,C>,<C,F>组成，它是一条简单路径，路径的长度是3。〔A,B,C,F,B,E〕也是图G的一条路径，它是由有向边序列〈A,B>,<B,C>,<C,F>,<F,B>,<B,E>组成，它不是简单路径，这条路径的长度是5。<A,B>,<B,C>,<C,F>,<F,A>也是图G的一条路径，这条路径的长度是4，它是一条简单回路。ABECF14精选课件7.1图的定义和术语在无向图G中，假设从顶点vi到顶点vj有路径，那么称vi和vj是连通的。假设图G中任意两个不同的顶点vi和vj都连通，那么称G为连通图。无向图G的一个极大连通子图称为G的一个连通分量。显然，任何连通图的连通分量只有一个，就是它自身，而非连通的无向图有多个连通分量。15精选课件7.1图的定义和术语例如：以下图所示为两个无向图G1和G2，其中:G1是一个连通图G2是由4个连通分量组成的非连通图。BCAFED无向图G1BEADCGHIFJ无向图G216精选课件7.1图的定义和术语在有向图G中，假设对于其中的任意两个不同的顶点vi和vj，从vi到vj和从vj到vi都存在路径，那么称G是强连通图。有向图G的极大强连通子图称为G的强连通分量。显然，强连通图只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分量。17精选课件7.1图的定义和术语例如：以下图所示为两个有向图G1和G2，其中:G1是一个强连通图，G2是由3个强连通分量组成的非连通图。ABECF有向图G1ABECF有向图G218精选课件7.1图的定义和术语结论有n个顶点的有向图最多有条边，最少有条边。有n个顶点的无向图最多有条边，最少有条边。有n个顶点的连通图最少有条边，假设少于条边，图一定是非连通图，多于条边，连通图中一定有环路存在。n(n-1)n(n-1)/200n-1n-1n-119精选课件7.1图的定义和术语生成树：一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只含有足以构成一棵树的n-1条边。如下图：连通图G的一棵生成树注意:

一棵有n个顶点的生成树一定有n-1条边。但有n个顶点和n-1条边的图，一定是一棵生成树吗？ABECFABECF1棵生成树20精选课件7.2图的存储结构由于图的结构比较复杂，除了要把图的各顶点存入计算机，还应该把各顶点之间的关系也输入计算机，而图中任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序映象的存储结构，但可以借助数组的数据类型表示图中顶点之间的关系，即图的领接矩阵的存储结构。另一方面，也可以用链表表示图，如领接表、领接多重表和十字链表是图常用的三种链式存储结构。21精选课件7.2图的存储结构对于具体问题中的图来说,要为其选择最好的存储结构，不仅仅要依赖于图的性质如有向图还是无向图,以及图中的数据,例如:顶点数,边数等,而且还与在图上所实施的操作有关，例如对图中的顶点进行插入或删除操作的频率等.下面将主要介绍图的领接矩阵和领接表这两种存储方式。22精选课件7.2.1邻接矩阵邻接矩阵(数组表示法〕是用二维数组表示顶点之间相邻关系的存储结构。设G＝(V，E)是具有n个顶点的无权图，那么G的邻接矩阵是具有如下性质的n阶方阵：A[i,j]={若(vi,vj)或<vi,vj>是E(G)中的边

0

反之23精选课件7.2.1邻接矩阵例1：给定4个顶点的有向图24精选课件7.2.1邻接矩阵例2：给定6个顶点的无向图①⑥⑤

④

③

②A注:无向图的邻接矩阵是对称的，即

A[i][j]=A[j][i]

25精选课件7.2.1邻接矩阵假设G＝(V，E)是具有n个顶点的带权图〔网〕那么G的邻接矩阵是具有如下性质的n阶方阵：A[i,j]={Wij若(vi,vj)或<vi,vj>是E(G)中的边，Wij为边上的权值∞

反之26精选课件7.2.1邻接矩阵例１：给定6个顶点的无向网〔无向带权图〕①⑥⑤

④

③

②5781014124A=∞5

∞∞8∞

∞∞∞107∞∞

∞4∞14∞∞4

∞∞12810∞∞∞∞∞71412∞∞无向网G1及其领接矩阵存储结构27精选课件7.2.1邻接矩阵例2：给定6个顶点的有向网〔有向带权图〕

v0v1v2v3v4v5v0∞∞10∞30100v1∞∞∞∞∞∞v2∞5∞50∞∞v3∞∞∞∞∞10v4∞∞∞20∞60v5∞∞∞∞∞∞v0v5v1v2v4v33010205051010060图G2的领接矩阵存储结构有向带权图G228精选课件7.2.1邻接矩阵结论在无向图的领接矩阵中,顶点vi的度等于邻接矩阵中第i行(或第i列)上非零元素的个数；在有向图的领接矩阵中，顶点vi的出度等于邻接矩阵中的第i行上非零元素的个数;在有向图的领接矩阵中，顶点vi的入度等于邻接矩阵中的第i列上非零元素的个数.29精选课件7.2.1邻接矩阵图的领接矩阵存储表示用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储图的顶点信息。其形式说明如下：#definen6 /*图的顶点数*/#definee8 /*图的边〔弧〕数*/typedefstruct{charvexs[n+1]；/*设顶点的数据类型为char型*/intarcs[n+1][n+1]；/*设权值类型为int*/}Graph；GraphG;30精选课件7.2.1邻接矩阵创立无向网的算法#defineMAX10000CreatGraph(Graph*G)/*建立无向网络*/{inti，j，k；intw；for(i＝1；i＜=n；i++)G->vexs[i]＝getchar()；/*读入n个顶点信息*/for(i＝1；i＜=n；i++)for(j＝1；j＜=n；j++)G->arcs[i][j]＝MAX；/*邻接矩阵初始化*/for(k＝1；k＜=e；k++)/*读入e条边*/{scanf(〞％d％d％d〞，&i,&j,&w)；G->arcs[i][j]＝w；G->arcs[j][i]＝w；}}31精选课件7.2.1邻接矩阵分析该算法的时间复杂度算法的执行时间是O(n+n2+e)，其中O(n2)的时间消耗在邻接矩阵的初始化操作上。因为e＜n2，所以，算法的时间复杂度是O(n2)。32精选课件7.2.2

邻接表领接表是图的一种链式存储结构。类似于树的孩子链表表示法。在领接表存储结构中，对于图G中的每个顶点vi，把vi的所有邻接点链成一个单链表，这个单链表就称为顶点vi的邻接点单链表。那么，假设图有n个顶点，就有n个领接点单链表。为了便于随机访问任一顶点的邻接点单链表，通常将所有邻接点单链表的头结点顺序存储在一个结构体数组中。33精选课件7.2.2

邻接表n个领接点单链表的表头结点结构均为：含有两个域，一个是顶点域，用来存放顶点vi的信息；另一个是指针域，用来指向vi的领接点单链表中的第一个结点。在顶点vi的邻接点单链表中，每个结点均有两个域，一个是邻接点域，用以存放与vi的领接点vj的信息；另一个是指针域，用来指向与vi相邻的下一个领接点。34精选课件7.2.2

邻接表v0v5v1v2v4v32361534^^^V0V1V2V3V4V55^^^例1：图的领接表存储结构

注意：图的邻接矩阵表示是唯一的，但其邻接表不唯一35精选课件7.2.2

邻接表例2：图的领接表存储结构

V5V3V2V6V1V425516664322431^^^^^^V1V2V3V4V5V636精选课件7.2.2

邻接表创立领接表的算法思想建立无向图的邻接表时，每读入一个顶点对〔i,j〕时，就创立一个邻接点序号为j的新结点，将其插入到vi为表头结点的领接点单链表中；同时生成一个邻接点序号为i的新结点，将其插入到vj为表头结点的单链表中。建立有向图的邻接表与此类似，只是更加简单，每读入一个顶点对序号＜i，j＞时，仅需生成一个邻接点序号为j的新结点，将其插入到vi为表头结点的领接点单链表中即可。假设建立网络的邻接表，那么需在链表的每个结点中增加一个存储边上的权值的数据域。37精选课件7.2.2

邻接表领接表存储结构的结论在无向图的领接表中顶点vi的度等于vi的邻接点链表中的结点个数在有向图的领接表中顶点vi的出度等于vi的邻接点链表中的结点个数；顶点vi的入度等于vi在所有领接点链表中出现的次数；38精选课件7.2.2

邻接表对于有向图G中的每个顶点vj，把所有邻接到vj的顶点vi链成一个单链表，这个单链表就称为顶点vj的逆邻接表。如下例2162643^^^^^^123456①⑥⑤

④

③

②39精选课件7.3

图的遍历和树的遍历类似，图的遍历也是从某个顶点出发,沿着某条搜索路径访问图中所有顶点，且每个顶点仅被访问一次。假设给定的图是连通图，那么从图中任一顶点出发均可以访问到该图的所有顶点。由于图中的任一顶点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条回路又回到了该顶点。因此，在遍历图的过程中，为了防止重复访问同一个顶点，必须记住每个顶点是否被访问过。为此，可设置一个辅助数组visited[n]，它的初值为全为0，一旦访问了顶点vi，便将visited[i]置为1。通常图的遍历有两种路径：深度优先搜索和广度优先搜索。40精选课件7.3.1图的深度优先搜索深度优先搜索类似于树的先序遍历。假设给定图G的初态是所有顶点均未访问过，在G中任选一顶点vi作为初始出发点，那么深度优先搜索可定义为：首先，访问出发点vi，并将其标记为已访问过，然后，依次从vi的未曾访问过的邻接点出发继续进行深度优先搜索,直到图中所有与vi有路径相通的顶点都被访问到；假设此时图中还有顶点未被访问〔即当图为非连通图时〕，那么另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。41精选课件7.3.1图的深度优先搜索例1:图的深度优先搜索12345678图7.13(a)深度优先搜索结果:v1-v2-v4-v8-v5-v3-v6-v742精选课件7.3.1图的深度优先搜索深度优先搜索算法如下：voidDFSTraverse(GraphG,intv){for(v=0;v<G.vexnum;v++)visited[v]=0;for(v=0;v<G.vexnum;v++)if(!visited[v])DFS(G,v);}voidDFS(GraphG,intv〕{visited[v]=1;printf(“％d〞，v);w=FirstAdjVex(G,v);//找v的第一个领接点while(w!＝NULL){if(!visited[w])DFS(G,w);//假设该顶点w未被访问过，那么从它出发进行深度优先搜索，否那么，找v的下一个邻接点w=w－>next;}}43精选课件7.3.2图的广度优先搜索广度优先搜索类似于树的按层次遍历。设图G的初态是所有顶点均未访问过，在G中任选一顶点Vi为初始出发点，那么广度优先搜索的根本思想是：首先访问出发点Vi，接着依次访问vi的所有邻接点wl，w2，…，wt，然后，再依次访问与wl，w2，…，wt邻接的所有未曾访问过的顶点，依此类推，直至图中所有和出发点v有路径相通的顶点都已访问到为止;假设此时图中尚有顶点未被访问〔即当图为非连通图时〕，那么另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。44精选课件7.3.2图的广度优先搜索例1:图的广度优先搜索12345678图7.13(a)广度优先搜索结果：v1-v2-v3-v4-v5-v6-v7-v845精选课件7.3.2图的广度优先搜索广度优先搜索算法如下：voidBFS(GraphG,intv〕{InitQueue(Q);visited[v]=1;printf(“％d〞，v);EnQueue(Q,v);while(!QueueEmpty(Q)){DelQueue(Q,u);for(w=FirstAdjVex(G,u);w;w=w－>next)if(!visited[w]){visited[w]=1;printf(“％d〞，w);EnQueue(Q,w);}}}46精选课件7.3.2图的广度优先搜索voidBFSTraverse(GraphG,intv){for(v=0;v<G.vexnum;v++)visited[v]=false;for(v=0;v<G.vexnum;v++)if(!visited[v])BFS(G,v);}47精选课件7.4图的连通性问题7.4.1无向图的连通分量和生成树在无向图的遍历算法中，假设从某个顶点出发访问下一个顶点时增加这两个顶点之间的边，那么可得到连通图的一棵生成树或不连通的图的生成森林。由深度优先遍历得到的生成树称为深度优先生成树。由广度优先遍历得到的生成树称为广度优先生成树。48精选课件7.4.2

最小生成树图的生成树不是唯一的，从不同的顶点出发进行遍历，可以得到不同的生成树。对于连通网G＝(V，E)而言，图中的边是带权的，因而G的生成树的各条边也是带权的。我们把生成树各条边的权值总和称为生成树的权〔或称代价〕，并把权最小的生成树称为G的最小生成树。生成树和最小生成树有许多重要的应用。例如：令图G的顶点表示城市，边表示连接两个城市之间的通讯线路。n个城市之间最多可设立n(n-1)／2条线路，把n个城市连接起来至少要n-1条线路,那么图G的生成树表示了建立通讯网络的可行方案。49精选课件7.4.2

最小生成树如果给图中的边都赋予权，而这些权可表示两个城市之间通讯线路的长度或建造代价，那么，如何选择n-1条线路，使得建立的通讯网络其线路的总长度最短或总代价最小呢?这就转换为如何构造该图的一棵最小生成树的问题。以下我们只讨论无向图的最小生成树问题。50精选课件7.4.2

最小生成树V1V2V4V3V5V6613555664251精选课件7.4.2

最小生成树构造最小生成树可以有多种算法，其中大多数构造算法都是利用了最小生成树的下述性质：设G＝(V,E)是一个连通带权图，U是顶点集V的一个真子集。假设边(u,v)〔u∈U，v∈V-U〕是图G的所有边中权值最小的一条边，那么一定存在图G的一棵最小生成树包含此边(u,v)。这个性质称为MST性质。可用反证法证明(略)下面将重点介绍两个利用MST性质构造最小生成树的算法：普里姆〔Prim〕算法和克鲁斯卡尔〔Kruskal〕算法。52精选课件7.4.2

最小生成树Prim算法的根本思想是：假设G=(V，E〕是连通网，设T=(U，TE)是最小生成树初始情况下设U＝{u0}(u0∈V〕,TE＝{}.重复执行下述操作：在所有的u∈U，v∈V－U的边(u，v)∈E中，找一条权值最小的边〔u0,v0)，将其并入集合TE，同时将v0并入集合U，直至U＝V为止，此时TE中必有n－1条边，那么T=(U,TE)即为G的一棵最小生成树。53精选课件7.4.2

最小生成树Prim算法求最小生成树：1.〔1,2〕被选中U={1,2}2.〔2,5〕被选中U={1,2,5}3.〔2,3〕被选中U={1,2,3,5}4.〔1,4〕被选中U={1,2,3,4,5}6.〔5,7〕被选中U={1,2,3,4,5,6,7}7.〔7,8〕被选中U={1,2,3,4,5,6,7,8}5.〔3,6〕被选中U={1,2,3,4,5,6}U={1},TE={}

①1②2③31453

④4⑤9⑥10589

⑦6⑧①1②2③3④1⑤4⑥5⑦6⑧54精选课件7.4.2

最小生成树Kruskal算法的根本思想：假设G=(V，E〕是连通网，设T=(U，TE)是要求的最小生成树。初始情况下设U＝V,TE＝{}.并将连通网中的所有边按权值的非递减次序进行排列，然后执行：依次将连通网中有序排列的各条边〔u,v〕作如下处理：假设将〔u,v〕参加TE中后，TE中的边构成了一条回路，那么不将〔u,v〕参加TE中；否那么将〔u,v〕参加TE中。重复上述过程，直至TE中已有n-1条边为止。此时T=(U,TE)即为G的一棵最小生成树。55精选课件7.4.2

最小生成树Kruskal算法求最小生成树过程：1.〔1，2〕被选中2.〔2，5〕被选中3.〔2，3〕被选中4.〔1，4〕被选中6.〔5，6〕不被选中8.〔5，7〕被选中7.〔7，8〕被选中5.〔3，6〕被选中①②③

④⑤⑥

⑦5⑧1312464

①1②2③31455

④8⑤4⑥96109

⑦5⑧56精选课件7.4.2

最小生成树练习题：分别用Prim算法和Kruskal算法求如下无向图的最小生成树。V1V2V4V3V5V66135556642V2V4V5V6V1V313542V1V2V4V3V5V613542无向带权图G用Prim算法求其最小生成树用Kruskal算法求其最小生成树57精选课件7.5有向无环图及其应用有向无环图:是一个无环的有向图.简称DAG图.有向无环图的作用:常用来描述一个过程〔如一个系统进行的过程，一个工程进行的过程〕.通常我们把方案、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，通常我们把这些子工程称为活动，当这些活动完成时，整个工程也就完成了。58精选课件7.5.1AOV网而在各个活动之间,有些必须按规定的先后次序进行，有些那么没有先后次序要求.那么，工程中的这种各个活动之间的次序要求,可以用一个有向图来表示：图中每个顶点代表一个活动.如果从顶点vi到顶点vj之间存在有向边<vi,vj>，那么表示活动vi必须先于活动vj进行.这种用顶点表示活动,用有向边〔弧〕表示顶点间优先关系的有向图称为AOV网.比方教学方案的制定.

59精选课件7.5.1AOV网C7C1C2C4C9C12C11C10C6C8C5C3表示必修课程优先关系的有向图〔AOV网〕必修课程关系表课程编号课程名称先决条件

C1

程序设计基础无

C2离散数学C1C3数据结构C1

，C2C4汇编语言C1C5语言的设计与分析C3，C4C6计算机原理C11C7编译原理C3，C5C8操作系统C3，C6C9高等数学无

C10线性代数C9C11普通物理C9C12数值分析C9，C10，C160精选课件7.5.1AOV网AOV网的特点:在AOV网中一定不能有回路。在AOV-网中如果出现了有向环，那么意味着某项活动应以自己的完成作为先决条件，这是不合理的，工程将无法进行。因此，对给定的有向图，判断它是否是一个AOV-网，应先判断有向图中是否存在环路。检测有向图中是否存在有向环,可用拓扑排序的方法即对AOV-网构造其顶点的拓扑有序序列，假设网中所有顶点都在它的拓扑有序序列中，那么AOV-网中必定无环，否那么，AOV-网中一定存在环路。61精选课件7.5.1AOV网拓扑排序：1.在有向图中选一个没有前驱的顶点〔即入度为0的顶点〕且输出之。2.从图中删除该顶点和所有从它发出的边。重复上述两步，直到全部顶点均已输出或当前图中不存在无前驱的顶点为止。假设所有顶点均已输出，那么说明有向图中无有向环，得到的顶点输出序列即为拓扑序列；否那么说明未输出的顶点构成了有向环。62精选课件7.5.1AOV网C7C1C2C4C9C12C11C10C6C8C5C3举例：拓扑序列为：C1C4C2C3C5C7C9C11C6C10C12C863精选课件7.5.2关键路径与AOV网相对应的是AOE网(ActivityOnEdgenetwork)，AOE网即边表示活动的网络。AOE网是一个有向带权图，图中的：

边：表示活动(子工程)，

边上的权：表示该活动的持续时间，即完成该活动所需要的时间； 顶点：表示事件，每个事件是活动与活动之间的转接点，即表示在它之前的所有活动已经完成，在它之后的活动可以开始。AOE网的作用：它通常用来表示一个工程的方案或进度，可用来估算工程的完成时间。64精选课件7.5.2关键路径V1V2V3V4V5V6V7V8V9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4有9个事件、11个活动的AOE-网举例：工程的开始点〔源点〕工程的完成点〔终点〕65精选课件7.5.2关键路径关键路径：路径长度最长的路径。关键活动：关键路径上的活动。求工程的最短工期：在AOE网上求一条关键路径的长度。

问题：

1.完成此工程最短需要多长时间？

2.影响此工程进度的活动是哪些？

3.如何加快工程进度、缩短工程完成时间？——源点到终点的最长路径的长度——最长路径上的所有活动——缩短最长路径长度66精选课件7.5.2关键路径设源点是v1,定义：事件vi的最早发生时间ve(i)：事件vi最早可以发生的时间，即从v1到vi的最长路径长度。事件vi的最迟发生时间vl(i)

：在不影响整个工程进度的前提下事件vi最迟必须发生的时间。活动ak=<vi,vj>的最早开始时间ee(k)

：等于事件vi的最早发生时间ve(i)。活动ak=<vi,vj>的最迟开始时间el(k)

：在不影响整个工程进度的前提下，活动ak最迟必须开始的时间，等于事件vj的最迟发生时间vl(j)减去活动ak的持续时间dut(<i,j>)。关键活动ak=<vi,vj>

即为ee(k)=el(k)的活动。67精选课件7.5.2关键路径ve(1)=0ve(j)=max{ve(i)+dut(<i,j>)}j=2,3,…,n按拓扑有序求ve(j){vl(n)=ve(n)vl(i)=min{vl(j)-dut(<i,j>)}j=n-1,n-2,…,1按拓扑有序求vl(i){ee(k)=ve(i)el(k)=vl(j)-dut(<i,j>)其中活动ak=<vi，vj>{<i,j>∈E<i,j>∈E68精选课件7.5.2关键路径顶点Ive(i)vl(i)V1

v2

v3

v4

v5

v6v7v8

v9

0645771614180668710161418活动kdut(k)ee(k)el(k)el(k)-ee(k)

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

645112974240006457771614023668771016140230230030069精选课件7.5.2关键路径V1V2V3V4V5V6V7V8V9a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=42条关键路径V1V2V5V7V8V9a1=6a4=1a7=9a8=7a10=2a11=4关键路径长度均为18，关键活动为：a1a4a7a8a10a1170精选课件7.5.2关键路径由此可见，用AOE网来估算某些工程完成的时间是非常有用的。要想加快整个工程的完成速度，缩短整个工期，只有提高关键活动的速度才有效。另外，假设网中有几条关键路径，那么只提高一条关键路径上的关键活动的速度还不能导致整个工程缩短工期，而必须提高同时在几条关键路径上的活动的速度。注意：关键活动的速度提高是有限度的。71精选课件7.5.2关键路径练习题：求以下图所示的AOE网的所有关键路径。有10个事件、14个活动的AOE-网V1V2V3V4V5V7V8V9V10a1=3a2=5a3=1a4=2a5=3a7=7a8=4a11=8a12=8a13=5V6a14=2a9=7a10=9a6=172精选课件7.6最短路径在复杂的交通网络中，人们常常会提出这样的问题：从A地到B地之间是否有道路相通?在有多条通路的情况下，哪一条道路长度最短〔最省时、最省钱〕等?解决这类问题也就是在带权图中求最短路径的问题。交通网络可用带权图来表示。图中的顶点表示城市，边表示两个城市之间有路相通，边上的权值可表示两个城市之间的距离〔或交通费用或途中所花费的时间等〕。那么，求两个顶点之间的最短路径，是指在连接两个顶点的所有路径中，选择一条路径上各边权值之和最小的路径。最短路径的问题常见两种:从某源点到其余各顶点之间的最短路径(要求)

每一对顶点之间的最短路径(不要求)73精选课件7.6.1单源点最短路径——求从某个源点到其余各个顶点的最短路径例1：如有向带权图G源点终点最短路径长度v0v1∞v0v2〔v0v2)10v0v3〔v0v4v3〕50v0v4〔v0v4〕30v0v5〔v0v4v3v5〕60v0v5v1v2v4v33010205051010060有向带权图G74精选课件7.6.1单源点最短路径 v0v1v2v3v4v5012345v00 ∞∞10∞30100v11 ∞∞∞∞∞∞v22 ∞5∞50∞∞v33 ∞∞∞∞∞10v44 ∞∞∞20∞60v55 ∞∞∞∞∞∞图G的领接矩阵存储结构A[6][6]有向带权图G图G以及它的领接矩阵的存储结构如下所示：v0v5v1v2v4v3301020505101006075精选课件7.6.1单源点最短路径迪杰斯特拉〔Dijkstra〕算法算法的核心思想：按最短路径长度递增的次序依次求出各条最短路径。为了描述算法步骤，需要引入几个辅助向量：D[i]：表示当前所找到的从源点V0出发到终点Vi的最短路径的长度；初始状态D[i]=A[0][i]S：为已经求出了最短路径的顶点组成的集合；初始状态为S={V0}；P[i]：记录当前所找到的从源点出发只经过S中的顶点到达Vi的最短路径中Vi的前驱顶点；那么当S中包含了图中所有顶点时，D[i]即为最终找到的从源点出发到达Vi的最短路径长度，P[i]即为最终找到的从源点出发到达Vi的最短路径中Vi的前驱顶点。76精选课件7.6.1单源点最短路径分析：显然，长度最短的一条最短路径就是长度为：D[j]=min{D[i]|Vi∈V}的路径。此路径是：〔V0，Vj〕那么下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是Vk，那么可想而知，这条路径或者是〔V0，Vk〕或者是〔V0，Vj，Vk〕。即它的长度或者是从V0到Vk的弧上的权值，或者是D[j]加上从Vj到Vk的弧上的权值之和。那么，长度倒数第三短的最短路径是？依次下去，一般情况下下一条最短路径是？77精选课件7.6.1单源点最短路径S集合是已经求得了最短路径的终点的集合，那么一般情况下，可以证明：下一条长度次短的最短路径〔设其终点是Vx)或者是〔V0，Vx〕，或者是中间只经过S中的顶点而最后到达顶点Vx的路径。反证法证明：假设下一条要找的长度次短的最短路径上有一个顶点不在S中，那么说明存在一条终点不在S中，而路径长度比此路径长度更短的路径。但这是不可能的。因为我们是按最短路径长度递增的次序来产生各条最短路径的，故长度比此路径更短的所有最短路径都已经产生，它们的终点必定在S中，即假设不成立！78精选课件7.6.1单源点最短路径因此，一般情况下：下一条长度次短的最短路径〔设其终点是Vx)，或者是〔V0，Vx〕，或者是中间只经过S中的顶点而最后到达顶点Vx的路径。那么下一条长度次短的最短路径的长度或者是弧(V0，Vx)上的权值A[0][x];或者是D[k](Vk∈S)加上弧(Vk,Vx)的权值:D[k]＋A[k][x](Vk∈S,Vx∈V-S)。即下一条长度次短的最短路径的长度一定是D[j]=min{D[i]|Vi∈V－S}，其中，{A[0][i]D[k]＋A[k][i]〔Vk∈S,Vi∈V-S〕D[i]=

79精选课件7.6.1单源点最短路径求解过程(重点〕:源点终点D[i]从V0到各终点的最短路径D[i]的值和最短路径i=1i=2i=3i=4i=5V0V1D[1]V2D[2]V3D[3]V4D[4]V5D[5]S{v0}10(v0,v2)∞∞30(v0,v4)100(v0,v5)∞∞∞∞60(v0,v2,v3)50(v0,v4,v3)30(v0,v4)100(v0,v5)90(v0,v4,v5)60(v0,v4,v3,v5){v0,v2}{v0,v2,v4}{v0,v2,v3,v4}{v0,v2,v3,v4,v5}S＝V

80精选课件7.6.1单源点最短路径

初始状态：

S={V0}D[i]=A[0][i]

P[i]=i=1,2,…,n{0A[0][i]<∞时-1A[0][i]=∞时

取min{D[i]}=D[j]

S=S+{Vj}

P[i]=

D[i]=min{D[i],D[j]+A[j][i]}i∈V-S{jD[i]>D[j]+A[j][i]时P[i]D[i]≤D[j]+A[j][i]时i∈V-S重复以下过程n-1次：81精选课件7.6.1单源点最短路径Dijkstra算