8.1 图的基本概念 8.2 图的存储结构 8.3 图的遍历 8.4 生成树 8.5 最短路径 8.6 拓扑排序 8.7 关键路径

Presentation on theme: "8.1 图的基本概念 8.2 图的存储结构 8.3 图的遍历 8.4 生成树 8.5 最短路径 8.6 拓扑排序 8.7 关键路径"— Presentation transcript:

1 8.1 图的基本概念 8.2 图的存储结构 8.3 图的遍历 8.4 生成树 8.5 最短路径 8.6 拓扑排序 8.7 关键路径
第八章 图 8.1 图的基本概念 8.2 图的存储结构 8.3 图的遍历 8.4 生成树 8.5 最短路径 8.6 拓扑排序 8.7 关键路径

2 8.1 图的基本概念 图:是一种数据结构，它的形式化定义为Graph=（V，E）,其中V是图中结点（Vertices）的非空有限集，E是图中边（Edges）的有限集 事例：

3 无向图： 图上的每条边都没有方向，即两个顶点对（V1，V2）和（V2，V1）代表同一边
事例：图8-1(b)中的G2是一个无向图：G2=( V , E )，其中：V=V1,V2,V3,V4,V5，E=(V1,V2)，(V1,V4)，(V2,V3)，(V2,V5) , (V3,V4) , (V3,V5) 有向图：图上的每条边都是有方向的，即两个顶点对（V1，V2）和（V2，V1）代表两条边 事例：图8-1(a)中的G1是一个有向图：G1=(V, E) 其中：V=V1,V2,V3,V4，E=〈V1,V2〉，〈V1,V3〉，〈V3,V4〉，〈V4,V1〉 图8-1

4 有向完全图：对于有向图，有n(n-1)条弧的有向图，如图8-1(c)所示（n为弧的数目）
无向完全图：对于无向图，有n(n-1)/2条边的无向图，如图8-1(d)所示 （n为边的数目） 权(weight)：与图的边或弧相关的数叫做权(weight)，权反应了这条边或弧的某种特征的数据 网(network)：带权的图 事例： 图8-1

5 子图（subgraph）：有两个图G=(V , E)和G′=(V′, E′)，如果V′V且E′E，则称G′为G的子图 事例：

6 弧头和弧尾: 有向图中存在<vi ,vj>，称弧的始点vi为弧尾，弧的终点vj为弧头
度: 无向图G=(V , E)，边(v，v′)E，称顶点v和v′互为邻接点(adjacent);边(v，v′)依附(incident)于顶点v和v′，或说边(v，v′)和顶点v与v′相关联;顶点v的度(degree)是和顶点v相关联的边的数目，记为TD(V) 入度(indegree):以顶点v为头的弧的数目，称为v的入度，记为ID（v） 出度(outdegree)：以顶点v为尾的弧的数目，称为v的出度，记为OD（v）

7 顶点的度：顶点的度TD（v）=ID（v）+OD（v）
路径：无向图G = (V , E)中从顶点v到顶点v的路径(path)是一个顶点序列(v,vi,0,vi,1,vi,2vi,m,v)，其中(vi,j-1,vi,j)E，1jm；如果G是有向图，则路径也是有向的顶点序列，应满足vi,j-1,vi,jE，1jm； 路径的长度：路径上的边或弧的数目 回路或环（cycle）：第一个顶点和最后一个顶点相同的路径 简单路径：序列中顶点不重复出现的路径 简单回路：一条简单路径，其长度2，且路径的起始点和终止点是同一顶点的路径

8 连通分量(connected component) ：无向图中极大连通子图 事例：
连通图（connected graph）：在无向图中，从顶点v到顶点v有路径，则称v和v是连通的；如果图中任意两个顶点vi ，vjV，vi和vj都是连通的，则称G是连通图 连通分量(connected component) ：无向图中极大连通子图 事例： (a) 无向图G (b)G5的三个连通分量

9 强连通图：有向图G中，如果对于每一对vi,vjV，vivj ，从vi到vj和从vj到vi都存在路径，则称G是强连通图
强连通分量：有向图中的极大连通子图称为有向图的强连通分量 事例：图8-1(a)中的G1不是强连通图，但它有两个强连通分量，如图8-5所示

