ch图实用学习教程.pptx

《ch图实用学习教程.pptx》由会员分享，可在线阅读，更多相关《ch图实用学习教程.pptx（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、哥尼斯堡七桥问题BDACABCD问题：如何不重复地走完问题：如何不重复地走完七桥后回到起点？七桥后回到起点？一笔画问题如何将此图一笔画出？欧拉（欧拉（1707178317071783）（17361736年解决该题）年解决该题）中国邮递员问题中国邮递员问题（19621962年管梅谷首次提出）年管梅谷首次提出）第1页/共70页周游世界问题问题：能否从某个城市出发，沿交问题：能否从某个城市出发，沿交通线路经过每个城市一次且仅一次，通线路经过每个城市一次且仅一次，最后回到出发点？最后回到出发点？哈密尔顿哈密尔顿（18591859年提出该问题）年提出该问题）第2页/共70页第七章 图7.1 图的定义和术

2、语图(Graph)图G是由两个集合V(G)和E(G)组成的，记为G=(V,E)其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对有向图有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v、w是顶点，v为弧尾，w为弧头无向图无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v)第3页/共70页例：例：v2v4v5v1v3v6G1图图G1中：中：V(G1)

3、=v1,v2,v3,v4,v5,v6E(G1)=,例：例：v1v5v7v3v2v4G2v6图图G2中：中：V(G2)=v1,v2,v3,v4,v5,v6,v7 E(G1)=(v1,v2),(v1,v3),(v2,v3),(v2,v4),(v2,v5),(v5,v6),(v5,v7)第4页/共70页有向完备图n个顶点的有向图最大边数是n(n-1)无向完备图n个顶点的无向图最大边数是n(n-1)/2权与图的边或弧相关的数叫网带权的图叫子图如果图G(V,E)和图G(V,E),满足：V VE E 则称G为G的子图顶点的度(Degree)无向图中，顶点v的度是和v相连的边的数目，记为TD(V)有向图中，

4、顶点的度分成入度(InDegree)与出度(OutDegree)入度：以该顶点v为头的弧的数目，记为ID(V)出度：以该顶点v为尾的弧的数目，记为OD(V)握手定理：一个有n个顶点，e条边或弧的图，满足如下关系第5页/共70页例：例：v2v1v3v2v1v3有向完备图有向完备图无向完备图无向完备图v3v5v6例：例：v2v4v5v1v3v6图与子图图与子图v2v4v5v1v3v6G2顶点顶点v2入度：入度：1 出度：出度：3顶点顶点v4入度：入度：1 出度：出度：0例：例：v1v5v7v3v2v4G1v6顶点顶点v v5的度：的度：3 3顶点顶点v v2的度：的度：4 4第6页/共70页v权与

5、边有关的数据信息称为权。v网边上带权的图称为网。v1v2v5v4v3176324 58无向网无向网BCA21435有向网有向网第7页/共70页v路径路径是一个顶点的序列V=Vi0,Vi1,Vin，满足(Vij-1,Vij)E 或 E,(1 j n)v路径长度沿路径边的数目或沿路径弧的数目之和v回路（或环）第一个顶点和最后一个顶点相同的路径叫v简单路径序列中顶点不重复出现的路径叫v简单回路（简单环）除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫v连通从顶点V到顶点W有一条路径，则说V和W是连通的v连通图无向图中任意两个顶点都是连通的图叫v连通分量指的是无向图中的极大连通子图，也就是非

6、连通图的每一个连通部分叫v强连通图有向图中，如果对每一对Vi、Vj V,Vi Vj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是v强连通分量指的是有向图的极大强连通子图第8页/共70页例：例：v1v5v7v3v2v4G2v6例：例：v2v4v5v1v3v6G1路径：路径：v1 v2 v3 v5 v6 v3路径长度：路径长度：5简单路径：简单路径：v1 v2 v3 v5回路：回路：v1 v2 v3 v5 v6 v3 v1简单回路：简单回路：v3 v5 v6 v3路径：路径：v1 v2 v5 v7 v6 v5 v2 v3路径长度：路径长度：7简单路径：简单路径：v1 v2 v5 v7 v6回

