第七章 图 7.1 图的基本概念 7.2 图的存储表示 7.3 图的遍历 7.4 图的生成树 7.5 最短路径 7.6 拓扑排序

Presentation on theme: "第七章 图 7.1 图的基本概念 7.2 图的存储表示 7.3 图的遍历 7.4 图的生成树 7.5 最短路径 7.6 拓扑排序"— Presentation transcript:

1 第七章 图 7.1 图的基本概念 7.2 图的存储表示 7.3 图的遍历 7.4 图的生成树 7.5 最短路径 7.6 拓扑排序
第七章 图 7.1 图的基本概念 7.2 图的存储表示 7.3 图的遍历 7.4 图的生成树 7.5 最短路径 7.6 拓扑排序 7.7 关键路径 小 结 2018年11月13日 1

2 本章主要内容 图的存储存储 图的遍历 最小生成树 拓扑排序 最短路径 关键路径
《数据结构》主要包括三种基本结构：线性结构，树型结构，图型结构。本章将学习图型结构知识。在图结构中，每个结点都可以和其它任何结点相连接。通过本章内容学习，应该掌握的知识如下： 图的定义和相关术语   图的存储存储 图的遍历 最小生成树   拓扑排序 最短路径 关键路径 2018年11月13日 2

3 G表示一个图，V是图G中非空顶点的集合，E是图G中边的集合。
7.1 图的基本概念 1．图的定义 图G (Graph)是由非空的顶点集合V（G）和描述顶点之间关系的边集合E（G）构成，其形式定义为：G＝(V(G)，E(G))。简写为G＝(V，E)。 G表示一个图，V是图G中非空顶点的集合，E是图G中边的集合。 无向图 G1 V0 V3 V2 V1 V2 V0 V3 V1 有向图G2 2018年11月13日 3

4 顶点（或结点）：图中，数据元素vi称为顶点(vertex )或结点。
2．图的相关概念 V0 V3 V2 V1 V2 V0 V3 V1 顶点（或结点）：图中，数据元素vi称为顶点(vertex )或结点。 向图：图中，如果某两个顶点构成的(vi, vj)∈E是无序偶，即顶点之间的连线是没有方向区分的，则称这样的边是无向边，简称边。用（vi, vj）来表示，称vi,和vj互为邻接点。如果某图全部是由无向边构成，则称该图为无向图。 有向图：在一个图中，如果两个顶点构成的<vi, vj>∈E是序偶，则称这样的边是有向边，简称弧。用<vi, vj>来表示。如果某图全部是由有向边构成，则称该图为有向图。 2018年11月13日 4

5 无向完全图：在一个无向图中，设V是包含n个结点的集合，且对于任意两个不相同的顶点之间都有一条边将它们连接，则称该图为无向完全图。
结论：在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。 有向完全图：在一个有向图中，设V是包含n个结点的集合，且对任意两个不同结点之间都有方向相反的两条弧相连，则称该图为有向完全图。 结论：在一个含有n个顶点的有向完全图中，有n(n-1)条弧。 V2 V0 V3 V1 V0 V3 V2 V1 2018年11月13日 5

6 结论：对于具有n个顶点、e条边的图，顶点vi的度D (vi)与边的数目满足如下关系：
顶点的度：顶点的度（degree）是指和该顶点相关联的边的数目，通常记为D (v)。 在有向图中，将从该顶点出发的弧的数目称为该顶点的出度，用OD(v)表示；对应的，将以该顶点结束的弧的数目称为该顶点的入度，用ID(v)表示；有向图顶点的度为出度和入度之和： D (v)=ID (v)＋OD(v)。 V0 V3 V2 V1 结论：对于具有n个顶点、e条边的图，顶点vi的度D (vi)与边的数目满足如下关系： 2e=（ D(vi)) n ∑ i=1 V2 V0 V3 V1 2018年11月13日 6

7 网络：若图的每条边(弧)都被赋予了具体含义，这种与图的边(弧) 相关的数据称为权，称这样的图为加权图或网络。 路径：在无向图中，若存在一个顶点序列vi,vi1,vi2,…,vim,vj，使得（vi,vi1），(vi1,vi2)，…，(vim,vj)均属于E(G)，则称顶点vi到vj 存在一条路径。对于有向图，路径由弧组成， 即<vi,vi1>，<vi1,vi2>，…,<vim,vj> 均属于E(G)。 V2 V0 V3 V1 4 6 5 2 7 无向加权图 路径上边的数目称为路径长度。 2018年11月13日 7

