数据结构课件：07.图.ppt

1、第七章第七章一、图的定义一、图的定义( (Graph)Graph)2第一节图的定义与术语第一节图的定义与术语n图是由顶点集合图是由顶点集合( (vertex)vertex)及顶点间的关系集合及顶点间的关系集合组成的一种数据结构：组成的一种数据结构： GraphGraph( V, E ) ( V, E ) 其中其中V = x | xV = x | x 数据对象数据对象 是顶点的有穷非空集合是顶点的有穷非空集合 E E是顶点之间关系的有穷集合，包括是顶点之间关系的有穷集合，包括 E1 = (x, y) | x, y E1 = (x, y) | x, y V V 边的集合边的集合 或或 E2 = |

2、 x, y E2 = | x, y V V 弧的集合弧的集合第章图第章图二、无向图二、无向图( (Undigraph)Undigraph)3第一节图的定义与术语第一节图的定义与术语n用用( (x,y)x,y)表示两个顶点表示两个顶点x,yx,y之间的一条边之间的一条边( (edge)edge)nN=V,EN=V,E，V=0,1,2,3,4,5V=0,1,2,3,4,5，E=(0,1), E=(0,1), (0,4), (0,5), (1,2), (1,3), (1,5), (2,3), (0,4), (0,5), (1,2), (1,3), (1,5), (2,3), (3,4), (3,5)

3、, (4,5)(3,4), (3,5), (4,5)第章图第章图132540二、无向图二、无向图( (完全图完全图) )4第一节图的定义与术语第一节图的定义与术语n如果无向图有如果无向图有n(n-1)/2n(n-1)/2条边，则称为无向完全条边，则称为无向完全图图第章图第章图132540二、无向图二、无向图5第一节图的定义与术语第一节图的定义与术语n邻接点：如果邻接点：如果( (x,y)x,y) E,E,称称x,yx,y互为邻接点，即互为邻接点，即x,yx,y相邻接相邻接n依附：边依附：边( (x,y)x,y)依附于顶点依附于顶点x,yx,yn相关联：边相关联：边( (x,y)x,y)与与x,

4、yx,y相关联相关联n顶点的度：和顶点相关联的顶点的度：和顶点相关联的 边的数目，记为边的数目，记为TD(x)TD(x)第章图第章图132540三、有向图三、有向图( (Digraph)Digraph)6第一节图的定义与术语第一节图的定义与术语n用用 x,y表示从表示从x x到到y y的一条弧的一条弧( (Arc)Arc)，且称且称x x为为弧尾，弧尾，y y为弧头，为弧头，nN=V,EN=V,E，V=0,1,2,3,4V=0,1,2,3,4，E=E=， 第章图第章图13240三、有向图三、有向图( (完全图完全图) )7第一节图的定义与术语第一节图的定义与术语n如果有向图有如果有向图有n(n

5、-1)n(n-1)条边，则称为有向完全图条边，则称为有向完全图第章图第章图120三、有向图三、有向图8第一节图的定义与术语第一节图的定义与术语n邻接：如果邻接：如果 x,y E,E,称称x x邻接到邻接到y,y,或或y y邻接自邻接自x xn相关联：弧相关联：弧 x,y与与x,yx,y相关联相关联n入度：以顶点为头的弧的入度：以顶点为头的弧的 数目，记为数目，记为ID(x)ID(x)n出度：以顶点为尾的弧的出度：以顶点为尾的弧的 数目，记为数目，记为OD(x)OD(x)n度：度：TD(x)=ID(x)+OD(x)TD(x)=ID(x)+OD(x)第章图第章图13240四、路径四、路径( (Pa

6、th)Path)9第一节图的定义与术语第一节图的定义与术语n路径：是一个从顶点路径：是一个从顶点x x到到y y的顶点序列的顶点序列( (x, vx, vi1i1, , v vi2i2, , v, vinin, y), y)n其中，其中，( (x,vx,vi1i1),(v),(vij-1ij-1,v,vijij),(v),(vinin,y),y)皆属于皆属于E E第章图第章图132401325401到3有路径(1,0,4,3)1到4有路径(1,2,4)五、回路五、回路10第一节图的定义与术语第一节图的定义与术语n回路或环：路径的开始顶点与最后一个顶点相回路或环：路径的开始顶点与最后一个顶点相同