10 生成树：为一个极小连通子图，含有图中的全部顶点，只有足以构成一棵树的n-1条边
事例： 有向树：一个有向图恰好有一个顶点入度为0，其余顶点入度为1，则为有向树 生成森林：有向图的生成森林由若干棵有向树组成，含有图中全部顶点，只含有足以构成若干棵不相交的有向树的弧

11 事例： 例题：图G=（V，E），V={a，b，c，d，e}，E={<a，b>，<a，c>，<b，d>，<c，e>，<d，c>，<e，d>}： （1）求与顶点b相关联的弧 （2）是否存在从顶点c到b的路径 （3）求ID（d）、OD（d）、TD（d） （4）该有向图是否是强连通图 （5）画出各个强连通分量

12 （1）与顶点b相关联的弧有两条：<a，b>和<b，d>
（2）不存在从顶点c到b的路径 （3）ID（d）=2，OD（d）=1，TD（d）=3 （4）不是强连通分量 （5）有三个强连通图分量，如图8-8所示。

13 8.2 图的存储结构 邻接矩阵 邻接表 十字链表 邻接多重表

14 8.2.1 邻接矩阵表示法 概念：用二维数组存储图中顶点的信息，用矩阵表示图中各个顶点（数据元素）之间的关系（边或弧）的信息；
设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵 ： 网的邻接矩阵：网G=(V，E)含有n(1)个顶点V=（v1,v2,vn），则元素为

15 图及其邻接矩阵事例： 网及其邻接矩阵事例：

16 邻接矩阵存储结构描述： #define maxnode 15 /*最大的顶点数*/ typedef struct 
elemtype Vertex; /*顶点信息*/ vertextype； int adj; /*顶点之间相关的信息 */ arctype； typedef struct vertextype vexs[maxnode] arctype arcs[maxnode] [maxnode] graph；

17 建立无向网络的算法 ： CreatGraph ( ga) Graph *ga ; { int i,j,k ,n ; float w ;
n = maxnode ; /*图中顶点个数*/ for (i = 0; i < n ; i ++) ga -> vexs [i] = getchar ( ); /*读入顶点信息，建立顶点表*/ for ( j = 0; j < n ; j++) ga -> arcs[i][j] = 0; /*邻接矩阵初始化*/ for ( k = 0; k<e; k++) /*读入e条边*/ scanf (“%d%d%f”,&i,&j,&w) ; /*读入边(vi, vj)上的权w*/ ga -> arcs[i][j] = w ; ga -> arcs[j][i] = w ; } 返回

18 8.2.2 邻接表 概念：图的一种顺序存储结构和链式存储结构相结合的存储方法；用一维数组表示顶点结点
Vertex域存放与顶点有 关的信息；FirstArc为指针域，存放与该结点相邻接的所有顶点组成的单链表的头指针 ； 邻接单链表中每个结点表示依附于该顶点的一条边，称作边结点，边结点的结构为： Adjvertex：存放依附于 该边的另一个顶点在一维数组中的序号； Weight域存放边和该边有关的信息 ；Nextarc域为指向依附于该顶点的下一个边结点的指针 Vertex FirstArc Adjvertex Weight Nextarc

19 事例：

20 邻接表存储结构： #define maxnode 256 /*图中顶点最大数*/ typedef struct arc {
int adjvertex; /*弧头结点在数组中的序号*/ int weight; /* 当为网时有此项*/ struct arc *nextarc; }arctype; typedef struct elemtype vertex; /*顶点信息*/ arctype *firstarc; }vertextype； typedef vertextype adjlisttype[maxnode];

21 建立无向图的邻接表存储结构 main ( ) /*建立无向图graph的邻接表存储结构*/ { int i,j ,n,e,k;
int v1,v2; arctype * p, *q; adjlisttype graph; printf(“\n输入图中顶点的个数n和边数e:\n”); scanf(“%d%d”,&n,&e); printf(“\n输入图中顶点的数据:\n”); for(k=0;k<n;k++) scanf(“%d”,&graph[k].vertex); graph[k].firstarc=NULL; }

22 printf(“\n输入图中的各边,次序为弧尾编号,弧头编号:\n”)
for(k=0;k<e;k++) { scanf(“%d%d”,&v1,&v2); i=locvertex(graph,v1); i=locvertex(graph,v2); q=(arctype *)malloc(sizeof(arctype)); q->adjvertex=j; q->nextarc=graph[i].firstarc; graph[i].firstarc=q; p=(arctype *)malloc(sizeof(arctype)); p->adjvertex= i; p->nextarc=graph[j].firstarc; graph[j].firstarc=p; }

