1、第7章 图 图是一种非线性结构,结构较复杂,数据元素之间的关系是任意的。它可应用到电子线路分析、系统工程、人工智能等。7.1 图的定义和术语图的抽象数据类型:P156157图的定义v图(Graph)图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对l 零图：只有顶点没有边，E（G）为空集v有向图有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头v无向图无向图G是由两个集合V(G)和
2、E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v)例245136G1图G1中：V(G1)=1,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)图的基本术语v完全图：n个顶点的图中，每个顶点与其它n-1个顶点都有边v有向完全图n个顶点的有向图最大边数是n(n-1)v无向完全图n个顶点的无向图最大边数是n(n-1)/2v权与图的边或弧相关的数叫v网带权的图
3、叫v子图如果图G(V,E)和图G(V,E),满足：l VVl EE 则称G为G的子图v顶点的度l 无向图中，顶点的度为与每个顶点相连的边数l 有向图中，顶点的度分成入度与出度u入度：以该顶点为头的弧的数目u出度：以该顶点为尾的弧的数目v路径路径是顶点的序列V=Vi0,Vi1,Vin，满足(Vij-1,Vij)E 或 E,(1jn)v路径长度沿路径边的数目或沿路径各边权值之和v回路第一个顶点和最后一个顶点相同的路径叫v简单路径序列中顶点不重复出现的路径叫v简单回路除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫v连通从顶点V到顶点W有一条路径，则说V和W是连通的v连通图图中任意两个顶点
4、都是连通的叫v连通分量非连通图的每一个连通部分叫 (P159 图7.3)v强连通图有向图中，如果对每一对Vi,VjV,ViVj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是 P159图7.4中V2是自身对自身的强连通分量例213213有向完全图无向完全图356例245136图与子图例245136G1顶点2入度：1 出度：3顶点4入度：1 出度：0例157324G26顶点5的度：3顶点2的度：4例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路径
5、长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1连通图例245136强连通图356例非连通图连通分量例245136v有向树:一个有向图若只有一个顶点的入度为0,其余顶点的入度都为1,则该图称为一棵有向树.v生成森林:由若干棵有向树组成,含图中全部顶点,这些顶点构成若干棵互不相交的有向树的弧.P160图7.67.2 图的存储结构多重链表(P160)例G12413例15324G2V1V2 V4 V3 V1 V2 V4 V5 V3数组表示法表示顶点间相联关系的邻接矩阵v定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵，其
6、它0E(G)v,v或)v,(v若1,jijijiA例G12413例15324G200110001011101010101010100001100000000110v特点：l无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2l有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为nl无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行(或第i列)元素之和l有向图中，u顶点Vi的出度OD(vi)是A中第i行元素之和u顶点Vi的入度ID(vi)是A中第i列元素之和l网络的邻接矩阵可定义为：，其它或0E(G)v,v或)v,(v若,jijiijjiA06183602401
7、20078400530750例1452375318642P162图7.9是有向网的邻接矩阵关联矩阵表示顶点与边的关联关系的矩阵v定义：设G=(V,E)是有n1个顶点，e0条边的图，G的关联矩阵A是具有以下性质的ne阶矩阵为头边相连，且顶点与边不相连顶点与为尾边相连，且顶点与有向图：ijijiijijiA,1,0,1,边不相连顶点与，边相连顶点与，无向图：jijijiA01,11000110000110114321例G124131234例15324G2123456110000000110011100101001000011432156例BDAC123456ABCD4321561010111100
8、00011100000111v特点特点l关联矩阵每列只有两个非零元素关联矩阵每列只有两个非零元素，是稀疏矩阵；，是稀疏矩阵；n越大，零越大，零元素比率越大元素比率越大l无向图中顶点无向图中顶点Vi的度的度TD(Vi)是关联矩阵是关联矩阵A中第中第i行元素之和行元素之和l有向图中，有向图中，u顶点顶点Vi的出度是的出度是A中第中第i行中行中“1”的个数的个数u顶点顶点Vi的入度是的入度是A中第中第i行中行中“-1”的个数的个数邻接表v实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边v有向图中指以Vi为尾的弧,即顶点vi的出度typedef struct node i
9、nt adjvex;/邻接点域，存放与Vi邻接的点在表头数组中的位置 struct node *next;/链域，指示下一条边或弧JD;adjvex next表头结点：typedef struct tnode int vexdata;/存放顶点信息 struct node *firstarc;/指示第一个邻接点TD;TD gaM;/ga0不用vexdata firstarc例G1bdac例aecbdG21234acdbvexdata firstarc 3 2 4 1adjvex next1234acdbvexdata firstarc 4 2 1 2adjvex next5e 4 3 5 1
10、5 3 2 3v特点l 无向图中顶点Vi的度为第i个单链表中的结点数l 有向图中u顶点Vi的出度为第i个单链表中的结点个数u顶点Vi的入度为整个单链表中邻接点域值是i的结点个数l 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表逆邻接表:例G1bdac1234acdbvexdata firstarc 4 1 1 3adjvex next有向图的十字链表表示法弧结点：typedef struct arcnode int tailvex,headvex;/弧尾、弧头在表头数组中位置 struct arcnode *hlink；/指向弧头相同的下一条弧 struct arcnode *tlin
11、k;/指向弧尾相同的下一条弧AD;tailvex headvex hlink tlink顶点结点：typedef struct dnode int data;/存与顶点有关信息 struct arcnode *firstin；/指向以该顶点为弧头的第一个弧结点 struct arcnode *firstout;/指向以该顶点为弧尾的第一个弧结点DD;DD gM;/g0不用data firstin firstout例bdacab cd1234 1 3 1 2 3 4 3 1 4 3 4 2 4 1蓝色邻接表，绿色第2个域值相同的结点链无向图的邻接多重表表示法顶点结点：typedef struct
12、 dnode int data;/存与顶点有关的信息 struct node *firstedge;/指向第一条依附于该顶点的边DD;DD gaM;/ga0不用data firstedge边结点：typedef struct node int mark;/标志域 int ivex,jvex;/该边依附的两个顶点在表头数组中位置 struct node *ilink,*jlink;/分别指向依附于ivex和jvex的下一条边JD;mark ivex ilink jvex jlink例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 27.3 图的遍历(P167)深度优先
13、遍历(DFS)v方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1 V2 V4 V8 V5 V6 V3 V7 或 V1 V2 V4 V8 V6 V3 V7 V5 或深度遍历：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5
14、V3V7V6V8例深度遍历：V1 V2 V4 V8 V3 V6 V7 V5v深度优先遍历算法l递归算法开始访问V0,置标志求V0邻接点有邻接点w求下一邻接点wV0W访问过结束NYNYDFS开始标志数组初始化Vi=1Vi访问过DFSVi=Vi+1Vi=Vexnums结束NNYYCh7_1.cV1V2V4V5V3V7V6V8例深度遍历：V112341342vexdata firstarc 2 7 8 3adjvex next55 6 4 1 5 1 2 8 2678678 7 3 6 3 5 4V3 V7 V6 V2 V5 V8 V4V1V2V4V5V3V7V6V8例12341342vexdata
15、 firstarc 2 7 8 3adjvex next55 6 4 8 2678678 7深度遍历：V1V3 V7 V6 V2 V4 V8 V5广度优先遍历(BFS)v方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6
16、V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V6 V7 V8 V5 （V5逆向最后访问）v广度优先遍历算法开始标志数组初始化Vi=1Vi访问过BFSVi=Vi+1Vi=Vexnums结束NNYYCh7_2.c开始访问V0,置标志求V邻接点ww存在吗V下一邻接点ww访问过结束NYNYBFS初始化队列V0入队队列空吗队头V出队访问w,置标志w入队NaaY例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1
17、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 3例1423512341342vexdata 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 5邻接表：0 1 2 3 4 5 2 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 5fr遍历序列：1 4 3
18、 2 50 1 2 3 4 5 fr遍历序列：1 4 3 2 5例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 27.4 图的连通性问题生成树v定义：所有顶点均由边连接在一起，但不存在回路的图叫v深度优先生成树与广度优先生成树v生成森林：非连通图每个连通分量的生成树组成的非连通图的v说明l一个图可以有许多棵不同的生成树l所有生成树具有以下共同特点：u生成树的顶点个数与图的顶点个数相同u生成树是图的极小连通子图u一个有n个顶点的连通图的生成树有n-1条边u生成树中任意两个顶点间的路径是唯一的u在生成树中再加一条边
19、必然形成回路l含n个顶点n-1条边的图不一定是生成树无向图的连通分量和生成树v连通图的生成树v非连通图的生成森林V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8(无向图)连通图的生成树:例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林最小生成树v问题提出要在n个城市间建立通信联络网，顶点表示城市权城市间建立通信线路所需花费
20、代价希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小最小代价生成树v问题分析1654327131791812752410n个城市间，最多可设置n(n-1)/2条线路n个城市间建立通信网，只需n-1条线路问题转化为：如何在可能的线路中选择n-1条，能把 所有城市（顶点）均连起来，且总耗费 （各边权值之和）最小v构造最小生成树方法l方法一：普里姆(Prim)算法u算法思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合Y初始令U=u0,(u0V),TE=Y 在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0)Y 将(u0,v0)并入集合
21、TE，同时v0并入UY 重复上述操作直至U=V为止，则T=(V,TE)为N的最小生成树u算法实现：图用邻接矩阵表示u算法描述u算法评价：T(n)=O(n)例16543265135664251311631416431421164321425165432142533到2和5中,到2最短1062460632055465051350651601 2 3 4 5 61 2 3 4 5 61-21-41-1例16543265135664251-51-3165432651356642516543214253以顶点6为起始点l方法二：克鲁斯卡尔(Kruskal)算法u算法思想：设连通网N=(V,E)，令最小生
22、成树Y初始状态为只有n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连通分量Y 在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边Y 依此类推，直至T中所有顶点都在同一连通分量上为止例165432651356642516543212345（0）用顶点数组和边数组存放顶点和边信息（1）初始时，令每个顶点的jihe互不相同；每个边的flag为0（2）选出权值最小且flag为0的边（3）若该边依附的两个顶点的jihe 值不同，即非连通，则令 该边的flag=1,选中该边；再令该边依附的两顶点的jihe 以及两集合中所有顶
23、点的jihe 相同 若该边依附的两个顶点的jihe 值相同，即连通，则令该 边的flag=2,即舍去该边（4）重复上述步骤，直到选出n-1条边为止 顶点结点：typedef struct int data;/顶点信息 int jihe;VEX;边结点：typedef struct int vexh,vext;/边依附的两顶点 int weight;/边的权值 int flag;/标志域EDGE;u算法实现：例1654326513566425Ch6_30.cu算法描述：datajihe124536124536124536vexhweight112213233544vextflag61最小5355
24、00000001342567893345566664260000111114211122222165432123457.5有向无环图及其应用 一个无环的有向图称做有向无环图（directed acycline praph）。简称DAG图有向无环图应用：描述公共子式表达式；工程；系统的有效工具。关于工程：计划、施工过程、生产流程、程序流程等都可看成一个工程。v活动(子工程)；一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动，这些活动完成时，整个工程也就完成了。v主要的两个方面:l工程的可行性;l估算整个工程完成所必须的最短时间(拓扑排序、求关键路径)有向树、DAG图和有向图示意 P1
25、79利用有向无环图表达含公共子式的表达式v利用有向无环图，可将相同子式共享，以减少信息的重复表达。v无向图中，若DFS过程中遇到回边，则必定存在环。v有向图中，DFS的回边可能是指向DFS生成森林的另一棵生成树上顶点的弧。v有向图中，DFS中v到u路径，但又出现u到v的回边，则必定存在包含v和u的环。7.5.1 拓扑排序问题提出：学生选修课程问题顶点表示课程有向弧表示先决条件，若课程i是课程j的先决条件，则图中有弧学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业拓扑排序 定义vAOV网用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vert
26、ex network)，简称AOV网l若是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继,并且具有传递性。lAOV网中不允许有回路，这意味着某项活动以自己为先决条件（此工程是无法完成的）7.5.1 拓扑排序拓扑排序:(数学中)由某个集合上的一个偏序得到该集合上的一个全序,这个操作过程叫拓扑排序。v偏序:直观地说指集合中仅有部分成员之间可比较。v全序:指集合中全体成员之间均可比较。v表示偏序和全序的有向图P180图7.25v拓扑排序把AOV网络中各顶点按照它们相互之间的优先关系排列成一个有序序列的过程叫l检测AOV网中是否存在环（回路）方法（拓扑排序）：对有向图构造其顶点的拓扑有序序列
27、，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环拓扑排序的方法v在有向图中选一个没有前驱的顶点且输出之v从图中删除该顶点和所有以它为尾的弧v重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止例课程代号 课程名称 先修棵C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3.C5C3,C6无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析C1C2C3C4C5C6C7C8C9C10C11C12C1C2C3C4C5C6C7C8C9C10C1
28、1C12拓扑序列：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网的拓扑序列不是唯一的C1C2C3C4C5C6C7C8C9C10C11C12C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1（1）C3C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2（2）C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3（3）C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3-C4（4）C6C8C10C11C12拓扑序列：C1-C2
29、-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）C6C8C12拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11（9）C8C12拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6（10）C8拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6-C12（11）拓扑序列：C1-C2-C3-C4-C5-C7-C9
30、-C10-C11-C6-C12-C8（12）算法实现（栈）v以邻接表作存储结构v把邻接表中所有入度为0的顶点进栈v栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈v重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕邻接表结点：typedef struct node int vex;/顶点域 struct node *next;/链域JD;表头结点：typedef struct tnode int in;/入度域 struct node *link;/链域TD;TD gM;/g0不用32104算法描
31、述例1234560122inlink 5 5 4 3vex next3 2 5 2 40123456Ch7_40.ctop16toptop0122inlink 5 5 4 3vex next3 2 5 2 40123456输出序列：63210416toptop0122inlink 5 5 4 3vex next3 2 5 2 40123456输出序列：6321041topp0122inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6321041topp0122inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6321041
32、topp0112inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6321041topp0112inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6321041topp=NULL0112inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 1321041toptop0112inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104topp0102inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 13210
33、4topp40102inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104p4top0102inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104p4top0002inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104p4top30002inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104p4top30002inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132
34、104p4top30001inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104p4top30001inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104p=NULL4top30001inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 1 3321044top30001inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 1 3321044topp0001inlink 5 5 4 3vex next1 2 5 2 401234
35、56输出序列：6 1 3321044topp0001inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：6 1 3321044topp0000inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：6 1 3321044topp20000inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：6 1 3321044topp20000inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：6 1 3321044top2p=NULL0000inlink 5 5 4 3vex
36、next1 2 5 2 40123456输出序列：6 1 3 2321044top2p=NULL0000inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：6 1 3 2321044topp=NULL0000inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：6 1 3 2 4321044top0000inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：6 1 3 2 432104topp0000inlink 5 5 4 3vex next0 2 5 2 40123456输出序列：6 1 3
37、2 432104topp50000inlink 5 5 4 3vex next0 2 5 2 40123456输出序列：6 1 3 2 432104topp=NULL50000inlink 5 5 4 3vex next0 2 5 2 40123456输出序列：6 1 3 2 4 532104top50000inlink 5 5 4 3vex next0 2 5 2 40123456输出序列：6 1 3 2 4 532104topp=NULL算法分析建邻接表：T(n)=O(e)搜索入度为0的顶点的时间：T(n)=O(n)拓扑排序：T(n)=O(n+e)Ch7_4.c7.5.2 关键路径问题提出
38、把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始例 设一个工程有11项活动，9个事件事件 V1表示整个工程开始事件V9表示整个工程结束问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4定义vAOE网(Activity On Edge)也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间v路径长度路径上各活动持续时间之和v关键路径路径长度最长的路径叫vV
39、e(j)表示事件Vj的最早发生时间vVl(j)表示事件Vj的最迟发生时间ve(i)表示活动ai的最早开始时间vl(i)表示活动ai的最迟开始时间vl(i)-e(i)表示完成活动ai的时间余量v关键活动关键路径上的活动叫，即l(i)=e(i)的活动问题分析v如何找e(i)=l(i)的关键活动？设活动ai用弧表示，其持续时间记为：dut()则有：（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut()jkaiv如何求Ve(j)和Vl(j)？(1)从Ve(1)=0开始向前递推为头的弧的集合是所有以其中jTnjTjijidutiVeMaxjVei2,),()()(2)从Vl(n)=Ve(n)开
40、始向后递推为尾的弧的集合是所有以其中iSniSjijidutjVlMiniVlj11,),()()(求关键路径步骤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 Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动 e l l-e00002266046258377077071031616014140033=(a1+a4)-(a2+a5)=18-(a6+a9+
41、a11)算法实现v以邻接表作存储结构v从源点V1出发，令Ve1=0,按拓扑序列求各顶点的Veiv从汇点Vn出发，令Vln=Ven,按逆拓扑序列求其余各顶点的Vliv根据各顶点的Ve和Vl值，计算每条弧的ei和li,找出ei=li的关键活动邻接表结点：typedef struct node int vex;/顶点域 int length;struct node *next;/链域JD;表头结点：typedef struct tnode int vexdata;int in;/入度域 struct node *link;/链域TD;TD gM;/g0不用算法描述v输入顶点和弧信息，建立其邻接表v计
42、算每个顶点的入度v对其进行拓扑排序l排序过程中求顶点的Veil将得到的拓扑序列进栈v按逆拓扑序列求顶点的Vliv计算每条弧的ei和li,找出ei=li的关键活动987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=47.6 最短路径问题提出用带权的有向图表示一个交通运输网，图中：顶点表示城市边表示城市间的交通联系权表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径最短路径求从某个源点到其余各顶点的最短路径51643208562301371732913长度最短路
43、径813192120v迪杰斯特拉(Dijkstra)算法思想按路径长度递增次序产生最短路径算法：把V分成两组：（1）S：已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加入到S中，保证：（1）从源点V0到S中各顶点的最短路径长度都不大于 从V0到T中任何顶点的最短路径长度 （2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶点作中间 顶点的最短路径长度依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的 直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和（反证法可证）v求
44、最短路径步骤l初始时令 S=V0,T=其余顶点，T中顶点对应的距离值u若存在，为弧上的权值u若不存在，为l从T中选取一个其距离值为最小的顶点W，加入Sl对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值l重复上述步骤，直到S中包含所有顶点，即S=V为止1383032V2:813-133032V1:13-13302220V3:13-192220V4:19终点 从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6:20516432085623013717329v算法实现l图用带权邻接矩阵存储adl数组dist存放当前找到的从
45、源点V0到每个终点的最短路径长度，其初态为图中直接路径权值l数组pre表示从V0到各终点的最短路径上，此顶点的前一顶点的序号；若从V0到某终点无路径，则用0作为其前一顶点的序号v算法描述627543185623013717329017020605079032308131addist1 2 3 4 5 6 70 13 8 30 32pre1 2 3 4 5 6 70 1 1 0 1 0 1(1)k=11133122 20221941215111长度最短路径13813192120v算法分析：T(n)=O(n)首先:V3加进来,(V1,V3,V4)=13求每一对顶点之间的最短路径v方法一：每次以一个
46、顶点为源点，重复执行Dijkstra算法n次 T(n)=O(n)v方法二：弗洛伊德(Floyd)算法l算法思想：逐个顶点试探法l求最短路径步骤u初始时设置一个n阶方阵，令其对角线元素为0，若存在弧，则对应元素为权值；否则为u逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值u所有顶点试探完毕，算法结束例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 2
47、3 7 0加入V3：路径：AB ABCBCA BCCA CABl算法实现u图用邻接矩阵存储ulength存放最短路径长度upathij是从Vi到Vj的最短路径上Vj前一顶点序号l算法描述例132264311初始：0 4 116 0 23 0length=-1 -1 -1-1 -1 -1-1 -1 -1path=加入V1：0 4 116 0 23 7 0length=-1 -1 -1-1 -1 -1-1 1 -1path=加入V2：0 4 66 0 23 7 0length=-1 -1 2-1 -1 -1-1 1 -1path=加入V3：0 4 65 0 23 7 0length=-1 -1 23 -1 -1-1 1 -1path=l算法分析：T(n)=O(n)
