第6章 图 6．2图的存储结构 6．3图的遍历 6．4图的连通性 6．5 最短路径 6．6 AOV网与拓扑排序 6. 7 AOE网与关键路径

Presentation on theme: "第6章 图 6．2图的存储结构 6．3图的遍历 6．4图的连通性 6．5 最短路径 6．6 AOV网与拓扑排序 6. 7 AOE网与关键路径"— Presentation transcript:

1 第6章 图 6．2图的存储结构 6．3图的遍历 6．4图的连通性 6．5 最短路径 6．6 AOV网与拓扑排序 6. 7 AOE网与关键路径
第6章 图 6．1图的基本概念 6．2图的存储结构 6．3图的遍历 6．4图的连通性 6．5 最短路径 6．6 AOV网与拓扑排序 AOE网与关键路径

2 6．1图的基本概念 6．1．1图的定义 图G是由两个集合V和E组成，V是有限的非空顶点集，E是顶点对所构成的边集，分别用V(G)和E(G)表示。用二元组G=(V，E)表示图G。

3 G1=(V1,E1) V1={A,B,C,D,E} E1={(A,C),(A,D),(C,D),(D,E),(E,B)}

4 G2=(V2,E2) V2={A,B,C,D,E,F} E2={<A,C>,<B,A>,<B,D>,<E,C>, <C,F>,<F,B>)}

5 加权图或网

6 图的基本操作包括： (1)CreateGraph(G)：创建图G。 (2)DestoryGraph(G)：销毁图G。
(3)LocateVertex(G，v)：确定v在图G中的位置。 (4)GetVertex(G，i)：取出第i个顶点的值。 (5)FirstAdjVertex(G，v)：求v的第一个邻接点。

7 (6)NextAdjVertex(G，v，w)：已知w是v的某个邻接点，求v的下一个邻接点。
(7)InsertVertex(G，u)：增加顶点u。 (8)DeleteVetrex(G，v)：删除v及与v相关联的弧。 (9)InsertArc(G，v，w)：增加一条从v到w的弧。 (10)DeleteArc(G，v，w)：删除v到w的弧。

8 6.1.2 图的基本术语 无向图和有向图 边集E(G)为无向边的集合，为无向图。 边集E(G)为有向边的集合，为有向图。 v2 v5 v1
图的基本术语 无向图和有向图 边集E(G)为无向边的集合，为无向图。 边集E(G)为有向边的集合，为有向图。 v2 v5 v1 v3 v4 v1 v2 v4 v3

9 6.1.2 图的基本术语 端点和邻接点 无向图中，若存在一条边(vi,vj)，则称vi、vj为该边的两个端点，并称它们互为邻接点。 v2
图的基本术语 端点和邻接点 无向图中，若存在一条边(vi,vj)，则称vi、vj为该边的两个端点，并称它们互为邻接点。 v2 v5 v1 v3 v4

10 起点和终点 有向图中，若存在边<vi，vj>，则称该边是顶点vi的出边，顶点vj的入边；并称vi为起始端点(或起点)，vj为终止端点(或终点)； v1 v2 v3 v4

11 度、入度和出度 无向图顶点 v 的度是和 v 相关联的边的数目，记做D(v)。 v2 v5 v1 v3 v4 v3 的度为 3

12 有向图顶点 v 的度分为出度和入度。 顶点 v 的度为 D(v) = ID(v) + OD(v)。 v1 v2 v4 v3
以 v 为头的弧的数目称为 v 的入度，记ID(v) ； 以v 为尾的弧的数目称为 v 的出度，记OD(v)； 顶点 v 的度为 D(v) = ID(v) + OD(v)。 v1 v2 v4 v3

13 子图 假设图 G=(V, E) 和 G’=(V’, E’) ，如果 V’  V，且 E’  E，则称 G’ 为 G 的子图。 v1 v3
求子图 v1 v1 v2 v4 v3 v1 v4 v3 v1 v2 v4 v3

14 无向完全图和有向完全图 无向图若具有n(n-1)/2条边，称为无向完全图。

15 无向完全图和有向完全图 有向图具有n(n-1)条边，称为有向完全图。