7、，即路径中同，即路径中( (x, vx, vi1i1, v, vi2i2, , v, vinin, y), y)，x=yx=yn简单路径：路径的顶点序列中，顶点不重复出简单路径：路径的顶点序列中，顶点不重复出现现第章图第章图1325401到1构成环(1,0,4,3,1)1到3是简单路径(1,0,4,3)六、连通六、连通11第一节图的定义与术语第一节图的定义与术语n连通：如果顶点连通：如果顶点x x到到y y有路径，称有路径，称x x和和y y是连通的是连通的n连通图：图中所有顶点都连通连通图：图中所有顶点都连通第章图第章图13240132540连通图非连通图七、子图七、子图12第一节图的定义与

8、术语第一节图的定义与术语n设有两个图设有两个图 G G(V, E) (V, E) 和和 G G(V(V, E, E) )。若若 V V V V 且且 E E E, E, 称图称图G G是图是图G G的子图的子图第章图第章图1325403240八、生成树八、生成树13第一节图的定义与术语第一节图的定义与术语n一个连通图的生成树是一个极小连通子图，它一个连通图的生成树是一个极小连通子图，它含有图中全部含有图中全部n n个顶点，但只有足以构成一棵个顶点，但只有足以构成一棵树的树的n-1n-1条边条边第章图第章图132540132540一、邻接矩阵一、邻接矩阵( (Adjacency Matrix)A

9、djacency Matrix)14第二节图的存储结构第二节图的存储结构n邻接矩阵：记录图中各顶点之间关系的二维数邻接矩阵：记录图中各顶点之间关系的二维数组。组。n对于不带权的图，以对于不带权的图，以1 1表示两顶点存在边表示两顶点存在边( (或或弧弧)()(相邻接相邻接) )，以，以0 0表示两顶点不邻接，即表示两顶点不邻接，即 1 1 如果如果( (i,j)i,j) E E 或或 i,j E EAij = Aij = 0 0 其它其它第章图第章图一、邻接矩阵一、邻接矩阵15第二节图的存储结构第二节图的存储结构n无向图的邻接矩阵为：有向图的邻接矩阵为：无向图的邻接矩阵为：有向图的邻接矩阵为：

10、 第章图第章图132540132400 1 0 0 1 1 1 0 1 1 0 10 1 0 1 0 00 1 1 0 1 11 0 0 1 0 11 1 0 1 1 00 1 0 1 10 0 1 0 00 0 0 0 10 0 1 0 00 0 0 0 0一、邻接矩阵一、邻接矩阵( (性质性质) )16第二节图的存储结构第二节图的存储结构n无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的n其第其第i i行行1 1的个数或第的个数或第i i列列1 1的个数，等于顶点的个数，等于顶点i i的度的度TD(i)TD(i)n有向图的邻接矩阵可能是不对称的有向图的邻接矩阵可能是不对称的n其第其第i i

11、行行1 1的个数等于顶点的个数等于顶点i i的出度的出度OD(i)OD(i)，第第j j列列1 1的个数等于顶点的个数等于顶点j j的入度的入度ID(j)ID(j)第章图第章图一、邻接矩阵一、邻接矩阵( (网络网络) )17第二节图的存储结构第二节图的存储结构n在网络中，两个顶点如果不邻接，则被视为距在网络中，两个顶点如果不邻接，则被视为距离为无穷大；如果邻接，则两个顶点之间存在离为无穷大；如果邻接，则两个顶点之间存在一个距离值一个距离值( (即权值即权值) ) w wi,ji,j 如果如果( (i,j)i,j) E E 或或 i,j E E Aij = Aij = 其它其它第章图第章图一、邻

12、接矩阵一、邻接矩阵( (网络网络) )18第二节图的存储结构第二节图的存储结构n有向网有向网N=V,EN=V,E，V=0,1,2,3,4V=0,1,2,3,4，E=E=， ，E E中每个元组的第三个元素表示权。中每个元组的第三个元素表示权。1 1、画出该网、画出该网, 2, 2、写出该网的邻接矩阵。、写出该网的邻接矩阵。第章图第章图132405515172 5 7 15 5 1 2 二、邻接表二、邻接表( (Adjacency ListAdjacency List) )19第二节图的存储结构第二节图的存储结构n邻接表是图的一种链式存储结构邻接表是图的一种链式存储结构n在邻接表中，每个顶点设置一