7、路：回路：v1 v2 v5 v7 v6 v5 v2 v1简单回路：简单回路：v1 v2 v3 v1第9页/共70页连通图连通图强连通图强连通图v3v5v6例：例：非强连通图非强连通图3 3个强连通分量个强连通分量例：例：v2v4v5v1v3v6例：例：ABLMCFDEGHKIJ非连通图非连通图3 3个连通分量个连通分量例：例：v2v4v5v1v3v6第10页/共70页生成树：所有顶点均由边连接在一起，但不存在回路的图叫生成树有深度优先生成树与广度优先生成树两种。一个连通图的生成树：一个有n个顶点连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n1条边。所有生成树具有

8、以下特征：生成树的顶点个数与图的顶点个数相同；生成树是图的一个极小连通子图；一个有n个顶点的连通图的生成树有n-1条边；生成树中任意两个顶点间的路径是唯一的；在生成树中加一条边必然构成回路。注意：有n1条边的图不一定是生成树。生成森林：非连通图每个连通分量的生成树一起组成非连通图的有向树：一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵一个有向图的生成森林：由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。GHKI第11页/共70页v5v1v3v2v4G G1 1的一棵生成树的一棵生成树例：例：v1v5v3v2v4G1ABLMCFJDEGHKI非连通

9、图非连通图G G2 2的生成森林的生成森林例：例：ABLMCFDEGHKIJ非连通图非连通图G G2 2第12页/共70页ABCFDEABCFED有向图有向图G3有向图有向图G3的生成森林的生成森林第13页/共70页6.2 图的存储结构多重链表例：例：G1v2v4v1v3例：例：v1v5v3v2v4G2V1V2 V4 V3 V1 V2 V4 V5 V3第14页/共70页一、数组表示法邻接矩阵表示顶点间相联关系的矩阵定义：设G=(V,E)是有n 1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵例：例：G1v2v4v1v3例：例：v1v5v3v2v4G2第15页/共70页邻接矩阵的特点：无向图

10、的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为 n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n有向图的矩阵中1的个数为图中弧的数目；无向图的矩阵中1的个数的一半为图中边的数目无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和网络的邻接矩阵可定义为：第16页/共70页网络的邻接矩阵网络的邻接矩阵例：例：v1v4v5v2v375318642网络网络第17页/共70页关联矩阵表示顶点与边的关联关系的矩阵v定义：设G=(V,E)是有n1个顶点，e0条边的图，G的关联矩阵A是具

11、有以下性质的ne阶矩阵第18页/共70页例：例：G1v2v4v1v31234例：例：v1v5v3v2v4G2123456第19页/共70页关联矩阵的特点关联矩阵每列只有两个非零元素，是稀疏矩阵；n越大，零元素比率越大无向图中顶点Vi的度TD(Vi)是关联矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行中1的个数顶点Vi的入度是A中第i行中1的个数第20页/共70页二、邻接表(Adjacency List)图的一种链式存储结构v邻接表是图的一种顺序存储与链式存储结合的存储方法。v邻接表表示法类似于树的孩子链表表示法，就是对于图G中的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，这

12、个单链表就称为顶点vi的邻接表，再将所有的邻接表表头放到数组中，就构成了图的邻接表。其中，单链表中的结点称为表结点，每个单链表设的一个头结点称为头结点。v实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是指以顶点vi为尾的弧）。第21页/共70页v表头结点：表头结点：typedef struct VNode VertexType data;/存放顶点信息存放顶点信息 ArcNode *firstarc;/指示第一指示第一条依附该条依附该 顶点的边或弧的指针顶点的边或弧的指针VNode;#define M 20VNode AdjListM;/AdjList

13、0不用不用 data firstarc图的邻接表存储表示图的邻接表存储表示v表结点：表结点：typedef struct ArcNode int adjvex;/邻接点域，存放与邻接点域，存放与v vi i邻接的点在表头数组中的位置邻接的点在表头数组中的位置 struct ArcNode *nextarc;/链域，指示下一条边或弧链域，指示下一条边或弧的指针的指针 InfoType*info;/信息域，存放信息域，存放边或弧边或弧相关信息的指针相关信息的指针ArcNode;adjvex nextarc info第22页/共70页例：例：G2bdac例：例：aecbdG11234acdbdata