16 稀疏图和稠密图 边较少(边数e<<nlog2n)的图称为稀疏图。边较多的图称为稠密图。 路径和路径长度
无向图 G 中若存在一条有穷非空序列 w = v0 e1 v1 e2 v2 … ek vk ，其中 vi 和 ei 分别为顶点和边，则称 w 是从顶点 v0 到 vk 的一条路径。 v0 v1 v2 vk-1 vk . . . e1 e2 ek 路径的长度是路径上的边的数目。

17 简单路径 若路径 w 的顶点 v0 , v1 , … , vk 互不相同，则称 w 为简单路径。 …

18 回路(环) 若一条路径上的开始点和结束点为同一个顶点，则称该路径为回路(环)。 开始点与结束点相同的简单路径称为简单回路(简单环)。
一个图如果不存在环，称为无环图。

19 连通、连通图和连通分量 无向图中 v 到 v’ 有路径，称连通的。 无向图 中任意两个顶点 vi , vj 都是连通的，称连通图。
连通分量：无向图中的极大连通子图。

20 A B C L H D E F G 非连通图 连通分量为 A B C L H F G H D E

21 强连通图和强连通分量 有向图 中每一对 vi, vj ∈V，vi≠vj ，从 vi 到 vj 和 从 vj 到 vi 都存在路径，G 是强连通图。 有向图中的极大强连通子图称强连通分量。 v1 v2 v4 v3 强连通分量 v1 v4 v3 v2

22 生成树、生成森林 无向图是连通的，包含所有顶点并含有最少边的连通子图称为无向图的生成树。

23 A B C L H J 生成树 A B C L H J A B C L H J A B C L H J

24 权和网 图的边或弧赋予相关的数值称为权。 带权的图称为网。 带权的无向图称为无向网。 带权的有向图称为有向网。
无向图G不是连通的，G的每个连通分量的生成树组成的森林为生成森林。 权和网 图的边或弧赋予相关的数值称为权。 A B C D E 5 3 8 2 1 4 9 7 带权的图称为网。 带权的无向图称为无向网。 带权的有向图称为有向网。

25 6．2 图的存储结构 6．2．1邻接矩阵 G 具有 n 个顶点 和 m 条边或弧 ，G 的邻接矩阵是 n×n 阶矩阵，记为 A(G) 。
6．2 图的存储结构 6．2．1邻接矩阵 G 具有 n 个顶点 和 m 条边或弧 ，G 的邻接矩阵是 n×n 阶矩阵，记为 A(G) 。 存放 n 个顶点信息和 n2 条边或弧信息。

26 aij 定义: aij= 1 vi 与 vj 不相邻 vi 与 vj 相邻

27 vi 的度是邻接矩阵第 i 行或第 i 列的元素之和。
【例6.1】无向图 G A(G) = 1 2 3 4 5 v1 v2 v3 v4 v5 vi 的度是邻接矩阵第 i 行或第 i 列的元素之和。

28 【例6.2】有向图 G vi 出度是第 i 行的元素之和。 vi 入度是第 i 列的元素之和。 v1 v2 v3 v4 A(G) =
1 2 3 4 v1 v2 v4 v3 vi 出度是第 i 行的元素之和。 vi 入度是第 i 列的元素之和。

29 无向图 有向图 无向图的邻接矩阵是对称矩阵。 有向图的邻接矩阵一般不对称。 ★无向图可以压缩存储 0 1 0 1 0 1 0 1 0 1
1 2 3 4 5 1 2 3 4 无向图 有向图 无向图的邻接矩阵是对称矩阵。 有向图的邻接矩阵一般不对称。 ★无向图可以压缩存储

30 aij = wij ∞ vi 与 vj 相邻接 vi 与 vj 不相邻接

31 带权图(网) 的邻接矩阵 A = 1 2 3 4 5 6 ∞ 5 ∞ 7 ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 5 8 ∞ ∞ ∞ ∞ 9 v1 v2 ∞ ∞ 5 ∞ ∞ 6 ∞ ∞ ∞ 5 ∞ ∞ 8 4 3 ∞ ∞ ∞ ∞ 3 7 v3 9 v6 6 5 1 v5 v4 5