13、个单链表，其每在邻接表中，每个顶点设置一个单链表，其每个结点都是依附于该顶点的边（或以该顶点为个结点都是依附于该顶点的边（或以该顶点为尾的弧）尾的弧）第章图第章图二、邻接表二、邻接表( (结点结构结点结构) )20第二节图的存储结构第二节图的存储结构n边边( (弧弧) )的结点结构的结点结构 adjvex; / adjvex; / 该边该边( (弧弧) )所指向的顶点的位置所指向的顶点的位置 nextarc;/ nextarc;/ 指向下一条边指向下一条边( (弧弧) )指针指针 info; / info; / 该边该边( (弧弧) )相关信息的指针或权值相关信息的指针或权值n顶点的结点结构顶

14、点的结点结构 data; / data; / 顶点信息顶点信息 firstarc;/ firstarc;/指向第一条依附该顶点的边指向第一条依附该顶点的边( (弧弧) )第章图第章图adjvexinfonextarcdatafirstarc二、邻接表二、邻接表( (无向图无向图) )21第二节图的存储结构第二节图的存储结构第章图第章图132540012345145 02313 1245 035 0134 5 二、邻接表二、邻接表( (有向图有向图) )22第二节图的存储结构第二节图的存储结构第章图第章图0123413240134242二、邻接表二、邻接表( (网络网络) )23第二节图的存储结

15、构第二节图的存储结构第章图第章图0123413240551517215374 15 25 41 22 二、邻接表二、邻接表( (性质性质) )24第二节图的存储结构第二节图的存储结构n对于有向图的邻接表，其第对于有向图的邻接表，其第i i个链表中结点的个链表中结点的个数只是该顶点的出度；如果要计算入度，必个数只是该顶点的出度；如果要计算入度，必须遍历整个邻接表须遍历整个邻接表 也可以建立一个也可以建立一个逆邻接表逆邻接表 n要判定两个顶点要判定两个顶点i i和和j j是否有边（或弧），必须是否有边（或弧），必须搜索整个第搜索整个第i i个和第个和第j j个链表，不及邻接矩阵方个链表，不及邻接矩

16、阵方便便第章图第章图二、邻接表二、邻接表( (有向图的有向图的逆邻接表逆邻接表) )25第二节图的存储结构第二节图的存储结构n逆邻接表中，弧的箭头向内逆邻接表中，弧的箭头向内( (入弧入弧) )第章图第章图0123413240302010三、十字链表三、十字链表( (Orthogonal ListOrthogonal List) )26第二节图的存储结构第二节图的存储结构n十字链表是十字链表是有向图的另一种存储结构有向图的另一种存储结构n十字链表是将有向图的邻接表和逆邻接表结合十字链表是将有向图的邻接表和逆邻接表结合起来的一种存储结构起来的一种存储结构第章图第章图三、十字链表三、十字链表( (

17、结点结构结点结构) )27第二节图的存储结构第二节图的存储结构n弧的结点结构弧的结点结构 tailvex;/ tailvex;/ 弧尾顶点的位置弧尾顶点的位置 headvex;/ headvex;/ 弧头顶点的位置弧头顶点的位置 tlink; / tlink; / 指向弧尾相同的下一条弧指向弧尾相同的下一条弧 hlink; / hlink; / 指向弧头相同的下一条弧指向弧头相同的下一条弧 info; / info; / 该弧相关信息的指针或权值该弧相关信息的指针或权值第章图第章图tailvexheadvexhlinktlinkinfo三、十字链表三、十字链表( (结点结构结点结构) )28第

18、二节图的存储结构第二节图的存储结构n顶点的结点结构顶点的结点结构data; / data; / 与顶点相关的信息与顶点相关的信息firstin; / firstin; / 指向以顶点为弧头的第一个弧结指向以顶点为弧头的第一个弧结点点firstout;/ firstout;/ 指向以顶点为弧尾的第一个弧结指向以顶点为弧尾的第一个弧结点点第章图第章图datafirstinfirstout三、十字链表三、十字链表( (举例举例) )29第二节图的存储结构第二节图的存储结构第章图第章图0 123413240010304122432四、邻接多重表四、邻接多重表( (Adjacency Multilist

19、Adjacency Multilist) )30第二节图的存储结构第二节图的存储结构n邻接多重表是邻接多重表是无向图的另一种存储结构无向图的另一种存储结构n在无向图中，一条边要用在无向图中，一条边要用2 2个结点表示个结点表示( (分别从分别从2 2个顶点的角度看个顶点的角度看) )n在邻接多重表中，一条边只用一个结点表示在邻接多重表中，一条边只用一个结点表示n将所有具有某顶点的结点，全部用链连结起来，将所有具有某顶点的结点，全部用链连结起来，链所在的域为该顶点对应的指针域链所在的域为该顶点对应的指针域第章图第章图四、邻接多重表四、邻接多重表( (结点结构结点结构) )31第二节图的存储结构第