23 printf(“\n图的邻接表结构为:\n”);
for(i=0;i<n;i++) { printf(“i=%d”,i); v1=graph[i].vertex; printf(“Vertex:%d”,v1); p=graph[i].firstarc; while(p!=NULL) v2=p->adjvertex; printf(“-->%d”,v2); p=p->nextarc; } printf(“\n”)

24 返回 int LocVertex(adjlisttype graph , int v) { int k;
for(k=0;k<maxnode;k++) if(graph[k].vertex==v) return(k); } 返回

25 8.2.3 十字链表 概念：对应于有向图中的每一条弧有一个结点，对应于每个顶点也有一个结点
头域(headvex)：该弧的弧头顶点在图中的位置 尾域（tailvex）：该弧的弧尾顶点在图中的位置 链域hlink：指向与该弧具有相同弧头的下一条弧的边结点 链域tlink：指向与该弧具有相同弧尾的下一条弧的边结点 info：域指向该弧的相关信息（如权值）

26 事例：

27 存储结构： #define vtxnum 256 /*图中顶点的最大数*/ struct arctype {
int tailvex；/*该弧的尾顶点位置*/ int headvex；/*该弧的头顶点位置*/ struct arctype *hlink；/*弧头相同的弧的链域*/ struct arctype *tlink; /*弧尾相同的弧的链域*/ infotype *info; /*该边信息指针*/ }arctype; struct vertextype elemtype vertex; struct arctype *firstin；/*指向该顶点的第一条入弧*/ struct arctype *firstout；/*指向该顶点的第一条出弧*/ } vertextype;

28 返回 struct { vertextype xlist[vtxnum]; /*表头向量*/
int vexnum ; /*有向图的当前顶点数*/ int arcnum ; /*有向图的当前弧数*/ } 返回

29 8.2.4 邻接多重表 概念：在邻接多重表中，每一条边用一个结点表示，它由如下所示的六个域组成：
mark为标志域，保存标志该条边是否被搜索过 ivex和jvex保存该边依附的两个顶点在图中的位置 ilink保存指向下一条依附于顶点ivex的边； jlink保存指向下一条依附于顶点jvex的边； info保存指向和边相关的各种信息的指针域 data域存储和该顶点相关的信息 firstedge域保存指示第一条依附于该顶点的边