14、firstarc 3 2 4 1adjvex next1234acdbdatafirstarc 4 2 1 2adjvex next5e 4 3 5 1 5 3 2 3第23页/共70页图的邻接表特点无向图的邻接表中需要n个表头结点和2e个表结点有向图的邻接表中需要n个表头结点和e个表结点无向图中顶点Vi的度为第i个单链表中的表结点数有向图中顶点Vi的出度为第i个单链表中的表结点数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表例：例：Gbdac1234acdbdatafirstarc 4 1 1 3adjvex next第24页/共7

15、0页三、有向图的十字链表(Orthogonal List)弧结点：typedef struct ArcBox int tailvex,headvex;/弧尾、弧头在表头数组中的位置 struct ArcBox *hlink；/指向弧头相同的下一条弧的链域 struct ArcBox *tlink;/指向弧尾相同的下一条弧的链域ArcBox;tailvex headvex hlink tlink顶点结点：typedef struct VexNode VertexType data;/存与顶点有关信息 ArcBox *firstin；/指向以该顶点为弧头的第一个弧结点 ArcBox *firsto

16、ut;/指向以该顶点为弧尾的第一个弧结点OLGraph;OLGraph gM;/g0不用data firstin firstout第25页/共70页例：例：bdacab cd1234 1 3 1 2 3 4 3 1 4 3 4 2 4 1数据域 弧头链域 弧尾链域尾域 头域 弧头链域 弧尾链域第26页/共70页四、无向图的邻接多重表顶点结点：typedef struct dnode int data;/存与顶点有关的信息 struct node *firstedge;/指向第一条依附于该顶点的边DD;DD gaM;/ga0不用data firstedge边结点：typedef struct n

17、ode int mark;/标志域 int ivex,jvex;/该边依附的两个顶点在表头数组中位置 struct node *ilink,*jlink;/分别指向依附于ivex和jvex的下一条边JD;mark ivex ilink jvex jlink第27页/共70页例：例：aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 2第28页/共70页 2929 课堂练习下面关于图的存储的叙述中，哪一个是正确的。A用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关 B用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C用邻接表法存

18、储图，占用的存储空间数只与图中结点个数有关，而与边数无关D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关 第29页/共70页7.3 图的遍历(Traversing Graph)图的遍历定义：从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历有四个难点：首结点、非连通图、回路、多个相连顶点深度优先遍历(Depth_First Search)方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起

19、点，重复上述过程，直至图中所有顶点都被访问到为止。V1V2V4V5V3V7V6V8例：例：深度优先遍历：深度优先遍历：V1 V2 V4 V8 V5 V3 V6 V7第30页/共70页深度优先遍历算法（需要采用栈来暂存顶点）递归算法开始访问V0,置标志求V0邻接点有邻接点w求下一邻接点wV0W访问过结束NYNYDFS开始标志数组初始化Vi=1Vi访问过DFSVi=Vi+1Vi=Vexnums结束NNYY第31页/共70页V1V2V4V5V3V7V6V8例：深度优先遍历：深度优先遍历：V11234v1v3v4v2vexdata firstarc 3 1 2 2adjvex next5v5 6 4

20、5 1 78 2 8v6v7v8678 3 7 3 6 4 5V2 V4 V8 V5 V3 V6 V7第32页/共70页深度优先遍历算法实现过程(从V V1 1出发,邻接表存储)v1v2v3v4v5v6v7v8231451672828373645v1v4v8v5v3v6v7112345678访问标志11v211111注注:1:1、从、从V V1 1出发，单击鼠标一次，完成一个结点出发，单击鼠标一次，完成一个结点的遍历，并找到未访问的邻结点；的遍历，并找到未访问的邻结点；2 2、访问标志为空时（算法中为、访问标志为空时（算法中为0 0）表示未被）表示未被访问，为访问，为1 1时表示本结点已访问；