20、二节图的存储结构n边的结点结构边的结点结构 mark; / mark; / 标记域，如指示该边是否被搜索过标记域，如指示该边是否被搜索过 ivex,jvex;/ ivex,jvex;/ 该边所依附的两个顶点的位置该边所依附的两个顶点的位置 ilink;/ ilink;/ 指向下一条依附于指向下一条依附于ivexivex的边的边 jlink;/ jlink;/ 指向下一条依附于指向下一条依附于jvexjvex的边的边 info; / info; / 该边相关信息的指针或权值该边相关信息的指针或权值第章图第章图ivexmarkilinkjvexjlinkinfo四、邻接多重表四、邻接多重表( (举

21、例举例) )32第二节图的存储结构第二节图的存储结构第章图第章图132540012345101 5 351250 4032 3454 13 一、图的遍历一、图的遍历33第三节图的遍历第三节图的遍历n从图的某一顶点开始，访遍图中其余顶点，且从图的某一顶点开始，访遍图中其余顶点，且使每一个顶点仅被访问一次使每一个顶点仅被访问一次n图的遍历主要应用于无向图图的遍历主要应用于无向图第章图第章图二、深度优先搜索二、深度优先搜索( (DFS)DFS)34第三节图的遍历第三节图的遍历n图的深度优先搜索是树的先根遍历的推广图的深度优先搜索是树的先根遍历的推广n图中可能存在回路，且图的任一顶点都可能与图中可能存

22、在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。沿着某些边又回到了曾经访问过的顶点。n为了避免重复访问，可设置一个标志顶点是否为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组被访问过的辅助数组 visited visited 第章图第章图二、深度优先搜索二、深度优先搜索( (DFSDFS算法算法) )第三节图的遍历第三节图的遍历n所有顶点访问标志所有顶点访问标志visitedvisited设置为设置为FALSEFALSEn从某顶点从某顶点v v0 0开始，设开始，设v=vv=v0 01.

23、1.如果如果visitedv=FALSE，则访问该顶点，且设访问该顶点，且设visitedv=TRUE2.2.如果找到当前顶点的一个新的相邻顶点如果找到当前顶点的一个新的相邻顶点w,w,设设v=w,v=w,重重复复1 13.3.否则否则( (说明当前顶点的所有相邻顶点都已被访问过，说明当前顶点的所有相邻顶点都已被访问过，或者当前顶点没有相邻顶点或者当前顶点没有相邻顶点) )，如果当前顶点是，如果当前顶点是v v0 0，退出；否则返回上一级顶点退出；否则返回上一级顶点，重复重复2 2第章图第章图二、深度优先搜索二、深度优先搜索( (DFSDFS算法算法) )第三节图的遍历第三节图的遍历n所有顶点

24、访问标志所有顶点访问标志visitedvisited设置为设置为FALSEFALSEn将初始顶点将初始顶点v v0 0压入栈，设压入栈，设v=vv=v0 01.1.检测栈是否为空。若栈为空，则迭代结束；否则，检测栈是否为空。若栈为空，则迭代结束；否则，从栈顶弹出一个顶点从栈顶弹出一个顶点v v；2.2.如果如果visitedv=FALSE，则访问该顶点，且设访问该顶点，且设visitedv=TRUE3.3.求出求出v v的邻接顶点表，将的邻接顶点表，将v v的未被访问的邻接顶点压的未被访问的邻接顶点压入栈，重复入栈，重复1 1第章图第章图第章图第章图n二、深度优先搜索二、深度优先搜索( (DF

25、SDFS算法算法) )nAGFBCEDAGFBCEDADBFEGC二、深度优先搜索二、深度优先搜索( (举例举例) )38第三节图的遍历第三节图的遍历n采用以下链表存储结构时，采用以下链表存储结构时，DFSDFS次序为次序为0,1,2,3,4,50,1,2,3,4,5第章图第章图1325400 F1 F2 F3 F4 F5 F14502313124503501345visit二、深度优先搜索二、深度优先搜索( (举例举例) )39第三节图的遍历第三节图的遍历nDFSDFS次序为次序为V1,V2,V4,V8,V5,V3,V6,V7V1,V2,V4,V8,V5,V3,V6,V7第章图第章图V1V3