8 回路：假设从vi到vj存在一条路径，且vi=vj，则称该路径为回路。顶点不重复出现的路径称为简单路径。 子图：设G(V,E)，G’(V’,E’)是两个图，假设V’⊆V且E’⊆E，称G’为G的子图。当满足V’=V且E’⊆E，称G’为G的生成子图。 V2 V0 V3 V1 有向图G2 无向图 G1 图G1和G2的子图 V1 V0 V2 V3 2018年11月13日 8

9 连通、强连通 若从顶点vi到顶点vj（i≠j）之间有路径存在，则称该两个顶点是连通的。 对于无向图，其中任意两顶点都是连通的，则称该无向图是连通图。无向图中的极大连通子图称为连通分量。
无向图G3及连通分量 2018年11月13日 9

10 在有向图中，若任意两个顶点vi和vj都连通，则称该有向图为强连通图。有向图的极大强连通子图称为强连通分量。
G4的强连通分量 V1 V0 有向图G4 V2 V3 生成树：连通图G的生成树，是G中包含其全部n 个顶点的一个极小连通子图。即由n个顶点，n-1条边构成的连通图。 生成森林：在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。 2018年11月13日 10

11 7.2 图的存储表示——邻接矩阵、邻接表等 7.2.1 邻接矩阵
7.2 图的存储表示——邻接矩阵、邻接表等 邻接矩阵 用二维数组来描述图中结点之间相邻关系的存储结构。假设有图G＝(V，E)，其中V＝{v0,v1,…,vn-1}，用一个n×n的矩阵来表示G中各顶点相邻的关系，则矩阵的表示如下： 3 V1 V3 V2 V0 2018年11月13日 11

12 图的邻接矩阵存储方法用一个二维数组存储顶点之间的相邻关系，再用一个一维数组存储顶点信息，另外还需要存储图的顶点数和边(弧)数。
邻接矩阵的说明： ① 无向图的邻接矩阵是一个对称矩阵。 ② 无向图邻接矩阵第i行（或第i列）中非零元素的个数表示第i个顶点的度。 ③ 有向图邻接矩阵第i行（或第i列）中非零元素的个数表示第i个顶点的出度（或入度）。 ④ 用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间的邻接关系。 2．图的邻接矩阵的建立 图的邻接矩阵存储方法用一个二维数组存储顶点之间的相邻关系，再用一个一维数组存储顶点信息，另外还需要存储图的顶点数和边(弧)数。 2018年11月13日 12

13 void CreateMGraph(Mgragh *G) int i,j,k,w; char ch;
typedef char Vextype； typedef struct { Vextype vexs[VEX_NUM]; int adj[MAXSIZE][MAXSIZE]; /*邻接矩阵*/ int n,e; /*顶点数和边数*/ }Mgragh; 【算法7.1】图邻接矩阵的存储实现 void CreateMGraph(Mgragh *G) int i,j,k,w; char ch; printf("请输入顶点数和边数:\n"); scanf("%d,%d",&(G->n),&(G->e)); /*输入*/ printf("请输入顶点信息:\n"); 2018年11月13日 13

14 for (i=0;i<G->n;i++) scanf("%c",&(G->vexs[i])); for (i=0;i<G->n;i++) for (j=0;j<G->n;j++) G->adj[i][j]=0; /*初始化邻接矩阵*/ printf("输入每条边对应的两个顶点的序号:\n"); for (k=0;k<G->e;k++) {scanf("%d,%d",&i,&j); /*输入e条边*/ G->adj[i][j]=1; } /*若加入G->adj[j][i]=1;则为无向图的邻接矩阵存储建立*/ }/*CreateMGraph*/ 2018年11月13日 14

15 7.2.2 邻接表 表头结点 边结点 邻接表是图的顺序与链式相结合的存储方法.
邻接表 邻接表是图的顺序与链式相结合的存储方法. 邻接表的存储思路：对图中的每个顶点建立一个单链表，第i个单链表中的结点表示和顶点vi相连接的顶点，称为边结点。 每个边结点包括两个域，其中邻接点域(adjvex)存储与顶点vi邻接的顶点在图中的位置(或序号)，指针域(next)用来指向下一条边(或弧)的结点. vertex firstedge adjvex next 表头结点 边结点 每个链表依附于一个表头结点:链域(firstedge)指向链表中的第一个结点，顶点域(vertex) 存储顶点vi有关信息. 2018年11月13日 15