32 带权无向图邻接矩阵的算法 ： (1)构造类型定义 #define MAXVEX 100 /*图的顶点个数*/ typedef struct
{ char vexs[MAXVEX]; /*顶点信息表*/ int edges[MAXVEX][ MAXVEX]; /*邻接矩阵*/ int n,e; /*顶点数和边数*/ }graph;

33 (2)建邻接矩阵(对无向图) CreateGraph(graph *ga) { int i,j,k,w; printf("请输入图的顶点数和边数：\n"); scanf("%d%d",&(ga->n),&(ga->e)); for(i=0;i<ga->n;i++) scanf("%c",&(ga->vexs[i])); /*输入顶点信息*/ for(i=0;i<ga->n;i++) /*邻接矩阵初始化*/ for(j=0;j<ga->n;j++) ga->edges[i][j]=0; for(k=0;k<ga->e;k++) /*读入边顶点编号和权值，建立邻接矩阵*/ { scanf("%d,%d,%d”,&i,&j,&w); ga->edges[i][j]=ga->edges[j][i]=w;}} 算法的执行时间是O(n+n2+e)，时间复杂度为O(n2)。

34 6．2．2 邻接表 邻接表存储结构是对图中的每个顶点建立一个带头结点的单链表。

35

36 typedef enum{UDG,/*无向图*/
WUDG,/*赋权无向图*/ DG,/*有向图*/ WDG/*赋权有向图*/} GraphKind; typedef struct rnode/*邻接点结点的结构*/ { int adjvexpos; /*顶点在list中的位置*/ struct rnode *next; }RNode; typedef struct { VertexDT data; /*顶点数据域*/ RNode *firstarc; /*链表头指针域*/ }VNode;

37

38

39

40 逆邻接表

41 有向图的邻接表和逆邻接表结合在一起，交叉链表。

42 6.3 图的遍历 从某一顶点出发访遍图中所有顶点，且每一个顶点仅被访问一次，称为图的遍历。
6.3 图的遍历 从某一顶点出发访遍图中所有顶点，且每一个顶点仅被访问一次，称为图的遍历。 避免同一个顶点被访问多次，增设一个数组 visited[0 . . n-1] 指示顶点是否已被访问过。

43 6．3．1广度优先搜索 (2) 接着依次访问与顶点i有边相连的所有顶点W1，W2，…，Wt；
(1) 访问顶点i，将访问标志置为已被访问，即visited[i]=1； (2) 接着依次访问与顶点i有边相连的所有顶点W1，W2，…，Wt； (3) 再按顺序（ “先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问）访问与 W1，W2，…，Wt有边相连又未曾访问过的顶点；依此类推，直到所有顶点都被访问完为止。

44 A BDF EG JI CH

45 无向图的广度优先搜索生成森林

46 BFS(ALGraph *g，int vi)
/*对邻接表g从顶点vi开始广度优先遍历*/ { int i,v,visited[MAXVEX]; int Qu[MAXVEX],front=0,rear=0; /*循环队列*/ RNode *p; for(i=0;i<g->n;i++) /*给visited置初值0*/ visited[i]=0; visited[vi]=1; /*访问初始顶点*/ printf(“%d ”,vi); rear=(rear+1)%MAXVEX; Qu[rear]=vi; /*初始顶点入队列*/ while(front!=rear) /*队列不为空时循环*/

47 {front=(front+1)%MAXVEX;
v=Qu[front]; /*出队列*/ p=g-> list[v]. firstarc ; /*查找v第一个邻接点*/ while(p!=NULL) /*查找v的所有邻接点*/ { if(visited[p->adjvexpos]==0) { visited[p->adjvexpos]=1; printf("%d",p->adjvexpos); /*访问该点并使之入队列*/ rear=(rear+1)%MAXVEX; Qu[rear]=p->adjvexpos; } p=p->next; /*查找v的下一个邻接点*/ } } }

48 6．3．2深度优先搜索 (1)先访问顶点i，将其访问标记置为访问过，即visited[i]=1；
(2)搜索与i有边相连的下一个顶点j，若j未被访问过，则访问它，将visited[j]=1，然后从j开始重复此过程，若j已访问，再看与i有边相连的其它顶点； (3)若与i有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，直到所有顶点都被访问完止。

49 无向图的深度优先搜索

50 无向图的深度优先搜索生成森林

51 DFS (ALGraph *g,int vi) /*从vi出发深度优先搜索图*/ { InitStack(S); /*初始化空栈*/ Push(S,vi); while(!Empty(S)) {v=Pop(S); if(!visited(v)) { visit(v);visited[v]=1;} w=FirstAdj(g,v); /*求v的第一个邻接点*/ while(w!=-1) { if(!visited(w)) {Push(S,w); visit(w); visited[w]=1; } w=NextAdj(g,v,w); /*求v相对于w的下一个邻接点*/}}}

52 6．4 图的连通性 赋权无向连通图的所有生成树中,各边上权值总和最小的生成树称为最小生成树。

53 6.4.1 普里姆算法 任取一个顶点K作为开始点，令U={k}，W=V-U，其中V为顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离, 使之保持最小，重复此过程，直到W为空集止。

54

55 若lowcost[i]=0，i在U中； 若0<lowcost[i]<∞，则i在(V-U)中，i和U中的顶点closest[i]构成的边(i，closest[i])是所有与i相邻、另一端在U的具有最小权值的边，最小的权值为lowcost[i]； 若lowcost[i]=∞，表示i与closest[i]之间没有边。 算法每一步扫描数组lowcost，在V-U中找出离U最近的顶点，令其为k，并打印边(k，closest[k])。修改数组lowcost和closest，标记k已经加入U。

56 对应的普里姆算法： #define INF 32767 /* INF 表示∞ */
Prim(int cost[][MAXVEX],int n,int v) /*输出最小生成树的每条边*/ { int lowcost[MAXVEX],min; int closest[MAXVEX],i,j,k; for(i=0;i<n;i++) /*给lowcost[]和closest[]置初值*/ { lowcost[i]=cost[v][i]; closest[i]=v; } for(i=1;i<n;i++) /*找出n-1个顶点*/ { min=INF ;

57 if(lowcost[j]!=0&&lowcost[j]<min) { min=lowcost[j]; k=j ; }
for(j=0;j<n; j++) /*在(V-U)中找出离U最近的顶点k*/ if(lowcost[j]!=0&&lowcost[j]<min) { min=lowcost[j]; k=j ; } printf(" 边%d 权%d",closest[k],k); lowcost[k]=0; /*标记k已经加入U*/ for(j=0;j<n;j++) /*修改数组lowcost和closest*/ if(cost[k][j]!=0&&cost[k][j]<lowcost[j]) {lowcost[j]=cost[k][j]; closest[j]=k； }}} 普里姆算法的时间复杂度为O(n2)

58 6.4.2克鲁斯卡尔算法 从赋权无向图G中取所有顶点作为一个森林F，从图G中滤出一条边，要求该边上的权值尽可能小并且该边两端的顶点必须分别处在森林F中的两棵树上，用该边把森林F中的两棵树合并成一棵，森林F中便减少了一棵树，按这个规则继续从图中滤出边来合并森林中的两棵树，直到森林中只有一棵树为止。

59

60 对应的克鲁斯卡尔算法： typedef struct { int u; /* 边的起始顶点*/ int v; /*边的终止顶点*/
int w; /*边的权值*/ }Edge; void Kruskal(Edge E[ ]，int n，int e) { int i,j,m1,m2,sn1,sn2,k; int vset[MAXV]; for(i=0;i<n;i++) vset[i]=i; /*初始化辅助数组*/ k=1; /*k表示当前构造最小生成树的第几条边，初值为1*/

61 j=0 ; /*E中边的下标，初值为0*/ while(k<n) /*生成的边数小于n时循环*/ { m1=E[j].u;m2=E[j].v; /*取一条边的头尾顶点*/ sn1=vset[m1];sn2=vset[m2];/*分别得到两个顶点所属的集合编号*/ if(sn1!=sn2) /*两顶点属不同的集合，该边是最小生成树的边*/ { printf("(%d,%d):%d",m1,m2,E[j].w); k++; /*生成边数增1*/ for(i=0;i<n;i++) /*两个集合统一编号*/ if(vset[i]==sn2) /*集合编号为sn2的改为sn1*/ vset[i]=sn1; } j++; /*扫描下一条边*/

62 6．5 最短路径 1、从甲地到乙地是否有公路？ 2、从甲地到乙地可能有多少条公路，哪条公路最短或花费最小？
6．5 最短路径 对于一个汽车司机或乘客来说： 1、从甲地到乙地是否有公路？ 2、从甲地到乙地可能有多少条公路，哪条公路最短或花费最小？ 最短路径是指经过的边的权值之和最小，而不是边的数目最小。

63

64 分两种情况： 单源最短路径； 每对顶点之间最短路径。
在赋权有向图中，顶点vi到顶点vj所有经过的弧上权值之和最小的路径就是vi到vj的最短路径。 分两种情况： 单源最短路径； 每对顶点之间最短路径。

65 单源最短路径 s[0，…，n-1]用于标记已找到最短路径的顶点。设顶点v为源点，集合s的初态只包含顶点v。 s[i]=

66 path[i]保存从源点v到终点vi当前最短路径中的前一个顶点编号，它的初值为源点v的编号 (v到vi有边)或-1(v到vi无边)。
dist[i]=cost[v][i]：从源点到其他各顶点距离，从V-S中选出一个顶点vu，使dist[u]的值最小。把u加入S中：dist[j]和dist[u]+cost[u][j]选择较小的值作为新的dist[j]。重复…。 path[i]保存从源点v到终点vi当前最短路径中的前一个顶点编号，它的初值为源点v的编号 (v到vi有边)或-1(v到vi无边)。

67

68 V1 50 <v0,v1> 45 <v0,v2,v3,v1> V2 10 <v0,v2> V3 ∞ 25 <v0,v2,v3> V4 <v0,v4> V5 Vj u (v0,v2) (v0,v2,v3) (v0,v2,v3,v1) (v0,v2,v3,v1,v4)

69 else path[i]=-1; } s[v]=1;path [v]=0; /*源点编号v放入 s*/ for(i=0;i<n;i++) /*循环直到所有顶点的最短路径都求出*/ { mindis=INF; u=-1; for(j=0;j<n; j++) /*选取不在s中且具有最小距离的顶点u*/ if(s[j]==0&&dist[j]<mindis) { u=j ; mindis=dist[j]; void Dijkstra(int cost[][MAXVEX]，int n，int v) { int dist[MAXVEX],path[MAXVEX]; int s[MAXVEX]; int mindis,i,j,u,pre; for(i=0;i<n;i++) {dist[i]=cost[v][i]; /*距离初始化*/ s[i]=0; /*s[]置空*/ if(cost [v][i]<INF) /*路径初始化*/ path[i]=v;

70 if(u!=-1) /*找到最小距离的顶点u*/ { s[u ]=1; /*将u加入s中*/ for(j=0;j<n;j++)
{if(i!=v) { printf(“ %d->%d:”,v,i); if(s[i]==1) {printf(“路径长度 %d”,dist[i]); pre=i; printf(“ 路径逆序为”); while(pre!=v) /*一直回溯到初始顶点*/ { printf(“%d,”,pre); pre=path[pre];} printf(“%d\n”,pre); } else printf(“不存在路径\n”);}}} if(u!=-1) /*找到最小距离的顶点u*/ { s[u ]=1; /*将u加入s中*/ for(j=0;j<n;j++) /*修改不在s中的顶点距离*/ if(s[j]==0) if(cost[u][j]<INF&&dist[u]+cost[u][j]<dist[j]) {dist[j]=dist[u]+cost[u][j] ; path[j]=u; } } } for(i=0;i<n;i++) /*输出最短路径的长度，路径逆序输出*/

71 6.5.2 每对顶点之间的最短路径 从vi到vj有边，则从vi到vj存在一条长度为cost[i][j]的路径。该路径不一定是最短路径，尚需进行n次试探。 首先考虑路径(vi,v0,vj)是否存在(即判断弧(vi,v0)和(v0,vj)是否存在)。如果存在，则比较其路径长度。 再增加一个顶点v1，即如果(vi ，…，v1)和(v1, …,vj) ,再增加一个顶点v2，继续进行试探。依此类推，直至经过n次比较，最后求得的必是从vi到vj的最短路径。

72 现定义一个n阶方阵序列：A -1，A0， …，Ak，…，An-1，其中：
A-1[i][j]=cost[i][j] (0≤i≤n-1，0≤j≤n-1) Ak+1[i][j]=min{Ak[i][j],Ak[i][k+1]+Ak[k+1][j]} (-1≤k≤n-2 )

73

74 【算法6.7】 #define MAXVEX 100 #define INF 32767 void Floyed(int cost[][MAXVEX],int n) {int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];

75 { printf(" %d ->%d",i,j); if(A[i][j]==INF) { if(i!=j)
int i,j,k,pre; for(i=0;i<n;i++) /*置初值*/ for(j=0;j<n; j++) { A[i][j]=cost[i][j]; path[i][j]=-1;} for(k=0;k<n;k++) { for(i=0;i<n; i++) for(j=0;j<n;j++) if(A[i][j]>(A[i][k]+A[k][j])) { A[i][j]=A[i][k]+A[k][j]; path[i][j]=k; } } for(i=0;i<n;i++) /*输出最短路径*/ for(j=0;j<n;j++) if(i!=j) { printf(" %d ->%d",i,j); if(A[i][j]==INF) { if(i!=j) printf("不存在路径\n"); } else { printf("长度%d",A[i][j]); printf("路径为%d",i); pre=path[i][j]; while(pre!=-1) { printf("%d",pre); pre=path[pre][j]; } printf("%d\n",j); } }}

76 6.6 AOV网与拓扑排序 有向图代表一个完整的任务，图中的每个顶点代表一个活动而弧代表活动的先后顺序，称为AOV网。

77 拓扑排序是把AOV网中的顶点转换成一个线性序列，有些顶点是有优先关系的，有些顶点不存在优先关系，人为地加入一些优先关系。

78 （1）在有向图中选择一个入度为0的顶点vi输出。
（2）把vi删除，并删除所有以vi为弧尾顶点的弧。 重复，直到没有顶点或没有入度为0的顶点为止。

79 算法实现 采用邻接表作为有向图的存储结构 ； 表头结点中增加一个存放顶点入度的count ； 入度为 0 的顶点即为没有前驱的顶点 ；
当某个顶点的入度为 0时，输出此顶点，同时将该顶点的所有后继顶点的入度减1； 为了避免重复检测入度为0的顶点，设立一个栈St，以存放入度为0的顶点。

80 拓扑排序算法： printf("%d"，i); /*输出顶点*/ p=adj[i].firstarc; /*找第一个相邻顶点*/
TopSort(VNode adj[],int n) {int i,j; int St[MAXV],top=-1; /*栈St的指针为top*/ RNode *p; for(i=0;i<n; i++) if(adj[i].count==0) /*入度为0的顶点入栈*/ { top++; St[top]=i;} while(top>-1) /*栈不为空时循环*/ { i=St[top];top--; /*出栈*/ printf("%d"，i); /*输出顶点*/ p=adj[i].firstarc; /*找第一个相邻顶点*/ while(p!=NULL) { j=p->adjvexpos; adj[j].count--; if(adj[j].count==0) /*入度为0的相邻顶点入栈*/ {top++; St[top]=j;} p=p->nextarc; /*找下一个相邻顶点*/} }}

81 AOE网与关键路径 赋权有向图代表一个完整任务，每个顶点代表一个事件，而弧代表活动，弧上权值代表活动持续时间，称为AOE网。

82 最关心问题： 整个工程需要时间是多少？ 哪些活动的提前或延期将直接影响整个工程的进度？

83 关键路径是指从工程开始点到工程结束点所经过的各条路径中时间耗费总量最大的路径。

84 ee(k)是指从工程开始点e1到顶点ek所耗费的最长时间。
(1)事件的最早发生时间 ee(k)是指从工程开始点e1到顶点ek所耗费的最长时间。 假设ee(1)=0，则ek的最早发生时间为： ee(k)=max{ee(j) + < ej, ek>上的权值}

85 (2)事件的最迟发生时间 不推迟整个工期的前提下，事件ek允许的最晚发生时间。ek的最迟发生时间：le(k)=min{le(j) - <ek, ej>上的权值}

86 (3)工程活动ai的最早开工时间e(i) 等于事件ek的最早发生时间。e(i)=ee(k)。

87 (4)工程活动ai的最晚开工时间 不推迟整个工期的前提下，ai必须开工的最晚时间。 l(i)=le(j) - <ek, ej>上的权值 d(i)=l(i)-e(i)是活动的时间余量。 l(i)=e(i)表示活动ai是没有时间余量的关键活动。

88 算法步骤为： （1）入度为0的工程开始点e1出发，令ee[1]=0，按正向拓扑排序顺序求其余各事件的最早发生时间ee[i](2≤i≤n )。如果得到的正向拓扑序列中事件顶点个数小于AOE网中顶点数n，则说明网中有环，操作失败，结束；否则继续下一步。 （2）从出度为0的工程结束点en出发，令le[n]=ee[n]，按逆向拓扑排序顺序求其余各事件的最迟发生时间le[i](2≤i≤n-1 )； （3）根据各事件顶点的ee和le值，求每个工程活动的最早开工时间e和最迟开工时间l。若某个工程活动的最早开工时间e和最迟开工时间l相等，则为关键活动。

89 【例6．1】AOE网的关键路径。 解：求所有事件的最早发生时间如下： ee(1)=0； ee(2)=3 ee(3)=4； ee(4)=ee(2)+2=5 ee(5)=Max{ee(2)+1， ee(3)+3)}=7； ee(6)=ee(3)+5=9 ee(7)=Max{ee(4)+6， ee(5)+8)}=15； ee(8)=ee(5)+4=11 ee(9)=Max{ee(8)+10，ee(6)+2)}=21； ee(10)=Max{ee(8)+4，ee(9)+1}=22 ee(11)=Max{ee(7)+7，ee(10)+6}=28

90 所有事件的最迟发生时间如下： le(11)=ee(11)=28； le(10)=le(11)-6=22 le(9)=le(10)-1=21； le(8)=Min{le(10)-4，le(9)-10}=11 le(7)=le(11)-7=21； le(6)=le(9)-2=19 le(5)=Min{le(7)-8，le(8)-4)}=7； le(4)=le(7)-6=15 le(3)=Min{le(5)-3，le(6)-5)}=4；le(2)=Min{le(4)-2，le(5)-1)}=6 le(1)=Min{le(2)-3，le(3)-4)}=0

91 求所有活动的e()、 活动a1：e(1)=ee(1)=0 活动a2：e(2)=ee(1)=0 活动a3：e(3)=ee(2)=3 活动a4：e(4)=ee(2)=3 活动a5：e(5)=ee(3)=4 活动a6：e(6)=ee(3)=4 活动a7：e(7)=ee(4)=5 活动a8：e(8)=ee(5)=7 活动a9：e(9)=ee(5)=7 活动al0：e(10)=ee(6)=9 活动a11：e(11)=ee(7)=15 活动a12：e(12)=ee(8)=11 活动a13：e(13)=ee(8)=11 活动a14：e(14)=ee(9)=21 活动a15：e(15)=ee(10)=22

92 活动a1：l(1)=le(2)-3=3， d(1)=3 活动a2：l(2)=le(3)-4=0， d(2)=0 活动a3：l(3)=le(4)-2=13， d(3)=10 活动a4：l(4)=le(5)-1=6， d(4)=3 活动a5：l(5)=le(5)-3=4， d(5)=0 活动a6：l(6)=le(6)-5=14， d(6)=10 活动a7：l(7)=le(7)-6=15， d (7)=10 活动a8：l(8)=le(7)-8=13， d(8)=6 活动a9：l(9)=le(8)-4=7， d(9)=0 活动al0：l(10)=le(9)-2=19，d(10)=10 活动a11：l(11)=le(11)-7=21， d(11)=6 活动a12：l(12)=le(10)-4=18， d(12)=-7 活动a13：l(13)=le(9)-10=11， d(13)=0 活动a14：l(14)=le(10)-1=21， d(14)=0 活动a15：l(15)=le(11)-6=22， d(15)=0

93 结 束！