26、V2V5V4V6V7V8三、广度优先搜索三、广度优先搜索( (BFS)BFS)40第三节图的遍历第三节图的遍历n广度优先搜索广度优先搜索( (BFS)BFS)是一种分层搜索方法是一种分层搜索方法nBFSBFS每向前走一步可能访问一批顶点每向前走一步可能访问一批顶点, , 不存在不存在往回退的情况往回退的情况nBFSBFS不是一个递归的过程。不是一个递归的过程。第章图第章图三、广度优先搜索三、广度优先搜索( (BFSBFS算法算法) )41第三节图的遍历第三节图的遍历n所有顶点访问标志所有顶点访问标志visitedvisited设置为设置为FALSEFALSEn从某顶点从某顶点v v0 0开始，

27、访问开始，访问v v0 0，visitedv0=TRUE，将将v v0 0插插入队列入队列Q Q1.1.如果队列如果队列Q Q不空，则从队列不空，则从队列Q Q头上取出一个顶点头上取出一个顶点v,v,否否则结束则结束2.2.依次找到顶点依次找到顶点v v的所有相邻顶点的所有相邻顶点v v，如果如果visitedv=FALSE，访问该顶点，访问该顶点v v，visitedv=TRUE，将将v v插入队列插入队列Q Q3.3.重复重复1,21,2第章图第章图三、广度优先搜索三、广度优先搜索( (举例举例) )第三节图的遍历第三节图的遍历BFSBFS为为0,1,4,5,2,3 0,1,4,5,2,3

28、 BFSBFS为为v1,v2,v3,v4,v1,v2,v3,v4, v5,v6,v7,v8 v5,v6,v7,v8第章图第章图132540V1V3V2V5V4V6V7V8一、无向图的连通性一、无向图的连通性43第四节图的连通性问题第四节图的连通性问题n如果无向图中，存在不连通的顶点，则该图称如果无向图中，存在不连通的顶点，则该图称为非连通图为非连通图第章图第章图ACDEBFOGNMLK二、无向图的连通分量二、无向图的连通分量44第四节图的连通性问题第四节图的连通性问题n非连通图的极大连通子图叫做连通分量非连通图的极大连通子图叫做连通分量n若从无向图的每一个连通分量中的一个顶点出若从无向图的每一

29、个连通分量中的一个顶点出发进行发进行DFSDFS或或BFSBFS遍历，可求得无向图的所有连遍历，可求得无向图的所有连通分量的生成树通分量的生成树(DFS(DFS或或BFSBFS生成树生成树) )n所有连通分量的生成树组成了非连通图的生成所有连通分量的生成树组成了非连通图的生成森林森林第章图第章图二、无向图的生成树二、无向图的生成树45第四节图的连通性问题第四节图的连通性问题n由由DFSDFS遍历，求得连通分量称为遍历，求得连通分量称为DFSDFS生成树生成树n由由BFSBFS遍历，求得连通分量称为遍历，求得连通分量称为BFSBFS生成树生成树第章图第章图BFS生成树DFS生成树ACDEBFOG

30、NMLK三、最小生成树三、最小生成树46第四节图的连通性问题第四节图的连通性问题n如果无向图中，边上有权值，则称该无向图为如果无向图中，边上有权值，则称该无向图为无向网无向网n如果无向网中的每个顶点都相通，称为连通网如果无向网中的每个顶点都相通，称为连通网n最小生成树最小生成树( (Minimum Cost Spanning Tree)Minimum Cost Spanning Tree)是是代价最小的连通网的生成树，即该生成树上的代价最小的连通网的生成树，即该生成树上的边的权值和最小边的权值和最小第章图第章图三、最小生成树三、最小生成树( (准则准则) )47第四节图的连通性问题第四节图的连

31、通性问题n必须使用且仅使用连通网中的必须使用且仅使用连通网中的n-1n-1条边来联结条边来联结网络中的网络中的n n个顶点；个顶点；n不能使用产生回路的边；不能使用产生回路的边；n各边上的权值的总和达到最小。各边上的权值的总和达到最小。第章图第章图四、普里姆四、普里姆( (Prim)Prim)算法生成最小生成树算法生成最小生成树48第四节图的连通性问题第四节图的连通性问题n假设假设N=(V,E)N=(V,E)是连通网是连通网nTETE是是N N上最小生成树中边的集合上最小生成树中边的集合1.1.U=uU=u0 0 ，(u(u0 0 V), TE=V), TE=2.2.在所有在所有u u U,v