16 用邻接表表示的形式描述如下： typedef struct node /. 边结点. / { int adjvex; /. 邻接点域
用邻接表表示的形式描述如下： typedef struct node /*边结点*/ { int adjvex; /*邻接点域*/ struct node * next; /*指向下一个边结点的指针域*/ }EdgeNode; typedef struct vnode { Vextype vertex; EdgeNode *firstedge; }VertexNode; typedef struct { VertexNode adjlist[MAXSIZE]; int n,e; } ALGraph; adjvex next vertex firstedge 表头结点 边结点 2018年11月13日 16

17 3 V1 V3 V2 V0 V0 V1 V2 V3 3 2 1 ∧ 【算法7.2】建立有向图的邻接表存储 void CreateALGraph(ALGraph *G) { /*建立有向图的邻接表存储*/ int i,j,k; EdgeNode * s; 2018年11月13日 17

18 printf(“请输入顶点数和边数：\n”); scanf(“%d,%d”,&(G->n),&(G->e)); printf(“请输入顶点信息：\n”); for (i=0;i<G->n;i++) { scanf(“%c”,&(G->adjlist[i].vertex)); G->adjlist[i].firstedge=NULL; } printf("请输入边的信息：\n"); for (k=0;k<G->e;k++) /*建立边表*/ { scanf("%d,%d",&i,&j); s=(EdgeNode*)malloc(sizeof(EdgeNode)); s->adjvex=j; s->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=s; } }/*CreateALGraph*/ 2018年11月13日 18

19 假设无向图中有n 个顶点、e条边，则它的邻接表需n个头结点和2e个边结点。显然，在边数很少(e<<n(n-1)/2)的情况下，用邻接表表示图比邻接矩阵节省存储空间。
V2 V0 V3 V1 有向图G2 图的逆邻接表 V0 V1 V2 V3 3 ∧ (a) 邻接表 1 ∧ 1 2 3 ∧ (b) 逆邻接表 V0 V1 V2 V3 2 ∧ 1 ∧ 1 2 3 ∧ 2018年11月13日 19

20 7.3 图的遍历——从图中的某个顶点出发，对图中所有顶点访问且只访问一次的过程。有深度优先遍历和广度优先遍历两种方式。
7.3 图的遍历——从图中的某个顶点出发，对图中所有顶点访问且只访问一次的过程。有深度优先遍历和广度优先遍历两种方式。 深度优先遍历(DFS) 从图中某个顶点v出发，找一个与v相邻接且没有被访问过的顶点w访问，然后从w开始进行深度优先遍历。此过程依此类推，直到所有顶点全部被访问为止。 V6  无向图 V7 V3 V4 V5 V1 V2 V0 图无向图为例，深度优先遍历过程如下： (1) 从顶点v0出发进行遍历，在访问了顶点v0之后，选择其邻接点之一v1访问。 2018年11月13日 20

21 (2) 从v1出发进行遍历。可选择点有v6和v0，由于v0已经被访问过，因此选择v6。
 无向图 V7 V3 V4 V5 V1 V2 V0 (2) 从v1出发进行遍历。可选择点有v6和v0，由于v0已经被访问过，因此选择v6。 (3) 从v6出发进行遍历。可选择点有v1和v5，由于v1已被访问过，选择v5。 最终得到的顶点访问序列为： v0 →v1 →v6→v5→v4→v2→v3→v7。 在遍历结点的过程中需要一个访问标志数组visited[]，用来记录被访问过的顶点。 2018年11月13日 21

22 【算法7.3】采用邻接矩阵存储的图的深度优先遍历 int visited[VEX_NUM]={0}; void DFSTraverseM(MGraph *G,int i) /*从i结点开始深度优先遍历以邻接矩阵存储的图G*/ { printf("%c",G->vexs[i]); visited[i]=1; /*标志向量初始化*/ for (j=0;i<G->n;j++) if ((G->adj[i][j]==1)&&(!visited[j])) DFSTraverseM(G,j); /*vj未访问，从vj开始DFS搜索*/ }/*DFSTraveseM*/ 时间复杂度为O(n2) 2018年11月13日 22

23 【算法7.4】采用邻接表存储的图的深度优先遍历 int visited[VEX_NUM]={0}; void DFSTraverseAL(ALGraph G,int i) {EdgeNode *p; printf("%c",G.adjlist[i].vertex); visited[i]=1; p=G.adjlist[i].firstedge; while(p!=NULL) {if(visited[p->adjvex]==0) DFSTraverseAL(G,p->adjvex); p=p->next; } } 时间复杂度为O(n+e) 2018年11月13日 23

24 广度优先遍历(BFS) 遍历过程如下：从图中某顶点v0出发，之后依次访问v0的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，直至图中所有顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 V6  无向图 V7 V3 V4 V5 V1 V2 V0 首先访问v0 和v0的邻接点v1、v2和v5，然后依次访问v1的邻接点v6、v2邻接的点v3和v7、v5的邻接点v4。访问序列为：v0→v1→v2→v5→v6→v3→v7→v4 2018年11月13日 24

25 使用队列来存储已被访问的顶点的次序，以确定下一层顶点的访问顺序。
【算法7.5】采用邻接矩阵存储的图的广度优先遍历 int visited[VEX_NUM]={0}; void BFSTraverseM(Mgragh *G,int k) /*从k点开始的广度优先遍历 */ { int i,j; InitQueue(&Q); printf("%3c\n",G->vexs[k]); /*访问原点vk*/ visited[k]=TRUE; EnQueue(&Q,k); 2018年11月13日 25

26 算法分析：在广度优先遍历算法中，每个顶点至多进一次队列。因此广度优先遍历图和深度优先遍历在相同的存储结构下的时间复杂度是相同的.
while (!QueueEmpty(&Q)) { i =DeQueue(&Q); /*vi出队列*/ for (j=0;j<G->n;j++) /*依次搜索vi的邻接点vj*/ if (G->adj[i][j]==1 && !visited[j]) /*若vj未访问*/ { printf(“%3c\n”,G->vexs[j]); visited[j]=TRUE; EnQueue(&Q,j); } /*访问过的vj入队列*/ } }/* BFSTraverseM */ 算法分析：在广度优先遍历算法中，每个顶点至多进一次队列。因此广度优先遍历图和深度优先遍历在相同的存储结构下的时间复杂度是相同的. 2018年11月13日 26

27 7.4 图的生成树 设G=(E，G)为连通图，遍历图的各个顶点时，将E(G)分成两个集合E1(G)和E2(G)，E1(G)是遍历图过程中经历的边的集合；E1(G)和图G中所有顶点一起构成连通图G的极小连通子图，称为连通图的一棵生成树。  广度优先生成树 V6 V7 V3 V4 V5 V1 V2 V0  深度优先生成树 V6 V7 V3 V4 V5 V1 V2 V0 V6  无向图 V7 V3 V4 V5 V1 V2 V0 2018年11月13日 27

28 假设无向连通图是一个网络，即每条边都有一个权值，它的所有生成树中必有一棵满足边的权值总和最小的生成树，——最小生成树。
7.4.2 最小生成树的基本概念 假设无向连通图是一个网络，即每条边都有一个权值，它的所有生成树中必有一棵满足边的权值总和最小的生成树，——最小生成树。 有两种常用的构造最小生成树的方法。 7.4.3 构造最小生成树的Prim算法 设有两个集合U和T，其中集合U用于存放G的最小生成树中的顶点，集合T存放G的最小生成树中的边。令集合U的初值为U＝{v0}（假设构造最小生成树从顶点v0开始），集合T的初值为T＝{ }。 2018年11月13日 28

29 Prim算法思想：从所有（u,v）(u∈U、v∈V－U)的边中选取具有最小权值的边（u，v），将顶点v加入集合U中，将边（u，v）加入集合T中，然后以集合U={u,v}为开始点，从E中选取次小的边（u，vk）(u∈U、vk∈V－U)，重复上面的过程，直到U＝V时。 一个辅助数组dge，以记录从U到V－U具有最小权值的边。dge数据类型定义如下： typedef struct {Vextype adjvex; int lowcost; }closedge[VEX_NUM]; 2018年11月13日 29

30 例，从顶点A出发，该网络最小生成树的构造过程。
47 52 90 69 54 58 A C G B D E F 55 53 24 42 A B E 53 42 54 A B D E 53 42 A B 53 54 A B D E F 53 24 42 47 52 54 A G B D E F 53 24 42 47 52 54 A C G B D E F 53 24 42 52 2018年11月13日 30

31 【算法7.6】Prim算法实现最小生成树 int LocatVex(Mgraph Gn,Vextype v0); int Mininum(closedge dge); void Prim（Mgraph Gn,Vextype v0） { closedge dge; k=LocatVex(Gn,v0); /* 查找v0顶点序号 */ for(j=0;j<VEX_NUM;j++) if(j!=k){ dge[j].adjvex=v0; dge[j].lowcost=Gn.adj[k][j]; } dge[k].lowcost=0; /*初始U={v0}*/ 2018年11月13日 31

32 在Prim算法中，第二个for循环中又嵌套了一个for循环，算法的时间复杂度为O(n2)。
for(i=0;i<VEX_NUM-1;i++){ k=Mininum(dge); /*求权值最小的边*/ printf(dge[k].adjvex,Gn.vexs[k],dge[k].lowcost); dge[k].lowcost=0; /*顶点vk入U*/ for(j=0;j<VEX_NUM;j++) if (Gn.adj[k][j]<dge[j].lowcost){ dge[j].lowcost=Gn.adj[k][j]; dge[j].adjvex=Gn.vexs[k]; }/*if*/ } }/* Prim*/ 在Prim算法中，第二个for循环中又嵌套了一个for循环，算法的时间复杂度为O(n2)。 2018年11月13日 32

33 int LocatVex(ALgraph Gn,Vextype v0){ int i; for(i=0;i<VEX_NUM;i++){ if(Gn.vexs[i]==v0) return i; }/* LocatVex*/ int Mininum(closedge dge){ for(i=0;i<VEX_NUM;i++) if(dge[i].lowcost!=0) break; min=i; for(j=0;j<VEX_NUM;j++) if(dge[j].lowcost!=0&&dge[j].lowcost<dge[min].lowcost) min=j; return min; }/* Mininum */ 2018年11月13日 33

34 构造最小生成树的Kruskal算法 算法设计思想：设无向连通网络为G＝(V，E)，令G的最小生成树为T，其初态为T＝(V，{ })，即开始时，最小生成树T由图G中的n个顶点构成，顶点之间没有边，这样T中各顶点各自构成一个连通分量。然后，按照边的权值由小到大的顺序，考察边的两个顶点是否属于T的两个不同的连通分量，若是，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；否则舍去此边，以免造成回路，依此类推，直到边数为n-1条为止，此连通分量便为G的一棵最小生成树。 2018年11月13日 34

35 例Kruskal算法最小生成树构造过程 58 A C A C G B D E F 24 A C G B D E F 24 42 53 52
55 69 47 B D G 24 54 42 E F 90 A C G B D E F 24 42 47 A C G B D E F 24 42 47 52 A C G B D E F 24 42 47 53 2018年11月13日 35

36 52 A C G B D E F 24 42 47 53 54 从构造过程可以看出，找最小生成树的边用时间为log2e（e是图的边数），可以证明该算法的时间复杂度为0(e×log2e)，因此该算法比较适用于稀疏网求最小生成树。 2018年11月13日 36

37 从一个源点到其它各点的最短路径 ：迪杰斯特拉(Dijkstra)算法。算法思想如下：
7.5 最短路径 从一个源点到其它各点的最短路径 ：迪杰斯特拉(Dijkstra)算法。算法思想如下： 设置两个顶点集合S和T＝V－S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点v0到集合T中剩余顶点的最短路径长度值。不断重复此过程，直到集合T的顶点全部加入到S中或无通路为止。 2018年11月13日 37

38 2．迪杰斯特拉(Dijkstra)算法过程
(1) 引进一个辅助向量Dist，它的每个分量Dist[i] 表示当前所找到的从开始点v0到每个终点vi的最短路径的长度。它的初态为：若从v0到vi有弧，则Dist[i]为弧上的权值；否则置 Dist[i]为∞。显然： Dist[j]=Min{Dist[i]| vi∈V} Dist[j]表示的就是从v0出发的长度最短的一条最短路径。此路径为<v0,vj>。 100 60 20 50 10 5 30 A B C D E F 从顶点A到顶点B，C，D，E，F的最短距离为{∞，10，∞，30，100}，其最短路径为10，C进入集合S，即S={A，C}。 2018年11月13日 38

39 （1）假设用带权的邻接矩阵ed 来表示带权有向图
(2) 求次短路径的方法。 例如，当S={A，C}后，A到其它顶点B，D，E，F的最短路径改变为{∞，60，30，100}，从中继续选取最小值，以此类推，直到全部元素都加到S中去。 算法描述: （1）假设用带权的邻接矩阵ed 来表示带权有向图 100 60 20 50 10 5 30 A B C D E F （2）选择vj，使得 Dist[j]=Min{Dist[i]| vj∈V-S} 2018年11月13日 39

40 （3）修改从v0出发到集合V-S上任一顶点vk可达的最短路径长度。如果             Dist[j]+ ed [j][k]<Dist[k] 则修改Dist[k]为Dist[k]=Dist[j]+ed[j][k]，重复操作(2)、(3)共n-1次。由此求得从v0到图上其余各顶点的最短路径是路径长度递增的序列。 100 60 20 50 10 5 30 A B C D E F A到其它点的最短路径 A→ B ：无 A→ C ：10 A→ D ：50（经E） A→ E ：30 A→ F ：60（经E ，D） 2018年11月13日 40

41 【算法7. 8】迪杰斯特拉(Dijkstra)算法实现 void ShortestPath(Mgraph G,int v0,int
【算法7.8】迪杰斯特拉(Dijkstra)算法实现             void ShortestPath(Mgraph G,int v0,int *P, int *Dist)             /*若P[v][w]为1，则w是从v0到v当前求得最短路径上的顶点。若P[v][w]为1。Dist[v]是从v0到v求得最短路径的长度。final[v] 为TRUE，表示已经求得从v0到v的最短路径*/             { for (v=0;v<VEX_NUM;v++)             {final[v]=FALSE; Dist[v]=G.ed[v0][v];             for (w=0; w<VEX_NUM;w++) P[v][w]=FALSE;             if (Dist[v]<INFINITY) {P[v][v0]=TRUE; P[v][w]=TRUE;}             } /* INFINITY为边权值最大值 */ Dist[v0]=0; final[v0]=TRUE 2018年11月13日 41

42 for(i=1; i<VEX_NUM;i++) {min=INFINITY; for (w=0;w<VEX_NUM;w++)
            if (!final[w])             if (Dist[w]<min) {v=w; min=Dist[w];}             final[v]=TRUE；             for(w=0;w<VEX_NUM;w++)             if (!final[w]&&(min+G.ed[v][w]<Dist[w]))             { Dist[w]=min+G.ed[v][w];             for(j=0;j<VEX_NUM;j++)  P[w][j]=(*P)[v][j];             P[w][w]=TRUE; /*P[w]=P[v]+[w]*/             }             }             }/*ShortestPath*/ 算法分析： 第一个for循环的时间复杂度是O(n)，第二个for循环共进行n-1次，总的时间复杂度是O(n2) 2018年11月13日 42

43 100 60 20 50 10 5 30 A B C D E F ∞ 50 5 10 100 30 20 60 终点 i=1 i=2 i=3 i=4 i=5 B ∞ C 10 (A,C) D 60 (A,C,D) 50 (A,E,D) E 30 (A,E) F 100 (A,F) 90 (A,E,F) 60 (A,E,D,F) S {A,C} {A,C,E} {A,C,D,E} {A,C,D,E,F} 2018年11月13日 43

44 无环的有向图称做有向无环图（Directed Acycline Graph）。简称DAG图 。
7.6 拓扑排序 有向无环图的概念 无环的有向图称做有向无环图（Directed Acycline Graph）。简称DAG图 。 V3 V2 V1 V0 V4 V5 DAG图 AOV网与拓扑排序 。 1．AOV网(Activity on vertex network) 在网络中，用顶点表示活动，用弧表示活动之间的优先关系，则这样构成的有向图称为AOV网。 2018年11月13日 44

45 2．相关概念 在AOV网中，若从顶点vi到顶点vj之间存在一条有向路径，称顶点vi是顶点vj的前驱，vj是vi 的后继。若<vi, vj>是图中的弧，则称顶点vi是顶点vj的直接前驱，顶点vj 是顶点vi的直接后继。 课程代号 课程名 先行课程代号 C0 JAVA程序设计基础 无 C1 高等数学 C2 计算方法 C0，C1 C3 数据结构 C0，C2 C4 数据库原理 C2，C3 C5 J2EE开发与应用 C1，C3，C4 2018年11月13日 45

46 为保证该项工程顺利完成，须保证AOV网没有回路。
C1 C3 C0 C2 C4 C5 顶点表示课程，有向边表示前提条件。 3．拓扑排序 为保证该项工程顺利完成，须保证AOV网没有回路。 检测的一个方法是：把AOV网中的各个顶点排成一个线性序列。称为拓扑有序序列。 4．拓扑排序算法 ①从AOV网中选择一个没有前驱的顶点（该顶点的入度为0）并且输出它； ②从网中删去该顶点，并且删去从该顶点发出的全部有向边； 2018年11月13日 46

47 ③重复上述两步，直到剩余的网中不再存在没有前驱的顶点为止。得到C0，C1，C2，C3，C4，C5。
2018年11月13日 47

48 为了实现上述算法，对AOV网采用邻接表存储方式，并且邻接表中头结点中增加一个记录顶点入度indegree的数据域。
count vertex firstedge C1 C3 C0 C2 C4 C5  3 2 4 C0 C1 C2 C3 ∧ 3 C4 C5 1 5 indegree 有向无环图的邻接表 2018年11月13日 48

49 void Topo_Sort (AlGraph *G) { int top=-1； /* 栈顶指针初始化*/
【算法7.9】拓扑排序的实现 void Topo_Sort (AlGraph *G) { int top=-1； /* 栈顶指针初始化*/ for (i=0；i<VEX_NUM；i++) { if ( G->adjlist[i]. indegree==0) { G->adjlist[i]. indegree=top； top=i； } }  3 2 4 C0 C1 C2 C3 ∧ 3 C4 C5 1 5 indegree 2018年11月13日 49

50 {if (top=-1) return ERROR; /*该AOV网有回路*/ j=top;
for (i=0;i<n;i++) {if (top=-1) return ERROR; /*该AOV网有回路*/ j=top; top=G->adjlist[top]. indegree; printf(“%c”,G->adjlist[j].vertex); ptr=G->adjlist[j].firstedge; while (ptr!=NULL) { k=ptr->adjvex; G->adjlist[k]. indegree--; if(G->adjlist[k].indegree==0) {G->adjlist[k].indegree=top; top=k; } ptr=ptr->next; } /*找到下一个邻接点*/ } 2018年11月13日 50

51 拓扑排序结果为：C1，C0，C2，C3，C4，C5。 算法分析：
对于一个具有n个顶点、e条边的网来说，初始建立入度为零的顶点栈的时间复杂度为O(n)。在拓扑排序过程中，每个顶点进、出栈各一次，时间复杂度为O(n+e) 。  3 2 4 C0 C1 C2 C3 ∧ 3 C4 C5 1 5 indegree 所以整个算法的时间复杂度为O(n+e) 2018年11月13日 51

52 7.7 关键路径 7.7.1 AOE网（Activity on edge network）
AOE网定义：在带权的有向图中，以顶点表示事件，以有向边(弧)表示活动，弧上的权值表示活动的权值（如该活动持续的时间、活动中的开销等），则这样带权的有向图称为AOE网 a11=7 a8=8 a9=4 a12=4 a15=6 a13=10 a6=5 a10=2 a14=1 a7=6 a2=4 a1=3 a3=2 a4=1 a5=3 V1 V2 V5 V3 V4 V6 V7 V8 V9 V10 V11 2018年11月13日 52

53 AOE网具有以下两个性质： ① 只有某顶点所代表的事件完成后，从该顶点出发的各弧所代表的活动才能开始。 ② 只有在指向某顶点的所有弧所代表的活动都已经结束，该顶点所代表的事件才能发生。 a11=7 a8=8 a9=4 a12=4 a15=6 a13=10 a6=5 a10=2 a14=1 a7=6 a2=4 a1=3 a3=2 a4=1 a5=3 V1 V2 V5 V3 V4 V6 V7 V8 V9 V10 V11 2018年11月13日 53

54 可采用邻接表存储方式。边结点中增加一个dut域，用来存储权值，即该有向边代表的活动所持续的时间。
a11=7 a8=8 a9=4 a12=4 a15=6 a13=10 a6=5 a10=2 a14=1 a7=6 a2=4 a1=3 a3=2 a4=1 a5=3 V1 V2 V5 V3 V4 V6 V7 V8 V9 V10 V11 2018年11月13日 54

55 7.7.2 关键路径 用AOE网表示工程活动时，一般比较关心整个工程完成所必须花费的时间，即源点到终点的最大路径长度。具有最大路径长度的路径称为关键路径。关键路径上的活动称为关键活动。 关键路径长度=28 a11=7 a8=8 a9=4 a12=4 a15=6 a13=10 a6=5 a10=2 a14=1 a7=6 a2=4 a1=3 a3=2 a4=1 a5=3 V1 V2 V5 V3 V4 V6 V7 V8 V9 V10 V11 2018年11月13日 55

56 利用AOE网进行工程管理时要需解决的主要问题是： ①计算完成整个工程的最短工期。 ②确定关键路径。
关键路径的确定 （1）事件的最早发生时间ve[k] a11=7 a8=8 a9=4 a12=4 a15=6 a13=10 a6=5 a10=2 a14=1 a7=6 a2=4 a1=3 a3=2 a4=1 a5=3 V1 V2 V5 V3 V4 V6 V7 V8 V9 V10 V11 2018年11月13日 56

57 ve[k]是从源点到顶点vk的最大路径长度代表的时间。
ve[l]=0 ve[k]=Max{ve[j]+dut(< vj, vk>)} (<vj, vk>∈p[k]) p[k]表示所有到达vk的有向边的集合；dut(< vj, vk>)为弧< vj,vk>上的权值。 （2）事件的最迟发生时间vl[k] vl[k]是指在不推迟整个工期的前提下，事件vk允许的最迟发生时间。            vl[n]=ve[n]            vl[k]=Min{vl[j]-dut(<vk,vj>)} (< vk, vj>∈s[k]) 其中，s[k]为所有以vk发出的弧的集合。 2018年11月13日 57

58 （3）活动ai的最早开始时间e[i] 活动ai由弧<vk,vj>表示，活动ai的最早开始时间应等于事件vk的最早发生时间。因此有： e[i]=ve[k] （4）活动的最迟开始时间l[i] 在不推迟整个工程完成日期的前提下， ai必须开始的最迟时间。 l [i]=vl [j]-dut(<vk,vj>) a11=7 a8=8 a9=4 a12=4 a15=6 a13=10 a6=5 a10=2 a14=1 a7=6 a2=4 a1=3 a3=2 a4=1 a5=3 V1 V2 V5 V3 V4 V6 V7 V8 V9 V10 V11 2018年11月13日 58

59 7.8 工程应用实例 a11=7 a8=8 a9=4 a12=4 a15=6 a13=10 a6=5 a10=2 a14=1 a7=6
V1 V2 V5 V3 V4 V6 V7 V8 V9 V10 V11 1. 求事件的最早发生时间ve[k] ve (1)=0， ve (7)=max{ve(4)+6,ve(5)+8}=15 ve (2)=3 ， ve (8)=ve(5)+4=11 ve (3)=4 ， ve (9)=max{ve(8)+10,ve(6)+2}=21 ve (4)=ve(2)+2=5， ve (10)=max{ve(8)+4,ve(9)+1}=22 ve (5)=max{ve(2)+1,ve(3)+3}=7 ve (6)=ve(3)+5=9， ve (11)=max{ve(7)+7,ve(10)+6}=28 2018年11月13日 59

60 2. 求事件的最迟发生时间vl[k] vl (11)= ve (11)=28 vl (10)= vl (11)-6=22 vl (9)= vl (10)-1=21 vl (8)=min{ vl (10)-4, vl (9)-10}=11 vl (7)= vl (11)-7=21 vl (6)= vl (9)-2=19 vl (5)=min{ vl (7)-8,vl (8)-4}=7 vl (4)= vl (7)-6=15 vl (3)=min{ vl (5)-3, vl (6)-5}=4 vl (2)=min{ vl (4)-2, vl (5)-1}=6 vl (1)=min{vl (2)-3, vl (3)-4}=0 a11=7 a8=8 a9=4 a12=4 a15=6 a13=10 a6=5 a10=2 a14=1 a7=6 a2=4 a1=3 a3=2 a4=1 a5=3 V1 V2 V5 V3 V4 V6 V7 V8 V9 V10 V11 2018年11月13日 60

61 3. 求出活动ai的最早开始时间e[i]和最迟开始时间l[i]。
活动a e (1)=ve (1)= l (1)=vl (2) -3 =3 活动a e (2)=ve (1)= l (2)=vl (3) - 4=0 活动a e (3)=ve (2)= l (3)=vl (4) - 2=13 活动a e (4)=ve (2)= l (4)=vl (5) - 1=6 活动a e (5)=ve (3)= l (5)=vl (5) - 3=4 活动a e (6)=ve (3)= l (6)=vl (6) - 5=14 活动a e (7)=ve (4)= l (7)=vl (7) - 6=15 活动a e (8)=ve (5)= l (8)=vl (7) - 8=13 活动a e (9)=ve (5)= l (9)=vl (8) - 4=7 活动a e (10)=ve (6)= l (10)=vl (9) - 2=19 活动a e (11)=ve (7)= l (11)=vl (11) - 7=21 活动a e (12)=ve (8)= l (12)=vl (10) - 4=18 活动a e (13)=ve (8)= l (13)=vl (9) - 10=11 活动a e (14)=ve (9)= l (14)=vl (10) -1=21 活动a e (15)=ve (10)= l (15)=vl (11) -6 =22 2018年11月13日 61

62 Ve Vl e[i] l[i] 0 0 3 3 4 4 5 7 3 0 13 6 4 14 15 13 e[i] l[i]
a11=7 a8=8 a9=4 a12=4 a15=6 a13=10 a6=5 a10=2 a14=1 a7=6 a2=4 a1=3 a3=2 a4=1 a5=3 V1 V2 V5 V3 V4 V6 V7 V8 V9 V10 V11 顶点 Ve Vl 9 10 11 3 4 5 7 9 15 11 21 22 28 6 4 15 7 19 21 11 22 28 e[i] l[i] 活动 活动 e[i] l[i] 2018年11月13日 62

63 比较e[i]=l[i]的值可判断出a2,a5,a9,a13,a14,a15是关键活动，关键路径如图。
V1 V5 V3 V8 V9 V10 V11 关键路径长度=28 2018年11月13日 63

64 3．掌握各种实际应用实现思想、时间复杂度的分析方法。
小 结 1．深刻理解图的定义和相关术语 。 2．理解图的存储存储； l         用图的存储存储实现图的遍历； 求解最小生成树、 拓扑排序、最短路径、 关键路径等实际应用 3．掌握各种实际应用实现思想、时间复杂度的分析方法。 2018年11月13日 64