30 存储结构： 事例： # define maxvex 256 typedef emnu {unvisit , visit} visitif ;
typedef struct EdgeBox { visitif mark ; /* 访问标记*/ int ivex ; /* 依附该边的一个顶点的位置*/ int jvex ; /* 依附该边的另一个顶点的位置*/

31 struct EdgeBox *jlink ; /* 指向依附该顶点的下一条边*/ infotype *info ; /* 该边信息指针*/
struct EdgeBox *ilink ; /* 指向依附该顶点的下一条边*/ struct EdgeBox *jlink ; /* 指向依附该顶点的下一条边*/ infotype *info ; /* 该边信息指针*/ }; typedef struct VexBox { vertextype data ; EdgeBox *firstedge ; /* 指向依附该顶点的第一条边*/ typedef struct VexBox adjmulist[maxvex] ; int vexnum ; /* 无向图的当前顶点数*/ int edgenum ; /* 无向图的当前边数*/

32 图的遍历（traversing graph）：从图中任一顶点出发访遍图中所有顶点，且使每一个顶点仅被访问一次的过程
8.3 图的遍历 图的遍历（traversing graph）：从图中任一顶点出发访遍图中所有顶点，且使每一个顶点仅被访问一次的过程

33 8.3.1深度优先搜索 遍历过程：首先访问指定的起始顶点v0，从v0出发在访问了任意一个和v0邻接的顶点w1之后，再从w1出发，访问和w1邻接且未被访问过的任意顶点w2，然后从w2出发，重复上述过程，直到图中所有和v0有路径相通的顶点都被访问过；如若仍有未被访问过的顶点，则另选图中一个未曾被访问过的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止

34 事例： 图a：V1V2V4V8V5V6V3V7 图b：V5V7V6V2V4V3V1

35 遍历算法： /*遍历有n个结点的图g*/ void depthtraver(adjlisttype g , int n) { int v;
int visited[maxnode] for( v=1;v<=n；v++) visited[v]=0; for( v=1;v<= n;v++) if(visited[v]==0) dfs(g,v,visited); }

36 void dfs(adjlisttype g , int v , int visited[ ])
{ arctype *p ; int w; visited[v] = 1; /*标记第v个结点已被访问*/ printf (“%5d” , g[v].vertex ); p= g[v].firstarc; w = p -> adjvertex ; while ( p!= NULL) if (visited [w ] ==0) dfs ( g , w, visited); p = p -> nextarc ; }

37 8.3.2广度优先搜索 遍历过程：首先访问指定的起始顶点v0，从v0出发，访问v0的所有未被访问过的邻接顶点w1，w2，…，然后再依次从w1，w2，…出发，访问他们的所有未被访问过的邻接顶点如此下去，直到图中所有被访问过的顶点的邻接顶点都被访问过；若此时图中还有未被访问过的顶点，则从一个未被访问过的顶点出发，重复上述过程，直到图中所有的顶点都被访问过为止

38 事例： 遍历结果：V5V6V7V2V4V1V3

39 遍历算法： void breathtraver(graph g，int k , int visited [ ]) {
arctype *p ; qqtype *qqueue ; int w ; InitQueue ( & qqueu ); /*初始化顺序队列*/ /*访问顶点k并把它加入队列*/ visited [k] = 1; printf (“%d\n”, g[k].vertex); Enqueue (qqueue , k); /*顶点k入队列*/ while (queueempty（qqueue）!= 0 )/*判断队列是否为空*/

40 w = Dequeue (qqueue ); /*队头元素出队并置为w*/
p = ].firstarc ; while (p != NULL) { if (visited [p -> adjvertex ] == 0) visited [p -> adjvertex ] = 1 ; printf (“%d\n” , g [p -> adjvertex ] .vertex ); Enqueue (qqueue , p ->adjvertex );/*将被访问的顶点入队*/ } p = p -> nextarc;

41 8.4 生成树 生成树：图中的顶点加上遍历时经过的所有边所构成的子图
8.4 生成树 生成树：图中的顶点加上遍历时经过的所有边所构成的子图 生成森林 ：对于一个非连通图和不是强连通的有向图，从任一点出发，不能访问到图中所有顶点，只能得到连通分量的生成树，所有连通分量的生成树成生成森林 事例：

42 最小代价生成树（Mininum Cost Spanning Tree） ：选择一棵生成树，使总的费用（一
棵生成树的代价就是树上各边的代价之和 ）最小 MST的性质 ：假设N=（V，E）是一个连通网，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值（代价）的边，其中uU，vV-U，则必存在一棵包含边（u,v）的最小生成树 算法：普里姆（Prim）算法 克鲁斯卡尔（Kruskal）算法

43 8.4.1普里姆（Prim）算法 算法描述： U={u1}，T={} While (U!=V) do
(u,v)=min{Wuv; uU，vV-U} T=T+{(u,v)} U=U+{v} 结束

44 事例： a

45 算法 # define maxnode 256 /*定义顶点的最大个数*/ /*记录从顶点集U到V-U的代价最小的边的辅助数组定义*/
struct { vertextype vex ; Vrtype lowcost ; }closedge[maxnode] ; void prim(int gn[][maxnode]，int vtxnum) int v , i , j , k ; float min ; for (v=1；v<vtxnum；v++) closedge[v].vex=0； closedge[v].lowcost=gn[0][v]； }

46 /*从序号为0的顶点出发生成最小生成树*/
closedge[0].lowcost=0； closedge[0].vex=0； for(i=1；i<vtxnum；i++) { /*寻找当前最小权值的边的顶点*/ min = closege[i].lowcost； k = i； for(j=1；j<vtxnum；j++) if(closedge[j].lowcost<min&& closedge[j].lowcost!=0) min=closege[j].lowcost； k=j； } printf(“<i,i>”，closedge[k].vex , k)； closedge[k].lowcost=0；

47 for(v=1；v<vtxnum；v++)
if(gn[k][v]<closedge[v].lowcost) { closedge[v].lowcost= gn[k][v]； closedge[v].vex=k)； }

48 事例分析：