32、U,v V-UV-U的边的边( (u,v)u,v) E E中找一条代价中找一条代价最小的边最小的边( (u,vu,v0 0) )并入集合并入集合TETE，同时同时v v0 0并入并入U U3.3.重复重复2 2，直到，直到U=VU=V第章图第章图四、普里姆四、普里姆( (Prim)Prim)算法举例算法举例49第四节图的连通性问题第四节图的连通性问题第章图第章图105046132原图 (a) (b)(c) (d) (e) (f)50461210251422161235046132102525504613210222550461321022122850461321025142422161812五

33、、克鲁斯卡尔五、克鲁斯卡尔( (Kruskal)Kruskal)算法生成最小生成树算法生成最小生成树50第四节图的连通性问题第四节图的连通性问题n假设假设N=(V,E)N=(V,E)是连通网是连通网1.1.非连通图非连通图T=V,T=V,，图中每个顶点自成一个图中每个顶点自成一个连通分量连通分量2.2.在在E E中找一条代价最小，且其两个顶点分别依中找一条代价最小，且其两个顶点分别依附不同的连通分量的边，将其加入附不同的连通分量的边，将其加入T T中中3.3.重复重复2 2，直到，直到T T中所有顶点都在同一连通分量上中所有顶点都在同一连通分量上第章图第章图五、克鲁斯卡尔五、克鲁斯卡尔( (K

34、ruskal)Kruskal)算法举例算法举例51第四节图的连通性问题第四节图的连通性问题第章图第章图(c) (d) (e) (f)28504613210251424221618 12原图 (a) (b)5046132105046132101250461321014125046132101416125046132102514221612一、最短路径一、最短路径52第五节最短路径第五节最短路径n最短路径是求从图（或网）中某一顶点，到其余各顶最短路径是求从图（或网）中某一顶点，到其余各顶点的最短路径点的最短路径n最短路径与最小生成树主要有三点不同：最短路径与最小生成树主要有三点不同：1.1.最短路

35、径的操作对象主要是有向图最短路径的操作对象主要是有向图( (网网) )，而最小生，而最小生成树的操作对象是无向图成树的操作对象是无向图2.2.最短路径有一个始点，最小生成树没有最短路径有一个始点，最小生成树没有3.3.最短路径关心的是始点到每个顶点的路径最短，而最短路径关心的是始点到每个顶点的路径最短，而最小生成树关心的是整个树的代价最小最小生成树关心的是整个树的代价最小第章图第章图二、二、DijkstraDijkstra算法算法53第五节最短路径第五节最短路径n最短路径可以采用迪杰斯特拉最短路径可以采用迪杰斯特拉( (Dijkstra)Dijkstra)算法算法求解求解nDijkstraDi

36、jkstra算法采用按路径长度递增的次序产生算法采用按路径长度递增的次序产生最短路径最短路径第章图第章图二、二、DijkstraDijkstra算法算法54第五节最短路径第五节最短路径n在在DijkstraDijkstra算法中，引进了一个辅助向量算法中，引进了一个辅助向量D Dn每个分量每个分量DiDi表示当前所找到的从始点到每个表示当前所找到的从始点到每个终点终点v vi i的最短路径长度的最短路径长度nDiDi初值为始点初值为始点v v0 0到各终点到各终点v vi i的直接距离，即的直接距离，即若从始点到某终点有若从始点到某终点有( (出出) )弧，则为弧上的权值，弧，则为弧上的权值，

37、否则为否则为第章图第章图二、二、DijkstraDijkstra算法算法第五节最短路径第五节最短路径n对于下图，如果对于下图，如果0 0是始点是始点v v0 0，则则DiDi的初值为：的初值为：Di=5,7,15Di=5,7,15n显然，显然， Dj=MinDi | vDj=MinDi | vi i VV 是从始点出发的长度最短的是从始点出发的长度最短的 一条最短路径一条最短路径第章图第章图132405515172二、二、DijkstraDijkstra算法算法第五节最短路径第五节最短路径n设设S S为已求得的最短路径的终点的集合为已求得的最短路径的终点的集合n下一条最短路径下一条最短路径(

38、(设其终点为设其终点为v vi i) )为以下之一：为以下之一：1.1.中间只经过中间只经过S S中的顶点而后到达顶点中的顶点而后到达顶点v vi i的路径的路径2.2.弧弧 nDjDj=MinDi | v=MinDi | vi i V-SV-S Dk=v Dk= or Di=Dj+ or Di=Dj+ 第章图第章图132405515172二、二、DijkstraDijkstra算法算法第五节最短路径第五节最短路径第章图第章图57二、二、DijkstraDijkstra算法算法第五节最短路径第五节最短路径第章图第章图顶点D152109377415151510终点j1324S0,10,1,30,