21、时表示本结点已访问；3 3、每访问一个结点，该结点进栈，当栈顶、每访问一个结点，该结点进栈，当栈顶结点没有未被访问的邻点时，栈顶结点出栈。结点没有未被访问的邻点时，栈顶结点出栈。栈深度优先遍历结果：深度优先遍历结果：v1 v2 v4 v8 v5 v3 v6 v7第33页/共70页V1V2V4V5V3V7V6V8例：例：1234v1v3v4v2vexdata firstarc 3 6 8 2adjvex next5v5 7 4 2 8v6v7v8678 7深度优先遍历：深度优先遍历：V1 V2 V4 V8 V3 V6 V7 V5第34页/共70页广度优先遍历(Breadth_First Sear

22、ch)v方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问到为止。广度优先遍历：广度优先遍历：V1 V2 V3 V4 V5 V6 V7 V8例：例：V V1 1 V V8 8 V V7 7 V V6 6 V V5 5 V V4 4 V V3 3 V V2 2V V1 1 V V2 2 V V3 3 V V4 4 V V5 5 V V6 6 V V8 8 V V7 7第35页

23、/共70页v广度优先遍历算法（需要采用队列来暂存顶点）l非递归算法：开始标志数组初始化Vi=1Vi访问过BFSVi=Vi+1Vi=Vexnums结束NNYY第36页/共70页开始访问V0,置标志求V邻接点ww存在吗V下一邻接点ww访问过结束NYNYBFS初始化队列V0入队队列空吗队头V出队访问w,置标志w入队NaaY第37页/共70页V1V2V4V5V3V7V6V8例：广度优先遍历：广度优先遍历：V11234v1v3v4v2vexdata firstarc 3 1 2 2adjvex next5v5 6 4 5 1 78 2 8v6v7v8678 3 7 3 6 4 5V2 V3 V4 V5

24、V6 V7 V8第38页/共70页广度优先遍历算法实现过程(从V V1 1出发,邻接表存储)v1v2v3v4v5v6v7v8231451672828373645v1v4v8v5v3v6v7112345678访问标志11v211111v1广度优先遍历结果：广度优先遍历结果：v2 v3 v4 v5 v6 v7 v8队列队列第39页/共70页V1V2V4V5V3V7V6V8例：例：广度优先遍历：广度优先遍历：V1 V2 V3 V4 V6 V7 V8 V51234v1v3v4v2vexdata firstarc 3 6 8 2adjvex next5v5 7 4 2 8v6v7v8678 7第40页/

25、共70页V1V2V4V5V3V7V6V8例：例：深度遍历：深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8深度优先生成树深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V8第41页/共70页对下面所示的图完成如下操作：对下面所示的图完成如下操作：1 1、分分别别写写出出该该图图的的邻邻接接矩矩阵阵与与 邻邻 接接 表表 表表 示示 法法；2 2、从从顶顶点点A A 出出发发分分别别写写出出DFSDFS和和

26、 BFSBFS遍遍 历历 序序 列列；3 3、从从顶顶点点A A 出出发发分分别别画画出出DFSDFS和和BFSBFS生成树。生成树。ACDEGBFIH第42页/共70页ACDEGBFIH邻接矩阵第43页/共70页深深 度度 优优 先先 搜搜 索索 DFS(Depth First Search)ACDEGBFIHACDEGBFIH128934567128934567前进回退深度优先搜索过程深度优先搜索过程 深度优先生成树深度优先生成树从顶点从顶点A A出发的出发的DFSDFS：A-B-C-F-D-H-I-E-GA-B-C-F-D-H-I-E-G第44页/共70页广广度度优优先先搜搜索索BFS(

27、Breadth First Search)AEBACDEGBFH689123456789广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树CDGFIH123457I从顶点从顶点A A出发的出发的BFSBFS：A-B-C-D-E-F-G-H-IA-B-C-D-E-F-G-H-I第45页/共70页7.4.3 最小生成树(Minimum Spanning Tree)无向图的应用示例一、问题提出 要在n个城市之间建立通信联络网，则连通n个城市需要n1条线路。如何在最节省经费的前提下建立这个通信网呢？顶点表示城市权城市间建立通信线路所需花费代价 这个问题就是希望找到一棵生成树，它的每条边上的