49 8.4.2 克鲁斯卡尔（Kruskal）算法 遍历过程：T是无向连通网N=（V，E）的最小生成树，E（T）是其边集，则构造最小生成树的步骤如下： T的边集E（T）有初态为空集；T中只有n个顶点，每个顶点都自成一个分量 当E中边数小于n-1时，重复执行： 在无向连通网N的边集E中选择权值最小的边<vi,vj>，并从E中删除它 如果vi、vj落在T中不同的连通分量上，则将此边加入到T中去，否则丢掉该边，继续在E中选择一条权值最小的边

50 事例：

51 算法描述： #define maxnode 256 typedef struct { elemtype v1 ; elemtype v2 ;
int cost ; }edgetype ; edgetype Edges[maxnode]; void Kruskal (edgetype Edges[ ], int n) int Vex[maxnode] ; int i,vex1,vex2 ; for ( i = 1 ; i < n+1 ; i++) Vex[i] = 0 ;

52 for ( i = 1 ; i < n+1 ; i++) { vex1 = find (Vex ,Edges[i].v1); vex2 = find (Vex ,Edges[i].v2); if (vex2 != vex1 ) Vex[vex2] = vex1 ; Printf (“%6d%6d\n”,Edges[i].v1 ,Edges[i].v2 ); } /*实现寻找图中顶点所在树的根结点在数组Vex中的序号*/ int find (int Vex [ ], int v ) /*寻找顶点v所在树的根结点*/ int t ; t = v ;

53 while (Vex[t] > 0) t = Vex[t] ; return ( t ) ; }

54 概念： 源点：路径开始的顶点 终点：最后的顶点 最短路径有两类 第一类是从一个顶点到其它各个顶点的最短路径 第二类是求每一对顶点间的最短路径
8.5 最短路径 概念： 源点：路径开始的顶点 终点：最后的顶点 最短路径有两类 第一类是从一个顶点到其它各个顶点的最短路径 第二类是求每一对顶点间的最短路径

55 8.5.1 单源最短路径 概念：从一个确定的顶点v到其余顶点的最短路径问题 事例： 从V1到V6有四条不同路径：
<V1,V3,V4,V5,V6>，长度：21（最短路径） <V1,V5,V6>长度：32 <V1,V7,V6>长度：49 <V1,V2,V6>2长度：22

56 迪杰斯特拉（Dijkstra）算法 算法描述：
用带权的邻接矩阵cost来表示带权的有向图，cost[i][j]为弧<vi，vj>上的权值（<vi，vj>存在）或为（弧<vi, vj>不存在，即vi和vj之间没有弧 dist[i]=cost[v][vi] viV 选择vj，使得dist[j]=min{dist[i]viV-S}令S=S{ vj } 修改从v出发到集合V-S上任一顶点vk可达的最短路径长度，如果dist[j]+cost[j][k]<dist[k]，则dist[k]= dist[j]+cost[j][k] 重复执行（2）、（3）直到再也没有可加入到S中的顶点为止

57 ＃define Maxnode 20 /*定义图中最大顶点数*/ # define Maxcost 99999 /*定义一个极大整数*/
算法： ＃define Maxnode /*定义图中最大顶点数*/ # define Maxcost /*定义一个极大整数*/ Void dijkstra(int cost[][Maxnode] , int n , int v0, int dist [ ]) { int s[Maxnode]； int mindis , dis ; int i , j, u ; for(i=0；i<n；i++) dist[i]=cost[v0][i]； s[i] = 0; }

58 s[v0]=1 ;/*标记源点v0/ for ( i = 1 ; i < n ; i ++) { mindis = Maxcost ; for ( j = 1 ; j < n ; j++) if (s[j] == 0&&dist[j] <mindis) u = j ; mindis = dist [j] ; } s[u] = 1 ;/*标记u*/ for (j =1; j< n ; j++) if (s[j] = =0) dis = dist[u] + cost [u][j] ; if (dist[j] > dis) dist[j] =dis; }}

59 8.5.2求每一对顶点之间的最短路径 算法描述： 注：A[i][j]表示当前顶点vi到顶点vj的最短路径长度 算法：
A0[i][j]=cost[i][j] Ak+1[i][j]=min{Ak[i][j]，Ak[i][k+1]+Ak[k+1][j]}（0≤k≤n-1） 注：A[i][j]表示当前顶点vi到顶点vj的最短路径长度 算法： #define max 256 Void Floyd (int cost[ ][max]，int n, int weight[ ][max] , int path[ ][max]) {

