《【数据结构(严蔚敏)】图论.ppt》由会员分享，可在线阅读，更多相关《【数据结构(严蔚敏)】图论.ppt（77页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1第七章 图7.1 图的定义和术语图(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)2例例245136G1图G1中：V(G1)=1
2、,2,3,4,5,6 E(G1)=,例例157324G26图G2中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)3有向完全图n个顶点的有向图，最大边数是n(n-1)无向完全图n个顶点的无向图，最大边数是n(n-1)/2v 若边或弧的个数 eenlognnlogn，则称作稀疏图，否则称作稠密图。权与图的边或弧相关的数叫网带权的图叫子图如果图G(V,E)和图G(V,E),满足：v VVv EE 则称G为G的子图4假若顶点v v 和顶点w w 之间存在一条边，则称顶点v v 和w w 互为邻接点邻接点。边(v,
3、w)和顶点v 和w 相关联关联；或边；或边(v,w)依附依附于顶点于顶点v v 和w w。顶点的度v无向图中，顶点的度为与每个顶点相连的边数v有向图中，顶点的度分成入度与出度l入度：以该顶点为头的弧的数目l出度：以该顶点为尾的弧的数目5例例213213有向完全图有向完全图无向完全图无向完全图356例例245136图与子图图与子图例例245136G1顶点顶点2入度：入度：1 出度：出度：3顶点顶点4入度：入度：1 出度：出度：0例例157324G26顶点顶点5的度：的度：3顶点顶点2的度：的度：46路径路径是顶点的序列V=Vi0,Vi1,Vin，满足(Vij-1,Vij)E 或 E,(1jn)路
4、径长度沿路径边的数目或沿路径各边权值之和回路第一个顶点和最后一个顶点相同的路径叫简单路径序列中顶点不重复出现的路径叫简单回路除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫7例例157324G26例例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，18连通在无向图G中，如果从顶点V到顶点W有一条路径，则说V和W是连通的连通图图中任意两个顶点都是连通的叫连通分量无向图
5、中的极大连通子图叫强连通图有向图中，如果对每一对Vi,VjV,ViVj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是9连通图连通图例例245136强连通图强连通图非连通图非连通图连通分量连通分量例例245136ABECF10 假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树生成树。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生生成森林成森林。BACDFE117.2 图的存储结构多重链表例例G12413例例15324G2V1V2 V4 V3 V1 V2 V4 V5 V312图的存储表示图的存储表
6、示一、一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示13 邻接矩阵邻接矩阵表示顶点间相联关系的矩阵表示顶点间相联关系的矩阵v定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵例例G12413例例15324G214特点：l无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2l有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为nl无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和或第i列元素之和l有向图中，u顶点Vi的出度是A中第i行元素之和u顶点Vi的入度
7、是A中第i列元素之和15#define MAX_VERTEX_NUM 20 /最大顶点个数typedef struct ArcCell /弧的定义弧的定义 VRType adj;/VRType是顶点关系类型。/对无权图，用1或0表示相邻否；/对带权图，则为权值类型。InfoType *info;/该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;16Typedef enumDG,DN,UDG,UDN GraphKind /有向图，有向网，无向图，无向网typedef struct /图的定义图的定义 VertexType vexs
8、MAX_VERTEX_NUM;/顶点信息 AdjMatrix arcs;/弧的信息，邻接矩阵 int vexnum,arcnum;/顶点数，弧数 GraphKind kind;/图的种类标志 MGraph;17例例1452375318642网的邻接矩阵可定义为：18 邻接表邻接表v实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）头结点：typedef struct Vnode VertexType data;/存放顶点信息 ArcNode *firstarc;/指示第一个邻接点Vnode,AdjListMAX_VERTEX_NUM;da
9、ta firstarc#define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex;/邻接点域，存放与Vi邻接的点在表头数组中 的位置 struct ArcNode *next;/链域，指示下一条边或弧 InfoType *info;ArcNode;/表结点：adjvex nextinfo19例例G1bdac例例aecbdG21234acdbdatafirstarc 3 2 4 1adjvex next1234acdbdata firstarc 4 2 1 2adjvexnext5e 4 3 5 1 5 3 2 320v特点特点l无向图
10、中顶点无向图中顶点ViVi的度为第的度为第i i个单链表中的结点数个单链表中的结点数l有向图中有向图中u顶点顶点ViVi的出度为第的出度为第i i个单链表中的结点个数个单链表中的结点个数u顶点顶点ViVi的入度为整个的入度为整个单链表中邻接点域值是单链表中邻接点域值是i i的的结点个数结点个数例例G1bdac1234acdbdatafirstarc 4 1 1 3adjvexnext逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表21有向图的十字链表表示法有向图的十字链表表示法顶点结点顶点结点：typedef struct VexNode VertexType data;/存与顶点有关信
11、息存与顶点有关信息 ArcBox *firstin；/指向以该顶点为弧头的第一个弧结点指向以该顶点为弧头的第一个弧结点 ArcBox *firstout;/指向以该顶点为弧尾的第一个弧结点指向以该顶点为弧尾的第一个弧结点VexNode;data firstin firstout#define MAX_VERTEX_NUM 20 弧结点弧结点：typedef struct ArcBox int tailvex,headvex;/弧尾、弧头在表头数组中位置弧尾、弧头在表头数组中位置 struct ArcBox *hlink；/指向弧头相同的下一条弧指向弧头相同的下一条弧 struct ArcBox
12、 *tlink;/指向弧尾相同的下一条弧指向弧尾相同的下一条弧 infoType *info;ArcBox;tailvex headvex hlink tlink info22例例bdacab cd1234 1 3 1 2 3 4 3 1 4 3 4 2 4 123 无向图的邻接多重表表示法无向图的邻接多重表表示法顶点结点顶点结点：typedef struct VexBox VertexType data;/存与顶点有关的信息存与顶点有关的信息 EBox *firstedge;/指向第一条依附于该顶点的边指向第一条依附于该顶点的边VexBox;data firstedge边结点边结点：type
13、def struct EBox visitif mark;/标志域标志域，标记该边是否被搜索过，标记该边是否被搜索过 int ivex,jvex;/该边依附的两个顶点在表头数组中位置该边依附的两个顶点在表头数组中位置 struct EBox*ilink,*jlink;/分别指向依附于分别指向依附于ivex和和jvex的的 下一条边下一条边 infotype *info;EBox;mark ivex ilink jvex jlinkinfo#define MAX_VERTEX_NUM 20 24例例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 2257.3 图的遍历
14、深度优先遍历(DFS)v方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。V1V2V4V5V3V7V6V8例例深度遍历：V1 V2 V4 V8 V5 V3 V6 V726V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V3 V6 V7 V527Vw1SG1SG2SG3W1
15、、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。访问顶点 V：for(W1、W2、W3)若该邻接点W未被访问，则从它出发进行深度优先搜索遍历。w2w3w228从上页的图解可见从上页的图解可见:1.从深度优先搜索遍历连通图的过程类似于从深度优先搜索遍历连通图的过程类似于树的先根遍历；树的先根遍历；解决的办法是：为每个顶点设立一个解决的办法是：为每个顶点设立一个“访问访问标志标志 visitedw”。2.如何判别如何判别V的邻接点是否被访问？的邻接点是否被访问？29void DFS(Graph G,int v)/从顶点从顶点v出发，出发，深度优先
16、搜索遍历连通图深度优先搜索遍历连通图 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/DFS30 首先将图中每个顶点的访问标志设为首先将图中每个顶点的访问标志设为 FALSE,之后搜索图中每个顶点，如果未被访问，则以该之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。续检查下一顶点。非连通图的
17、深度优先搜索遍历非连通图的深度优先搜索遍历31void DFSTraverse(Graph G,Status(*Visit)(int v)/对图对图 G 作深度优先遍历。作深度优先遍历。VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化 for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);/对尚未访问的顶点调用DFS32F F F F F F F F FT T T T T T T TTach d kfe bg访问标志访问标志:访问次序访问次序:例如例如:0 1 2 3 4 5 6 7 8
18、abchdekfgachkfedbg33广度优先遍历(BFS)v方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。V1V2V4V5V3V7V6V8例例广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V834V1V2V4V5V3V7V6V8例例广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例例广度遍历：V1
19、 V2 V3 V4 V6 V7 V8 V535 void BFSTraverse(Graph G,Status(*Visit)(int v)/按广度优先非递归遍历图按广度优先非递归遍历图G，使用辅助队列，使用辅助队列Q和访和访问标志数组问标志数组visit for(v=0;vG.vexnum;+v)visitedv=FALSE;/初始化访问标志 InitQueue(Q);/置空的辅助队列Q for(v=0;vG.vexnum;+v)if(!visitedv)/v 尚未访问 /BFSTraverse 36visitedu=TRUE;Visit(u);/访问uEnQueue(Q,v);/v入队列w
20、hile(!QueueEmpty(Q)DeQueue(Q,u);/队头元素出队并置为u for(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;Visit(w);EnQueue(Q,w);/访问的顶点w入队列 /if/while37例1423512341342datafirstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍历序列：10 1 2 3 4 54fr遍历序列：1 40 1 2 3 4 54 3fr遍历序列：1 4 338例1423
21、512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3 4 54 3 2fr遍历序列：1 4 3 20 1 2 3 4 5 3 2fr遍历序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍历序列：1 4 3 2 5390 1 2 3 4 5 2 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 fr遍历序列：1 4 3 2 5例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5
22、1 1 4 3 2 2407.4 生成树生成树v定义：所有顶点均由边连接在一起，但不存在回路的图叫v深度优先生成树与广度优先生成树v生成森林：非连通图每个连通分量的生成树一起组成非连通图的v说明l一个图可以有许多棵不同的生成树l所有生成树具有以下共同特点：u生成树的顶点个数与图的顶点个数相同u生成树是图的极小连通子图u一个有n个顶点的连通图的生成树有n-1条边u生成树中任意两个顶点间的路径是唯一的u在生成树中再加一条边必然形成回路l含n个顶点n-1条边的图不一定是生成树GHKI41V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4
23、V5V3V7V6V8深度优先生成树深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V842例例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林深度优先生成森林43最小生成树MST(Minimum cost Spanning Tree)v问题提出要在要在n个城市间建立通信联络网，个城市间建立通信联络网，顶点顶点表示城市表示城市权权城市间建立通信线路所需花费代价城市间建立通信线路所需花费代价希望找到一棵生成树，它的每条边上的权值
24、之和（即建立希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小该通信网所需花费的总代价）最小最小代价生成树最小代价生成树v问题分析1654327131791812752410n个城市间，最多可设置个城市间，最多可设置n(n-1)/2条线路条线路n个城市间建立通信网，只需个城市间建立通信网，只需n-1条线路条线路问题转化为：如何在可能的线路中选择问题转化为：如何在可能的线路中选择n-1条，能把条，能把 所有城市（顶点）均连起来，且总耗费所有城市（顶点）均连起来，且总耗费 （各边权值之和）最小（各边权值之和）最小44v构造最小生成树方法构造最小生成树方法l MST性质
25、：假设性质：假设N=(V,E)是一个连通图，是一个连通图，U是顶是顶点集合点集合V的一个非空子集。若的一个非空子集。若(u,v)是一条具有最小是一条具有最小权值（代价）的边，其中权值（代价）的边，其中u u U,vU,v V V-U-U，则必存在，则必存在一棵包含边一棵包含边(u,v)的最小生成树。的最小生成树。l反证法：假设网反证法：假设网N N的任何一棵最小生成树都不包含的任何一棵最小生成树都不包含(u,vu,v)。设。设T T是连通图上的一棵最小生成树，当将是连通图上的一棵最小生成树，当将边边(u,v)加入到加入到T中时，则中时，则T中必存在一条包含中必存在一条包含(u,v)的回路。另一
26、方面，由于的回路。另一方面，由于T是生成树，则在是生成树，则在T上必上必存在另一条边存在另一条边(u,v)，其中，其中u u U,vU,v V V-U-U，且，且u u和和u u、v v和和v v之间存在通路。删除边之间存在通路。删除边(u,v)，得，得到另一棵生成树到另一棵生成树T。因为。因为(u,v)的代价低于的代价低于(u,v)，则则T是包含边是包含边(u,v)的最小生成树。与假设矛盾，的最小生成树。与假设矛盾，得证。得证。45l方法一：普里姆(Prim)算法u算法思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合Y 初始令U=u0,(u0V),TE=Y 在所有uU,vV-U
27、的边(u,v)E中，找一条代价最小的边(u0,v0)Y 将(u0,v0)并入集合TE，同时v0并入UY重复上述操作直至U=V为止，则T=(V,TE)为N的最小生成树u算法实现：图用邻接矩阵表示u算法描述 P175 算法7.9u算法评价：T(n)=O(n)46例例165432651356642513116314164314211643214251654321425347abcdegf例如例如:195141827168213ae12dcbgf7148531621所得生成树权值和=14+8+3+5+16+21=6748 设置一个辅助数组，对当前设置一个辅助数组，对当前VU集中集中的每个顶点，记录和顶
28、点集的每个顶点，记录和顶点集U中顶点相连中顶点相连接的代价最小的边：接的代价最小的边：struct VertexType adjvex;/U集中的顶点序号 VRType lowcost;/边的权值 closedgeMAX_VERTEX_NUM;49abcdegf195141827168213ae12dcb7aaa19141814例如例如:e12ee8168d3dd7213c5 550void MiniSpanTree_P(MGraph G,VertexType u)/用普里姆算法从顶点u出发构造网G的最小生成树 k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助
29、数组初始化 if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;/初始，Uu for(i=0;iG.vexnum;+i)继续向生成树上添加顶点继续向生成树上添加顶点;51 k=minimum(closedge);/求出加入生成树的下一个顶点(k)printf(closedgek.adjvex,G.vexsk);/输出生成树上一条边 closedgek.lowcost=0;/第k顶点并入U集 for(j=0;jG.vexnum;+j)/修改其它顶点的最小边 if(G.arcskj.adj closedgej.lowcost)closedgej
30、=G.vexsk,G.arcskj.adj;52l 方法二：克鲁斯卡尔(Kruskal)算法u 算法思想：设连通网N=(V,E)，令最小生成树Y 初始状态为只有n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连通分量Y 在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边Y 依此类推，直至T中所有顶点都在同一连通分量上为止。例例165432651356642516543212345537.5 拓扑排序(Topological Sort)问题提出：学生选修课程问题顶点表示课程有向弧表示先决条件，若课程i是课程j的先决条
31、件，则图中有弧学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业拓扑排序定义vAOV网用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网。l若是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继；lAOV网中不允许有回路，这意味着某项活动以自己为先决条件；54例例课程代号课程代号 课程名称课程名称 先修棵先修棵C1C2C3C4C5C6C7C8C9C10C11C12无无C1C1,C2C1C3,C4C11C3.C5C3,C6无无C9C9C1,C9,C10程序设计基础程序设计基础离散数学离散数学数据结
32、构数据结构汇编语言汇编语言语言的设计和分析语言的设计和分析计算机原理计算机原理编译原理编译原理操作系统操作系统高等数学高等数学线性代数线性代数普通物理普通物理数值分析数值分析C1C2C3C4C5C6C7C8C9C10C11C1255v拓扑排序把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫l检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环拓扑排序的方法v在有向图中选一个没有前驱的顶点且输出之v从图中删除该顶点和所有以它为尾的弧v重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为
33、止56C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8一个一个AOV网的拓扑序列不是唯一的网的拓扑序列不是唯一的57C1C2C3C4C5C6C7C8C9C10C11C12拓扑排序的分析过程：58C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1（1）C3C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2（2）59C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3（3）
34、C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3-C4（4）60C6C8C10C11C12拓扑序列：C1-C2-C3-C4-C5-C7-C9C6C8C11C12拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10（8）C6C7C8C9C10C11C12拓扑序列：C1-C2-C3-C4-C5（5）C6C8C9C10C11C12拓扑序列：C1-C2-C3-C4-C5-C7（6）61C6C8C12拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11（9）C8C12拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6（10）C8拓扑序列：C
35、1-C2-C3-C4-C5-C7-C9 -C10-C11-C6-C12（11）拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6-C12-C8（12）62拓扑排序的算法（P182 算法7.12）Status Status TopologicalSort(ALGraphTopologicalSort(ALGraph G)G)/有向图有向图G G采用邻接表存储结构，若采用邻接表存储结构，若G G无回路，则输出无回路，则输出G G的顶点的一个的顶点的一个拓扑序列并返回拓扑序列并返回OKOK，否则，否则ERRORERROR FindInDegree(G,indegreeFind
36、InDegree(G,indegree);/);/对各顶点求入度对各顶点求入度indegree0.vernum-1indegree0.vernum-1 InitStack(SInitStack(S););for(ifor(i=0;i=0;i=p-nextarcnextarc)k=p-k=p-adjvexadjvex;/;/对对i i号顶点的每个邻接点的入度减号顶点的每个邻接点的入度减1 1 if(!(-if(!(-indegreekindegreek)Push(S,kPush(S,k);/for);/for /while /while if(countif(count G.vexnumG.ve
37、xnum)return ERROR;/)return ERROR;/该图有回路该图有回路 else return OK;else return OK;/TopologicalSortTopologicalSort637.5.2 关键路径把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始。例 设一个工程有11项活动，9个事件事件 V1表示整个工程开始事件V9表示整个工程结束问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4
38、a10=2a11=4问题提出问题提出64定义vAOE网(Activity On Edge)也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间v路径长度路径上各活动持续时间之和v关键路径路径长度最长的路径叫vVe(j)表示事件Vj的最早发生时间vVl(j)表示事件Vj的最迟发生时间ve(i)表示活动ai的最早开始时间vl(i)表示活动ai的最迟开始时间vl(i)-e(i)表示完成活动ai的时间余量v关键活动关键路径上的活动叫，即l(i)=e(i)的活动65问题分析问题分析v 如何找如何找e(ie(i)=)=l(il(i)的关键活动？的关键活动？设
39、活动设活动ai用弧用弧表示，其持续时间记为：表示，其持续时间记为：dut()则有：（则有：（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut()jkaiv 如何求如何求Ve(jVe(j)和和Vl(jVl(j)？(1)从从Ve(1)=0开始向前递推开始向前递推(2)从从Vl(n)=Ve(n)开始向后递推开始向后递推66求关键路径步骤v求Ve(i)v求Vl(j)v求e(i)v求l(i)v计算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点顶点 Ve Vl06457716
40、14180668710161418a1a2a3a4a5a6a7a8a9a10a11活动活动 e l l-e 0000226604625837707707103161601414003367V1V2V3V4V5V6a1=3a2=2a3=2a4=3a5=4a6=3a7=2a8=1V1V2V3V4V5V6顶点顶点 Ve Vl032668042678a1a2a3a4a5a6a7a8活动活动 e l l-e 011000341220253660671341（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut()68求关键路径算法 参见P185 算法7.13，7.14算法7.13Status St
41、atus TopologicalOrder(ALGraphTopologicalOrder(ALGraph G,Stack&T)G,Stack&T)FindInDegree(G,indegreeFindInDegree(G,indegree););InitStack(SInitStack(S);count=0;ve0.vexnum-1=0;);count=0;ve0.vexnum-1=0;while(!StackEmpty(Swhile(!StackEmpty(S)Pop(S,jPop(S,j););Push(T,jPush(T,j);+count;/j);+count;/j号入栈号入栈T T
42、 for(pfor(p=G.verticesj.firstarc;p;pG.verticesj.firstarc;p;p=p-=p-nextarcnextarc)k=p-k=p-adjvexadjvex;if(-if(-indegreekindegreek=0)=0)Push(S,kPush(S,k););if(vejif(vej+*(p-info)+*(p-info)vek)vekvek)vek=vejvej+*(p-info);+*(p-info);/for /for/while/whileif(countif(count nextarc)k=p-adjvex;dut=*(p-info);
43、if(vlk-dutvlj)vlj=vlk-dut;/forfor(j=0;jnextarc)k=p-adjvex;dut=*(p-info);ee=vej;el=vlk-dut;tag=(ee=ve)?*:;printf(j,k,dut,ee,el,tag);/输出关键活动 /CriticalPath707.7 最短路径用带权的有向图表示一个交通运输网，图中：用带权的有向图表示一个交通运输网，图中：顶点顶点表示城市表示城市边边表示城市间的交通联系表示城市间的交通联系权权表示此线路的长度或沿此线路运输所花的时间或费用等表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边
44、到达另一顶点所经过的路径中，问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径各边上权值之和最小的一条路径最短路径最短路径 从某个源点到其余各顶点的最短路径51643208562301371732913长度长度最短路径最短路径813192120问题提出71v 迪杰斯特拉(Dijkstra)算法思想按路径长度递增次序产生最短路径算法：按路径长度递增次序产生最短路径算法：把把V分成两组：分成两组：（1）S：已求出最短路径的顶点的集合已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合尚未确定最短路径的顶点集合将将T中顶点按最短路径递增的次序加入到
45、中顶点按最短路径递增的次序加入到S中，中，保证：（保证：（1）从源点）从源点V0到到S中各顶点的最短路径长度都不大于中各顶点的最短路径长度都不大于 从从V0到到T中任何顶点的最短路径长度中任何顶点的最短路径长度 （2）每个顶点对应一个距离值）每个顶点对应一个距离值 S中顶点：从中顶点：从V0到此顶点的最短路径长度到此顶点的最短路径长度 T中顶点：从中顶点：从V0到此顶点的只包括到此顶点的只包括S中顶点作中间中顶点作中间 顶点的最短路径长度顶点的最短路径长度依据：可以证明依据：可以证明V0到到T中顶点中顶点Vk的最短路径，或是从的最短路径，或是从V0到到Vk的的 直接路径的权值；或是从直接路径的
46、权值；或是从V0经经S中顶点到中顶点到Vk的路径权值之和。的路径权值之和。（反证法可证）（反证法可证）72v求最短路径步骤l初使时令 S=V0,T=其余顶点，T中顶点对应的距离值u若存在，为弧上的权值；u若不存在，为；l从T中选取一个其距离值为最小的顶点W，加入Sl对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值l重复上述步骤，直到S中包含所有顶点，即S=V为止73138 30 32V2:813-1330 32V1:13-13302220V3:13-192220V4:19终点终点 从从V0到各终点的最短路径及其长度到各终点的最短路径及其长度
47、V1V2V3V4V5V6Vj-2120V6:20516432085623013717329示例一示例一74 10 30100V2:10-6030100V4:30-50-90V3:50-60V5:60终点终点 从从V0到各终点的最短路径及其长度到各终点的最短路径及其长度V1V2V3V4V5VjS-V1V0V1V5V4V2V31003060510501020示例二示例二75每一对顶点之间的最短路径v方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次 T(n)=O(n)v方法二：弗洛伊德(Floyd)算法l算法思想：逐个顶点试探法l求最短路径步骤u初始时设置一个n阶方阵，令其对角线元素为
48、0，若存在弧，则对应元素为权值；否则为u逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值u所有顶点试探完毕，算法结束76例例ACB2643110 4 116 0 23 0初始：初始：路径：路径：AB ACBA BCCA0 4 66 0 23 7 0加入加入V2：路径：路径：AB ABCBA BCCA CAB0 4 116 0 23 7 0加入加入V1：路径：路径：AB ACBA BCCA CAB0 4 65 0 23 7 0加入加入V3：路径：路径：AB ABCBCA BCCA CAB77l算法实现算法实现u图用邻接矩阵存储图用邻接矩阵存储ulength存放最短路径长度存放最短路径长度upathij是从是从Vi到到Vj的最短路径上的最短路径上Vj前一顶点序号前一顶点序号l算法描述算法描述例例132264311初始：初始：0 4 116 0 23 0length=0 1 12 0 23 0 0path=加入加入V1：0 4 116 0 23 7 0length=0 1 12 0 23 1 0path=加入加入V2：0 4 66 0 23 7 0length=0 1 22 0 23 1 0path=加入加入V3：0 4 65 0 23 7 0length=0 1 23 0 23 1 0path=l算法分析：算法分析：T(n)=O(n)