28、权值之和（即建立该通信网所需花费的总代价）最小 最小代价生成树。二、问题分析n个城市间，最多可能设置n(n1)/2条线路n个城市间建立通信网，只需n-1条线路问题转化为：如何在可能的线路中选择n1条，能把所有城市（顶点）均连起来，且总耗费（各边权值之和）最小。V1V6V5V4V3V27131791812752410第46页/共70页三、构造最小生成树方法方法一：普里姆(Prim)算法算法思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合初始令U=u0,(u0 V),TE=在所有u U,v VU的边(u,v)E中，找一条代价最小的边(u0,v0)将(u0,v0)并入集合TE，同时v0

29、并入U重复上述操作直至U=V为止，则T=(V,TE)为N的最小生成树该算法适用于边比较稠密的网第47页/共70页例例v1v6v5v4v3v26513566425v1v31v1v6v314v1v6v4v3142v1v1v6v4v3v21425v1v6v5v4v3v214253第48页/共70页方法二：克鲁斯卡尔(Kruskal)算法算法思想：设连通网N=(V,E)，令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连通分量在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边依此类推，直至T中所有

30、顶点都在同一连通分量上为止该算法适用于边比较稀疏的网例例v1v6v5v4v3v26513566425v1v6v5v4v3v212345第49页/共70页例：从顶点例：从顶点A A出发，采用普里姆出发，采用普里姆 (Prim)(Prim)算法算法求出该网络求出该网络的最小生成树。的最小生成树。475290695458ACGBDEF55532442475254ACGBDEF532442475254AGBDEF5324425254ABDEF53244254ABDE5342AB53ABE5342第50页/共70页例：例：KruskalKruskal算法最小生成树构造过程算法最小生成树构造过程 4752

31、90695458ACGBDEF55532442ACGBDEF24ACGBDEF2442ACGBDEF24424752ACGBDEF24424753ACGBDEF24424752第51页/共70页52ACGBDEF2442475354第52页/共70页7.5.1 拓扑排序(Topological Sort)有向图的应用一、问题提出：学生选修课程问题：学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业？例：例：课程代号 课程名称 先修棵C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3.C5C3,C6无C9C9C1,C9,C10程序设计基础离散数

32、学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析第53页/共70页l顶点表示课程l有向弧表示先决条件，若课程vi 是课程vj 的先决条件，则图中有弧 定义AOV网用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网。若是网中的一条弧，则vi是vj的直接前驱；vj是vi的直接后继；AOV网中不应该出现有向环，若存在，这意味着某项活动应以自己为先决条件，显然是荒谬的。C1C2C3C4C5C6C7C8C9C10C11C12第54页/共70页二、问题的解决方法拓扑排序把AOV

33、网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫检测AOV网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。拓扑排序的方法在有向图中选一个没有前驱的顶点且输出之；从图中删除该顶点和所有以它为尾的弧；重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。后一种情况说明有向图中存在环。第55页/共70页C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或或 ：C9-C10-C11-C6-C1-C12-

34、C4-C2-C3-C5-C7-C8一个一个AOVAOV网的拓扑序列不是唯一的网的拓扑序列不是唯一的第56页/共70页7.5.2 关键路径(Critical Path)一、问题提出l把工程计划表示为有向图，用顶点表示事件，弧表示活动；l每个事件表示在它之前的活动已完成，在它之后的活动可以开始。l例:设一个工程有11项活动，9个事件 事件V V1 1表示整个工程开始，是一个入度为0的点，称为源点。事件V V9 9表示整个工程结束，是一个出度为0的点，称为汇点。l问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？v9v8v7v6v4v5v3v2v1a1=6a2=4a3=5

35、a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4第57页/共70页定义AOE网(Activity On Edge)也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续的时间。通常，AOE网可用来估算工程的完成时间。路径长度路径上各活动持续时间之和关键路径路径长度最长的路径叫ve(j)表示事件Vj的最早发生时间vl(j)表示事件Vj的最迟发生时间e(i)表示活动ai的最早开始时间l(i)表示活动ai的最迟开始时间l(i)e(i)表示完成活动ai的时间余量关键活动关键路径上的活动叫，即l(i)e(i)的活动第58页/共70页二、问题分