60 int i，j，k； for(i=0；i<n；i++) for(j=0；j<n; j++) { weight[i][j]=cost[i][j]; path[i][j]=0; } for(k=0；k<n；k++) for(j=0；j<n；j++) if (weight[i][j]>(weight[i][k]+weight[k][j])) weight[i][j]=weight[i][k]+weight[k][j]； path[i][j]=k;

61 8.6 拓扑排序 概念： 设S是一个集合，R是S上的一个关系，a和b是S中的任意元素：
8.6 拓扑排序 概念： 设S是一个集合，R是S上的一个关系，a和b是S中的任意元素： 若(a,b)R，则称a是b关于R的前趋元素，b是a关于R的后继元素 若a、b、c是S中的任意元素，若(a,b) R， (b,c) R，则必有（a,c）R，则R是S上的传递关系 若对于S中任一元素a，不存在（a，a）R，则称R是S上的一个非自反关系 若S上的一个关系R是传递关系且是非自反的，则称R是S上的偏序关系 若R是集合S上的一个偏序关系，A =（ai , aj）A是S中元素的一个序列，且当（ai , aj）R时，有i < j，则称A是相对于R的一个拓扑序列

62 AOV-网络：在一个有向图G中，若用顶点表示活动或任务，用边表示活动（或任务）之间的关系 AOV-网拓扑排序算法的基本步骤：
拓扑排序：构造拓扑序列的过程 AOV-网络：在一个有向图G中，若用顶点表示活动或任务，用边表示活动（或任务）之间的关系 AOV-网拓扑排序算法的基本步骤： 在网络中选取一个没有前趋的顶点，且把它输出； 从网络中删除该顶点和以它为尾的所有出边。 重复执行上述两个步骤，直到所有顶点都被输出，或者直到遗留在网络上的顶点都有前趋顶点为止

63 事例：

64 拓扑有序序列：V1V3V7V4V9V2V5V8V6

65 其邻接表：

66 算法： typedef int datatype ; typedef int vextype ; typedef struct node {
int adjvex ; /*邻接点域*/ struct node *next ; /* 链域*/ }edgenode ; /* 边表结点*/ typedef struct vextype vertex ; /*顶点信息 */ int indgree ; /*入度*/ edgenode *link ; /*边表头指针*/ }vexnode ; /*顶点表结点*/ vexnode dig[n] /*全程量邻接表*/

67 Toposort (vexnode dig[ ]) /*dig为AOV网的邻接表*/
{ int i , j , m , top; edgenode *p ; m = 0; /*赋初值，m为输出顶点个数计数器*/ top = -1 ; /*赋初值，top为栈指针*/ for (i = 0; i < n ;i++) /* 建立入度为零的顶点链栈*/ if ( dig [i].indgree == 0) dig[i].indgree = top ; top = i ; } while (top != -1 ) /*栈非空*/ j = top ; top = dig[top].indgree ; /*第j+1个顶点退栈*/ printf (“%d\t”,dig[j].vertex +1); /*输出退栈顶点*/