39、1,3,2 0,1,3,2,4132405515172一、有向无环图一、有向无环图( (DAG)DAG)第六节有向无环图及其应用第六节有向无环图及其应用n有向无环图有向无环图( (DAG:Directed Acycline Graph)DAG:Directed Acycline Graph)是图中无环的有向图是图中无环的有向图第章图第章图1324013240DAG非DAG59一、有向无环图一、有向无环图( (DAG)DAG)第六节有向无环图及其应用第六节有向无环图及其应用n有向图中，可以用深度优先有向图中，可以用深度优先搜索搜索( (DFS)DFS)，找出是否存在环找出是否存在环n从某个顶点从

40、某个顶点v v出发，进行出发，进行DFSDFS，如果存在一条从顶点如果存在一条从顶点u u到到v v的的回边，则有向图中存在环回边，则有向图中存在环nDFS: 0,1,2,DFS: 0,1,2,4 4,3,3第章图第章图13240非DAG二、拓扑排序二、拓扑排序第六节有向无环图及其应用第六节有向无环图及其应用1.1.偏序偏序n若集合若集合X X上的关系上的关系R R是：是：. .自反的：自反的：x R xx R x. .反对称的：反对称的：x R yx R y且且y R x =x=yy R x =x=y. .传递的：传递的：xRy & yRz = xRzxRy & yRz = xRz 则称则称

41、R R是集合是集合X X上的偏序关系上的偏序关系第章图第章图13240二、拓扑排序二、拓扑排序第六节有向无环图及其应用第六节有向无环图及其应用2.2.全序全序n设关系设关系R R是集合是集合X X上的偏序，如果对每个上的偏序，如果对每个x,yx,y X X，必有必有xRyxRy或者或者yRxyRx，则称则称R R是是X X上的全序关系上的全序关系n偏序指集合中仅有部分成员之间可比较偏序指集合中仅有部分成员之间可比较n全序指集合中全体成员之间均可比较全序指集合中全体成员之间均可比较第章图第章图62二、拓扑排序二、拓扑排序第六节有向无环图及其应用第六节有向无环图及其应用3.3.拓扑有序拓扑有序n右

42、图是一个偏序关系，因为右图是一个偏序关系，因为1,31,3没有先后关系没有先后关系n如果人为地增加如果人为地增加1,31,3先后关系，先后关系，如如1 1先于先于3 3，则右图变为全序，则右图变为全序， 称为拓扑有序称为拓扑有序第章图第章图13240二、拓扑排序二、拓扑排序第六节有向无环图及其应用第六节有向无环图及其应用4.4.拓扑排序拓扑排序n由偏序定义得到的拓扑有序的操作称拓扑排序由偏序定义得到的拓扑有序的操作称拓扑排序n算法：算法：. .在有向图中选一个没有前驱的顶点且输出之在有向图中选一个没有前驱的顶点且输出之. .从图中删除该顶点和所有以它为尾的弧从图中删除该顶点和所有以它为尾的弧

43、重复两步，直到所有顶点输出为止重复两步，直到所有顶点输出为止第章图第章图64二、拓扑排序二、拓扑排序( (举例举例) )第六节有向无环图及其应用第六节有向无环图及其应用第章图第章图132413240原图输出0之后324输出0,1之后24输出0,1,3之后4最后输出拓扑排序结果：0,1,3,2,4输出0,1,3,2之后三、三、AOV-AOV-网网第六节有向无环图及其应用第六节有向无环图及其应用n如果用有向图的顶点表示活动，用弧表示活动如果用有向图的顶点表示活动，用弧表示活动间的优先关系，则称该有向图为顶点表示活动间的优先关系，则称该有向图为顶点表示活动的网的网AOV(Activity On Ve

44、rtex Network)AOV(Activity On Vertex Network)nAOVAOV一定是一定是DAGDAG，即图中不存在环，因为存在环即图中不存在环，因为存在环意味着某项活动应以自己为先决条件意味着某项活动应以自己为先决条件nAOVAOV的应用包括流程图等的应用包括流程图等第章图第章图66三、三、AOV-AOV-网网( (举例举例) )第六节有向无环图及其应用第六节有向无环图及其应用课程代号课程代号 课程名称课程名称 先修课程先修课程n拓扑排序结果为拓扑排序结果为 C1 , C2 , C3 , C4 , C5 , C6, C8 , C9 , C7或或 C1 , C8 , C