36、析如何寻找e(i)l(i)的关键活动呢？设活动a i用弧表示，其持续时间记为：dut()则有：（1）e(i)ve(j)（2）l(i)vl(k)dut()jka iv如何求ve(j)和vl(j)？(1)从ve(1)0开始向前递推求顶点的最早发生时间(2)从vl(n)ve(n)起向后递推求顶点的最迟发生时间第59页/共70页求关键路径步骤：求最早发生时间ve(j)求最迟发生时间vl(j)求活动ai的最早开始时间e(i)求活动ai的最迟开始时间l(i)计算l(i)e(i)挑选出e(i)l(i)的弧作为关键路径。v9v8v7v6v4v5v3v2v1a2=4a3=5a5=1a6=2a9=4a1=6a4=

37、1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点 ve vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动 e l le00002266046258377077071031616014140033第60页/共70页三、算法实现v以邻接表作存储结构v从源点V1出发，令Ve1=0，按拓扑序列求各顶点的Veiv从汇点Vn出发，令Vln=Ven，按逆拓扑序列求其余各顶点的Vliv根据各顶点的Ve和Vl值，计算每条弧的ei和li，找出ei=li的关键活动第61页/共70页四、算法描述v输入顶点和弧信息，建立其邻接表v计

38、算每个顶点的入度v对其进行拓扑排序l排序过程中求顶点的Veil将得到的拓扑序列进栈v按逆拓扑序列求顶点的Vliv计算每条弧的ei和li,找出ei=li的关键活动第62页/共70页7.6 最短路径一、问题提出l用带权的有向图表示一个交通运输网，图中：顶点表示城市边表示城市间的交通联系权表示此线路的长度或沿此线路运输所花的时间或费用等l问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径最短路径。V5V1V6V4V3V2V085623013717329长度最短路径13819132120货郎担问题（旅行商问题）第63页/共70页一、从某个源点到其余各顶点的最短路径迪杰

39、斯特拉(Dijkstra)算法思想一个按路径长度递增次序产生最短路径的算法。算法思想：(1)把顶点集合V分成两组：S：已求出最短路径的顶点集合TV S：尚未确定最短路径的顶点集合(2)将T中顶点按最短路径递增的次序加入到S中，保证 从源点V0到S中各顶点的最短路径长度都不大于 从源点V0到T中任何顶点的最短路径长度；每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶点作中间 顶点的最短路径长度依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和（反证法可证）第64页/共70页求

40、最短路径的步骤初使时令 S=V0，T=其余顶点，T中顶点对应的距离值l若存在，为弧上的权值；l若不存在，为；从T中选取一个其距离值为最小的顶点W，加入S；对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值；重复上述步骤，直到S中包含所有顶点，即S=V为止。第65页/共70页终点终点从从V0到各终点的到各终点的D值和最短路径的求解过程值和最短路径的求解过程i=1i=2i=3i=4i=5V1V2V3V4V5VjS无无10(V0,V2)30(V0,V4)100(V0,V5)V2V0,V260(V0,V2,V3)50(V0,V4,V3)30(V0,V

41、4)100(V0,V5)V4V0,V2,V490(V0,V4,V5)V3V0,V2,V3,V460(V0,V4,V3,V5)V5V0,V2,V3,V4,V5Dijkstra算法例题讲解-第66页/共70页1383032V2:813-133032V1:13-13302220V3:13-192220V4:19终点 从V0到各终点D值和最短路径的求解过程V1V2V3V4V5V6Vj-2120V6:20516432085623013717329Dijkstra算法练习第67页/共70页二、每一对顶点之间的最短路径方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次。方法二：弗洛伊德(Floy

42、d)算法算法思想：逐个顶点试探法求最短路径的具体步骤初始时设置一个n阶方阵，令其对角线元素为0，若存在弧，则对应元素为权值；否则为逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值所有顶点试探完毕，算法结束第68页/共70页例：例：ACB2643110 4 116 0 23 0初始：初始：路径：路径：AB ACBA BCCA0 4 66 0 23 7 0加入加入B：路径：路径：AB ABCBA BCCA CAB0 4 116 0 23 7 0加入加入A：路径：路径：AB ACBA BCCA CAB0 4 65 0 23 7 0加入加入C：路径：路径：AB ABCBCA BCCA CAB第69页/共70页感谢您的欣赏！第70页/共70页