68 m++; /*为输出顶点计数*/ p = dig[j].link ; /*p指向vj+1的出边表结点的指针*/ while (p) /*删去所有以vj+1为起点的出边*/ { k = p -> adjvex ; /*k为边<vj+1 , vk+1>的终点vk+1在dig中的下标序号*/ dig[k].indgree -- ; /*vk+1入度减1 */ if (dig[k].indgree = =0) /*将新入度为零的顶点入栈*/ {dig[k].indgree = top; top = k ; } p = p ->next ;/* 找vj+1的下一条边*/ if (m<n) /* 输出顶点数小于n，有回路存在*/ printf (“\nThe network has a cycle!\n”);

69 8.7 关键路径 概念： AOE-网：在带权的有向图中，用顶点表示事件（event），用弧表示活动（activity），权表示活动持续的时间，这样组成的网称为以边表示活动的网（Activity On Edge） 起始点：入度为0的顶点 结束点：出度为0的顶点 关键路径（critical path）：从源点到汇点具有最大长度的路径 关键活动：关键路径上的活动

70 事件vi可能的最早发生时间VE(i)：是从源点v1到顶点vi的最长路径长度
事件vk的最迟发生时间VL(k)：汇点vn的最早发生时间VE(n)减去vk 到vn的最长路径长度 活动ai的最早开始时间E(i)：事件vi最早发生时间，即VE(i)=E(i) 活动ai的最迟开始时间L(i)：ai的最迟完成时间减去ai的持续时间，即L(i)=VL(k) - <vj，vk>的权

71 计算 VE(j)：从源点v1，自左到右对每个事件向前计算，直至计算到汇点vn为止 ，即VE(1)=0，VE(j)=Max{ VE(i)+ dut(<i,j>)} < vi，vj>T, j=2,3n VL(j)：从汇点vn 开始，自右到左逐个事件逆推计算，直至计算到源点v1为止 ，即VL(n)=VE(n）， VL(j)=Min{ VL(k)-dut(<j,k>)} < vj，vk>S，j = n-1，n-2，，1

72 事例：

73 算法： # define Maxsize 256 typedef int datatype ; typedef int vextype ; typedef struct node { int adjvex ; /*邻接点域*/ int dut ; /*权值*/ struct node *next ; /* 链域*/ }edgenode ; /* 边表结点*/ typedef struct vextype vertex ; /*顶点信息 */ int indgree ; /*入度*/ edgenode *link ; /*边表头指针*/ }vexnode ; /*顶点表结点*/ vexnode dig[n] /*全程量邻接表*/

74 CriticalPath (vexnode dig[ ]) /*dig为AOV网的邻接表*/
{ int i , j , m , k ; int front , rear ; /*顺序队列的首尾指针*/ int tpord[n] ,VL[n], VE[n] ; int L[Maxsize] ,E[Maxsize] ; edgenode *p ; front = -1; /*赋初值为-1*/ rear = -1 ; /*赋初值为-1*/ for (i = 0; i < n ;i++) VE[i] = 0 ;/* 各事件vi+1的最早发生时间均置初值零*/ for (i = 0; i < n ;i++) /*扫描顶点表，将入度为零的顶点入队*/ if ( dig [i].indgree == 0) tpord[++rear]=i; m=0 ; /*计数器初始化*/

75 while (front != rear ) /*队非空*/
{ front ++ ; j = tpord [front] ; /*vj+1出队，即删去顶点vj+1*/ m++; /*计算出队的顶点个数*/ p = dig[j].link ; /*p指向vj+1为起点的出边表中表结点的下标*/ while (p) /*删去所有以vj+1为起点的出边*/ /*k为边<vj+1 , vk+1>的终点vk+1在dig中的下标序号*/ k = p -> adjvex ; dig[k].indgree -- ; /*vk+1入度减1 */

76 if (VE[j] + p->dut > VE[k])
VE[k]=VE[j]+ p->dut ; /*修改VE[k]*/ if (dig[k].indgree = =0) { tpord[++rear] = k; /*将新入度为零的顶点vk+1入队*/ p= p->next ; /*找vk+1的下一条边*/ } if (m<n) /* 输出顶点数小于n，有回路存在*/ printf (“\nThe network has a cycle!\n”); return (0) ; for (i =0 ; i < n ; i++) /*为各事件vi+1的最迟发生时间VL[i]置初值*/ VL[i]=VE[n-1] ;

77 i = 0 ; /*边计数器置初值*/ for (i =n-2 ; i >= 0 ; i --) /*按拓扑序列的逆序取顶点*/ {
j = tpord[i] ; p = dig[j].link ; /*取vj+1的出边表上第一个表结点*/ while (p) { k = p->adjvex ; /*k为<vj+1, vk+1>的终点vk+1的下标*/ if ((VL[k]- p->dut )< VL[j]) VL[j] = VL[k] – p->dut ; /*修改VL[j]*/ p = p->next ; /*找vj+1的下一条边*/ } i = 0 ; /*边计数器置初值*/ for (j = 0 ; j < n ; j++) /*扫描顶点表，依次取顶点vj+1*/ p=dig[j].link ;

78 while (p) /*扫描顶点vj+1的出边表*/
{ k = p -> adjvex ; E[++i]=VE[j] ; L[i] = VL[k]- p->dut ; printf(“%d\t%d\t%d\t%d\t%d\t”, dig[j].vertex+1,dig[k].vertex+1,E[i],L[i],L[i]-E[i]); if (L[i]==E[i]) /*关键活动*/ printf(“Critical activity”); printf (“\n”) ; p = p->next ; }