45、9 , C2 , C5 , C3 , C4 , C7 , C6第章图第章图C8C3C5C4C9C6C7C1C267四、四、AOE-AOE-网网第六节有向无环图及其应用第六节有向无环图及其应用n如果用有向图的顶点表示事件，用弧表示活动，如果用有向图的顶点表示事件，用弧表示活动，则称该有向图为边表示活动的网则称该有向图为边表示活动的网AOE(Activity AOE(Activity On Edge)On Edge)nAOEAOE同样是同样是DAGDAGnAOEAOE包括估算工程的完成时间包括估算工程的完成时间第章图第章图13240a1=5a2=5a5=15a6=1a3=7a4=2五、关键路径五、

46、关键路径第六节有向无环图及其应用第六节有向无环图及其应用n求工程的完成时间是求工程的完成时间是AOEAOE的一个应用的一个应用n在工程问题中，需要研究的问题有：在工程问题中，需要研究的问题有：. .完成整个工程至少需要多少时间？完成整个工程至少需要多少时间？. .哪些活动是影响工程进度的关键？哪些活动是影响工程进度的关键？第章图第章图69五、关键路径五、关键路径第六节有向无环图及其应用第六节有向无环图及其应用1.1.关键路径关键路径n工程问题的工程问题的AOEAOE网中，从工程开始网中，从工程开始( (顶点顶点) )到工到工程结束程结束( (顶点顶点) )之间路径长度最长的路径叫关键之间路径长

47、度最长的路径叫关键路径路径n提前完成关键路径上的活动，工程进度会加快提前完成关键路径上的活动，工程进度会加快n提前完成非关键路径上的活动，对工程无帮助提前完成非关键路径上的活动，对工程无帮助第章图第章图70五、关键路径五、关键路径第六节有向无环图及其应用第六节有向无环图及其应用2.2.关键活动关键活动n关键路径上的所有活动称为关键活动关键路径上的所有活动称为关键活动n找到工程找到工程AOEAOE中的所有关键活动，即找到了关中的所有关键活动，即找到了关键路径键路径第章图第章图71五、关键路径五、关键路径第六节有向无环图及其应用第六节有向无环图及其应用3.3.关键活动有关的量关键活动有关的量ne(

48、i)e(i)：活动活动a ai i最早开始时间最早开始时间nl(i)l(i)：活动活动a ai i最迟开始时间最迟开始时间nl(i)-e(i)l(i)-e(i)：活动活动a ai i开始时间余量开始时间余量n如果如果l(i)=e(i)l(i)=e(i)，则称活动则称活动a ai i为关键活动为关键活动第章图第章图7213240a1=5a2=5a5=15a6=1a3=7a4=2五、关键路径五、关键路径第六节有向无环图及其应用第六节有向无环图及其应用3.3.关键活动有关的量关键活动有关的量nve(j)ve(j)：事件事件v vj j最早开始时间最早开始时间nvl(j)vl(j)：事件事件v vj

49、j最迟开始时间最迟开始时间ne(i)=ve(j)e(i)=ve(j)nl(j)=vl(k)-dut() l(j)=vl(k)-dut() dut()dut()为活动为活动a ai i的持续时间的持续时间第章图第章图7313240a1=5a2=5a5=15a6=1a3=7a4=2五、关键路径五、关键路径第六节有向无环图及其应用第六节有向无环图及其应用3.3.关键活动有关的量关键活动有关的量n从从ve(0)=0ve(0)=0开始向前递推开始向前递推 ve(j)=Maxve(i)+dut() ve(j)=Maxve(i)+dut() T T，T T是所有以第是所有以第j j个顶点为头的弧的集合个顶点

50、为头的弧的集合n从从vl(n-1)=ve(n-1)vl(n-1)=ve(n-1)起向后递推起向后递推 vl(i)=Minvl(j)-dut() vl(i)=Minvl(j)-dut() S S，S S是所有以第是所有以第i i个顶点为尾的弧的集合个顶点为尾的弧的集合第章图第章图7413240a1=5a2=5a5=15a6=1a3=7a4=2五、关键路径五、关键路径第六节有向无环图及其应用第六节有向无环图及其应用4.4.求关键活动算法求关键活动算法n从始点从始点v v0 0出发，令出发，令ve0=0ve0=0，按拓扑有序求按拓扑有序求vejvejn从终点从终点v vn-1n-1出发，令出发，令v