《数据结构用C语言描述》第七章

1、数据结构用C语言描述第七章 v图的基本概念图的基本概念 v图的存储结构图的存储结构 v图的遍历图的遍历 v图的连通性问题图的连通性问题 v最小生成树最小生成树 v最短路径最短路径 v活动网络活动网络 第七章第七章 图图 数据结构用C语言描述第七章 图的基本概念图的基本概念 图定义图定义 图是由顶点集合图是由顶点集合(vertex)及顶点间的关及顶点间的关 系集合组成的一种数据结构：系集合组成的一种数据结构： Graph( V, E ) 其中其中 V = x | x 某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合； E1 = (x, y) | x, y V 或或 E2 =

2、| x, y V 顶点顶点 v 的出度的出度是以是以 v 为为 始点的有向边的条数始点的有向边的条数, 记作记作 OD(v)。 n路径路径 在图在图 G(V, E) 中中, 若从顶点若从顶点 vi 出出 发发, 沿一些边经过一些顶点沿一些边经过一些顶点 vp1, vp2, , vpm，到达顶点，到达顶点vj。则称顶点序列。则称顶点序列 (vi vp1 vp2 . vpm vj) 为从顶点为从顶点vi 到顶点到顶点 vj 的路径。的路径。 它经过的边它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj) 应是属于应是属于E的边。的边。 数据结构用C语言描述第七章 顶点的出度顶

3、点的出度: : 以顶点以顶点v 为弧尾的弧的数目为弧尾的弧的数目; ; 顶点的入度顶点的入度: : 以顶点以顶点v v为为 弧头的弧的数目。弧头的弧的数目。 A BE CF 有向图有向图 顶点的度顶点的度D= =出度出度( (OD)+)+入度入度( (ID) ) D(B) =OD(B)+2ID(B) = 3 例如例如: : 数据结构用C语言描述第七章 n路径长度路径长度非带权图的路径长度是指此路径上边非带权图的路径长度是指此路径上边 的条数。带权图的路径长度是指路径上各边的权的条数。带权图的路径长度是指路径上各边的权 之和。之和。 n简单路径简单路径若路径上各顶点若路径上各顶点 v1,v2,.

4、,vm 均不均不 互互 相重复相重复, 则称这样的路径为简单路径。则称这样的路径为简单路径。 n简单回路简单回路 若路径上第一个顶点若路径上第一个顶点 v1 与最后一个与最后一个 顶点顶点vm 重合重合, 则称这样的路径为回路或环。则称这样的路径为回路或环。 0 12 3 0 12 3 0 12 3 数据结构用C语言描述第七章 A BE CF 如如: :从从A A到到F F长度为长度为 3 的路径的路径A,B,C,F 数据结构用C语言描述第七章 n连通图与连通分量连通图与连通分量 在无向图中在无向图中, 若从若从 顶点顶点v1到顶点到顶点v2有路径有路径, 则称顶点则称顶点v1与与v2是是 连

5、通的。如果图中任意一对顶点都是连通连通的。如果图中任意一对顶点都是连通 的的, 则称此图是连通图。非连通图的极大则称此图是连通图。非连通图的极大 连通子图叫做连通分量。连通子图叫做连通分量。 n强连通图与强连通分量强连通图与强连通分量在有向图中在有向图中, 若对于每一对顶点若对于每一对顶点vi和和vj, 都存在一条从都存在一条从vi 到到vj和从和从vj到到vi的路径的路径, 则称此图是强连通则称此图是强连通 图。非强连通图的极大强连通子图叫做强图。非强连通图的极大强连通子图叫做强 连通分量。连通分量。 数据结构用C语言描述第七章 无向图无向图,若图中任意两若图中任意两 个顶点之间都有路径相个

6、顶点之间都有路径相 通，则称此图为连通图通，则称此图为连通图; 若无向图为非连通图，若无向图为非连通图， 则图中各个极大连通子则图中各个极大连通子 图称作此图的连通分量图称作此图的连通分量。 B A C D F E B A C D F E 数据结构用C语言描述第七章 有向图有向图,若任意两个顶点之间都存在一条有向路若任意两个顶点之间都存在一条有向路 径，则称此有向图为强连通图径，则称此有向图为强连通图。 否则，其各个强连通子图称作它的强连通分量否则，其各个强连通子图称作它的强连通分量。 A BE CF A BE CF 数据结构用C语言描述第七章 生成树生成树: :假设一个连通图有假设一个连通图

7、有 n 个顶点和个顶点和 e 条边，条边， 其中其中 n-1 条边和条边和 n 个顶点构成一个极小连通子个顶点构成一个极小连通子 图，称该极小连通子图为此连通图的生成树图，称该极小连通子图为此连通图的生成树。 在极小连通子图中增加一条边，则一定有环。极小连通子图中增加一条边，则一定有环。 在极小连通子图中去掉一条边，则成为非连通极小连通子图中去掉一条边，则成为非连通 图。图。 B A C D F E B A C D F E 数据结构用C语言描述第七章 有有n个顶点，个顶点，n-1条边的图必定是生成树吗？条边的图必定是生成树吗？ 对非连通图，则称由各个连通分量的生成对非连通图，则称由各个连通分量

8、的生成 树的集合为此非连通图的生成森林树的集合为此非连通图的生成森林。 BA C D FE B A C D F E 数据结构用C语言描述第七章 图的存储结构图的存储结构 n在图的邻接矩阵表示中，有一个记录各个在图的邻接矩阵表示中，有一个记录各个 顶点信息的顶点表，还有一个表示各个顶顶点信息的顶点表，还有一个表示各个顶 点之间关系的邻接矩阵。点之间关系的邻接矩阵。 n设图设图 A = (V, E)是一个有是一个有 n 个顶点的图个顶点的图, 图图 的邻接矩阵是一个二维数组的邻接矩阵是一个二维数组 A.edgenn， 定义：定义： 邻接矩阵邻接矩阵 (Adjacency Matrix) , ),(

9、 , , . 否否则则 或或若若 0 1 A EjiEji jiEdge 数据结构用C语言描述第七章 n无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的; n有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。 0 12 3 0101 1010 0101 1010 A.edge 0 1 2 000 101 010 A.edge 数据结构用C语言描述第七章 n在有向图中在有向图中, 统计第统计第 i 行行 1 的个数可得顶点的个数可得顶点 i 的出度，统计第的出度，统计第 j 列列 1 的个数可得顶点的个数可得顶点 j 的入度。的入度。 n在无向图中在无向图中, 统计第统计第 i 行

10、行 (列列) 1 的个数可得的个数可得 顶点顶点i 的度。的度。 数据结构用C语言描述第七章 1 8 6 32 9 5 4 2 0 3 1 06 8053 290 410 A.edge 网络的邻接矩阵网络的邻接矩阵 ji ji,ji,ji ji,ji,jiji ji 若若 或或且且若若 或或且且若若 , )(, )(),( 0 EE EEW A.edge 数据结构用C语言描述第七章 #define e 8 /边条数边条数 #define n 6 /顶点个数顶点个数 typedef char Vextype; /顶点数据类型顶点数据类型 typedef float adjtype; /边上权值类

11、型边上权值类型 typedef struct Vextype vexsn; /顶点表顶点表 adjtype arcsnn; /邻接矩阵邻接矩阵, 可视为边之间的关系可视为边之间的关系 graph; 用邻接矩阵表示的结构定义用邻接矩阵表示的结构定义 数据结构用C语言描述第七章 下面给出建立一个无向网络的算法下面给出建立一个无向网络的算法 CREATGRAPH( graph *ga ) int i, j, k ; float w ; for ( i=0 ; ivexsi=getchar( ); for ( i=0 ; in ; i+ ) for ( j=0 ; jarcsij=0 ; for (

12、k=0 ; karcsij=w; ga-ji=w; 数据结构用C语言描述第七章 邻接表邻接表 (Adjacency List) 邻接表邻接表:是图的一种链式存储结构。是图的一种链式存储结构。 弧的结点结构弧的结点结构 adjvex; / 该弧所指向的顶点的位置该弧所指向的顶点的位置 nextarc;/ 指向下一条弧指针指向下一条弧指针 info; / 该弧相关信息的指针该弧相关信息的指针 adjvex nextarc info 顶点的结点结构顶点的结点结构 data firstarc data; / 顶点信息顶点信息 firstarc; /指向第一条依附该顶点的弧指向第一条依附该顶点的弧 数据

13、结构用C语言描述第七章 无向图的邻接表无向图的邻接表 同一个顶点发出的边链接在同一个边链表同一个顶点发出的边链接在同一个边链表 中，每一个链结点代表一条边中，每一个链结点代表一条边(边结点边结点), 结结 点中有另一顶点的下标点中有另一顶点的下标 dest 和指针和指针 link。 A BC D data link A B C D 0 1 2 3 dest linkdest link 13 02 1 0 数据结构用C语言描述第七章 有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表 A B C data adj A B C 0 1 2 dest link dest link 邻接表邻接表 (出边

14、表出边表) data adj A B C 0 1 2 dest link 逆邻接表逆邻接表 (入边表入边表) 1 02 0 1 1 数据结构用C语言描述第七章 n网络网络 (带权图带权图) 的邻接表的邻接表 B A C D 6 9 52 8 data adj A B C D 0 1 2 3 dest cost link 1 53 6 2 8 3 2 1 9 (出边表出边表)(顶点表顶点表) 数据结构用C语言描述第七章 图的邻接表存储表示图的邻接表存储表示 #define MAX_VERTEX_NUM 20 typedef struct Node int adjvex; / 该弧所指向的顶点的位

15、置该弧所指向的顶点的位置 struct Node *next;/ 指向下一条弧指针指向下一条弧指针 InfoType *info; / 该弧相关信息的指针该弧相关信息的指针 edgeNode; typedef struct Vextype vertex; / 顶点信息顶点信息 edgeNode *link; / 指向第一条依附该顶点的弧指向第一条依附该顶点的弧 VexNode; VexNodeMAX_VERTEX_NUM; 数据结构用C语言描述第七章 邻接表的构造算法邻接表的构造算法 void CREATADJLIST(vexnode ga ) int i, j, k ; edgenode *

16、s ; for ( i = 0; i n; i+) gai.vertex=getchar( ); /输入顶点信息输入顶点信息 gai.link = NULL; for ( k = 0; k -adjvex= j; s-next = gai.link; 数据结构用C语言描述第七章 gai-link = = s; s=malloc(sizeof(edgenode); s-adjvex = i; s-next= gaj.link; gaj-link = = s; 数据结构用C语言描述第七章 图的遍历图的遍历 n从图中某一顶点出发访遍图中所有的顶点，从图中某一顶点出发访遍图中所有的顶点， 且使每个顶点

17、仅被访问一次，这一过程就且使每个顶点仅被访问一次，这一过程就 叫做图的遍历叫做图的遍历 (Traversing Graph)。 n图中可能存在回路，且图的任一顶点都可图中可能存在回路，且图的任一顶点都可 能与其它顶点相通，在访问完某个顶点之能与其它顶点相通，在访问完某个顶点之 后可能会沿着某些边又回到了曾经访问过后可能会沿着某些边又回到了曾经访问过 的顶点。的顶点。 n为了避免重复访问，可设置一个标志顶点为了避免重复访问，可设置一个标志顶点 是否被访问过的辅助数组是否被访问过的辅助数组 visited 。 数据结构用C语言描述第七章 n辅助数组辅助数组 visited 的初始状态为的初始状态为

18、 0, 在图在图 的遍历过程中的遍历过程中, 一旦某一个顶点一旦某一个顶点 i 被访问被访问, 就立即让就立即让 visited i 为为 1, 防止它被多次访防止它被多次访 问。问。 n两种图的遍历方法两种图的遍历方法: u深度优先搜索深度优先搜索 DFS (Depth First Search) u广度优先搜索广度优先搜索 BFS (Breadth First Search) 数据结构用C语言描述第七章 深度优先搜索深度优先搜索DFS ( Depth First Search ) n深度优先搜索过程深度优先搜索过程 6 7 A CD E G B FIH A CD E G B FIH 123

19、 45 89 123 45 6 7 89 前进 回退 深度优先生成树深度优先生成树 数据结构用C语言描述第七章 nDFS 在访问图中某一起始顶点在访问图中某一起始顶点 v 后后, 由由 v 出出 发发, 访问它的任一邻接顶点访问它的任一邻接顶点 w1; 再从再从 w1 出发出发, 访问与访问与 w1邻邻 接但还没有访问过的顶点接但还没有访问过的顶点 w2; 然后再从然后再从 w2 出发出发, 进行类似的访问进行类似的访问, 如此如此 进行下去进行下去, 直至到达所有的邻接顶点都被访直至到达所有的邻接顶点都被访 问过的顶点问过的顶点 u 为止。接着为止。接着, 退回一步退回一步, 退到退到 前一

20、次刚访问过的顶点前一次刚访问过的顶点, 看是否还有其它没看是否还有其它没 有被访问的邻接顶点。如果有有被访问的邻接顶点。如果有, 则访问此顶则访问此顶 点点, 之后再从此顶点出发之后再从此顶点出发, 进行与前述类似进行与前述类似 的访问的访问; 如果没有如果没有, 就再退回一步进行搜索。就再退回一步进行搜索。 重复上述过程重复上述过程, 直到连通图中所有顶点都被直到连通图中所有顶点都被 访问过为止。访问过为止。 数据结构用C语言描述第七章 图的深度优先搜索算法图的深度优先搜索算法 int visitedn; graph g; void DFS ( int i ) int j ; for ( j

21、 = 0; j n; j+ ) visited j = 0; /访问数组访问数组 visited 初始化初始化 printf(“node:%cn”,g.vexsi); visitedi=1; for ( j= 0; jadjvex ) DFSL (p-adjvex); /若顶点若顶点 p未访问过未访问过, 递归访问顶点递归访问顶点 p p=p-next; /取顶点取顶点 i排在排在 p后的下一个邻接顶点后的下一个邻接顶点 数据结构用C语言描述第七章 广度优先搜索广度优先搜索BFS ( Breadth First Search ) n广度优先搜索过程广度优先搜索过程 A CD E G B FIH

22、 A CD E G B FH 12 34 5 6 7 89 12 34 5 6 7 89 广度优先生成树广度优先生成树 I 数据结构用C语言描述第七章 nBFS在访问了起始顶点在访问了起始顶点 v 之后之后, 由由 v 出发出发, 依依 次访问次访问 v 的各个未被访问过的邻接顶点的各个未被访问过的邻接顶点 w1, w2, , wt, 然后再顺序访问然后再顺序访问 w1, w2, , wt 的的 所有还未被访问过的邻接顶点。再从这些访所有还未被访问过的邻接顶点。再从这些访 问过的顶点出发，再访问它们的所有还未被问过的顶点出发，再访问它们的所有还未被 访问过的邻接顶点，访问过的邻接顶点， 如此做

23、下去，直到如此做下去，直到 图中所有顶点都被访问到为止。图中所有顶点都被访问到为止。 n广度优先搜索是一种分层的搜索过程广度优先搜索是一种分层的搜索过程, 每向每向 前走一步可能访问一批顶点前走一步可能访问一批顶点, 不像深度优先不像深度优先 搜索那样有往回退的情况。因此搜索那样有往回退的情况。因此, 广度优先广度优先 搜索不是一个递归的过程。搜索不是一个递归的过程。 数据结构用C语言描述第七章 n为了实现逐层访问为了实现逐层访问, 算法中使用了一个队列算法中使用了一个队列, 以记忆正在访问的这一层和下一层的顶点以记忆正在访问的这一层和下一层的顶点, 以便于向下一层访问。以便于向下一层访问。

24、n为避免重复访问为避免重复访问, 需要一个辅助数组需要一个辅助数组 visited ，给被访问过的顶点加标记。，给被访问过的顶点加标记。 图的广度优先搜索算法图的广度优先搜索算法 void DFS( int k ) int i ,j ; SETNULL(Q); printf(“%cn”,g.vexsk); visitedk=1; ENQUEUE(Q,k); while ( ! EMPTY(Q) ) i=DEQUEUE(Q); 数据结构用C语言描述第七章 for(j=0 ;jadjvex) printf(“%cn”,g1p-adjvex.vertex); visitedp-sdjvex=1; E

25、NQUEUE(Q,p-adjvex); p=p-next; 数据结构用C语言描述第七章 连通分量连通分量 (Connected component) n当无向图为非连通图时当无向图为非连通图时, 从图中某一顶点出从图中某一顶点出 发发, 利用深度优先搜索算法或广度优先搜索利用深度优先搜索算法或广度优先搜索 算法不可能遍历到图中的所有顶点算法不可能遍历到图中的所有顶点, 只能访只能访 问到该顶点所在的最大连通子图问到该顶点所在的最大连通子图(连通分量连通分量) 的所有顶点。的所有顶点。 n若从无向图的每一个连通分量中的一个顶若从无向图的每一个连通分量中的一个顶 点出发进行遍历点出发进行遍历, 可

26、求得无向图的所有连可求得无向图的所有连 通分量。通分量。 图的连通性问题图的连通性问题 数据结构用C语言描述第七章 n求连通分量的算法需要对图的每一个顶点求连通分量的算法需要对图的每一个顶点 进行检测：若已被访问过，则该顶点一定进行检测：若已被访问过，则该顶点一定 是落在图中已求得的连通分量上；若还未是落在图中已求得的连通分量上；若还未 被访问，则从该顶点出发遍历图，可求得被访问，则从该顶点出发遍历图，可求得 图的另一个连通分量。图的另一个连通分量。 n对于非连通的无向图，所有连通分量的生对于非连通的无向图，所有连通分量的生 成树组成了非连通图的生成森林。成树组成了非连通图的生成森林。 数据结

27、构用C语言描述第七章 A CDEIB FOG H J NML K 非连通无向图的三个连通分量非连通无向图的三个连通分量 AHK CDEIB FOGJ NML 非连通图的连通分量的极小连通子图非连通图的连通分量的极小连通子图 数据结构用C语言描述第七章 非连通图的遍历算法非连通图的遍历算法 TRAVER（ ） int i； for (i=0; in; i+ ) visitedi=FALSE; for (i=0; in; i+ ) if (!visitedi ) DFS( i ); printf ( “comp end n” ); 数据结构用C语言描述第七章 重连通分量重连通分量 (Biconne

28、cted Component) n在无向连通图在无向连通图G中中, 当且仅当删去当且仅当删去G中的顶中的顶 点点v及所有依附于及所有依附于v的所有边后的所有边后, 可将图分割可将图分割 成两个或两个以上的连通分量，则称顶点成两个或两个以上的连通分量，则称顶点v 为关节点。为关节点。 n没有关节点的连通图叫做重连通图。没有关节点的连通图叫做重连通图。 n在重连通图上在重连通图上, 任何一对顶点之间至少存在任何一对顶点之间至少存在 有两条路径有两条路径, 在删去某个顶点及与该顶点相在删去某个顶点及与该顶点相 关联的边时关联的边时, 也不破坏图的连通性。也不破坏图的连通性。 n一个连通图一个连通图G

29、如果不是重连通图，那么它可如果不是重连通图，那么它可 以包括几个重连通分量。以包括几个重连通分量。 数据结构用C语言描述第七章 n在一个无向连通图在一个无向连通图G中中, 重连通分量可以利重连通分量可以利 用深度优先生成树找到。用深度优先生成树找到。 n在图中各顶点旁标明的深度优先数在图中各顶点旁标明的深度优先数, 给出进给出进 行深度优先搜索时各顶点访问的次序。行深度优先搜索时各顶点访问的次序。 n深度优先生成树的根是关节点的充要条件深度优先生成树的根是关节点的充要条件 是它至少有两个子女。是它至少有两个子女。 数据结构用C语言描述第七章 A B CD E F G H IJA B CD E

30、F G H J A B CD E F G H JI I 1 2 3 4 5 6 7 8 910 根有两根有两 个子女个子女 数据结构用C语言描述第七章 A B CD E F G H IJ A B H I DF B CD E F G H 连通图和它的连通分量连通图和它的连通分量 数据结构用C语言描述第七章 最小生成树最小生成树 ( minimum cost spanning tree ) n使用不同的遍历图的方法，可以得到不同使用不同的遍历图的方法，可以得到不同 的生成树；从不同的顶点出发，也可能得的生成树；从不同的顶点出发，也可能得 到不同的生成树。到不同的生成树。 n按照生成树的定义，按照生

31、成树的定义，n 个顶点的连通网络个顶点的连通网络 的生成树有的生成树有 n 个顶点、个顶点、n-1 条边。条边。 n构造最小生成树的准则构造最小生成树的准则 n必须使用且仅使用该网络中的必须使用且仅使用该网络中的n- -1 条边条边 来联结网络中的来联结网络中的 n 个顶点；个顶点； n不能使用产生回路的边；不能使用产生回路的边； n各边上的权值的总和达到最小。各边上的权值的总和达到最小。 数据结构用C语言描述第七章 普里姆普里姆(Prim)算法算法 n普里姆算法的基本思想：普里姆算法的基本思想： 从连通网络从连通网络 N = V, E 中的某一顶点中的某一顶点 u0 出出 发发, 选择与它关

32、联的具有最小权值的边选择与它关联的具有最小权值的边 ( u0, v ), 将其顶点加入到生成树顶点集合将其顶点加入到生成树顶点集合U中。中。 以后每一步从一个顶点在以后每一步从一个顶点在 U 中中,而另一个而另一个 顶点不在顶点不在 U 中的各条边中选择权值最小的中的各条边中选择权值最小的 边边(u, v), 把它的顶点加入到集合把它的顶点加入到集合 U 中。如中。如 此继续下去此继续下去, 直到网络中的所有顶点都加入直到网络中的所有顶点都加入 到生成树顶点集合到生成树顶点集合 U 中为止。中为止。 n采用邻接矩阵作为图的存储表示。采用邻接矩阵作为图的存储表示。 数据结构用C语言描述第七章 2

33、525 10 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 5 0 4 6 1 3 25 0 4 6 1 3 2 10 原图 (a) (b) 5 0 4 6 1 3 2 10 (c) (d) (e) (f) 5 0 4 6 1 3 2 10 22 12 5 0 4 6 1 2 10 25 14 22 16 12 3 25 22 12 数据结构用C语言描述第七章 n在构造过程中，还设置了两个辅助数组：在构造过程中，还设置了两个辅助数组： u lowcost 存放生成树顶点集合内顶点到存放生成树顶点集合内顶点到 生成树外各顶点的各边上的当前最小权值；生成树外各顶点的各

34、边上的当前最小权值； u nearvex 记录生成树顶点集合外各顶点记录生成树顶点集合外各顶点 距离集合内哪个顶点最近距离集合内哪个顶点最近(即权值最小即权值最小)。 n例子例子 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 0241814 02510 2425022 1822012 12016 1416028 10280 数据结构用C语言描述第七章 n若选择从顶点若选择从顶点0出发，即出发，即u0 = 0，则两个辅，则两个辅 助数组的初始状态为：助数组的初始状态为： n然后反复做以下工作：然后反复做以下工作： u 在在 lowcost 中选择中选择 nea

35、rvexi - -1 int * nearvex = new intNumVertices; for ( int i = 0; i NumVertices; i+ ) lowcosti = G.Edgeui; /Vu到各点代价到各点代价 nearvexi = u; /及最短带权路径及最短带权路径 数据结构用C语言描述第七章 nearvexu = - -1; /加到生成树顶点集合加到生成树顶点集合 int k = 0; /存放最小生成树结点的变量存放最小生成树结点的变量 for ( i = 0; i G.n; i+ ) if ( i != u ) /循环循环n-1次次, 加入加入n-1条边条边

36、EdgeData min = MaxValue; int v = 0; for ( int j = 0; j NumVertices; j+ ) if ( nearvexj != - -1 min = lowcostj; /求生成树外顶点到生成树内顶点具有最求生成树外顶点到生成树内顶点具有最 /小权值的边小权值的边, v是当前具最小权值的边是当前具最小权值的边 数据结构用C语言描述第七章 if ( v ) /v=0表示再也找不到要求顶点表示再也找不到要求顶点 Tk.tail = nearvexv; /选边加入生成树选边加入生成树 Tk.head = v; Tk+.cost = lowcostv

37、; nearvexv = - -1; /该边加入生成树标记该边加入生成树标记 for ( j = 0; j G.n; j+ ) if ( nearvexj != - -1 /修改修改 nearvexj = v; 数据结构用C语言描述第七章 /循环循环n-1次次, 加入加入n-1条边条边 n分析以上算法分析以上算法, 设连通网络有设连通网络有 n 个顶点个顶点, 则则 该算法的时间复杂度为该算法的时间复杂度为 O(n2), 它适用于边它适用于边 稠密的网络。稠密的网络。 n注意：当各边有相同权值时，由于选择的随注意：当各边有相同权值时，由于选择的随 意性，产生的生成树可能不唯一。当各边的意性，产

38、生的生成树可能不唯一。当各边的 权值不相同时，产生的生成树是唯一的。权值不相同时，产生的生成树是唯一的。 数据结构用C语言描述第七章 活动网络活动网络 (Activity Network) n计划、施工过程、生产流程、程序流程等都计划、施工过程、生产流程、程序流程等都 是是“工程工程”。除了很小的工程外，一般都把。除了很小的工程外，一般都把 工程分为若干个叫做工程分为若干个叫做“活动活动”的子工程。完的子工程。完 成了这些活动，这个工程就可以完成了。成了这些活动，这个工程就可以完成了。 n例如，计算机专业学生的学习就是一个工程，例如，计算机专业学生的学习就是一个工程， 每一门课程的学习就是整个

39、工程的一些活动。每一门课程的学习就是整个工程的一些活动。 其中有些课程要求先修课程，有些则不要求。其中有些课程要求先修课程，有些则不要求。 这样在有的课程之间有领先关系，有的课程这样在有的课程之间有领先关系，有的课程 可以并行地学习。可以并行地学习。 用顶点表示活动的网络用顶点表示活动的网络 (AOV网络网络) 数据结构用C语言描述第七章 C1 高等数学高等数学 C2 程序设计基础程序设计基础 C3 离散数学离散数学 C1, C2 C4 数据结构数据结构 C3, C2 C5 高级语言程序设计高级语言程序设计 C2 C6 编译方法编译方法 C5, C4 C7 操作系统操作系统 C4, C9 C8

40、 普通物理普通物理 C1 C9 计算机原理计算机原理 C8 课程代号课程代号 课程名称课程名称 先修课程先修课程 数据结构用C语言描述第七章 学生课程学习工程图学生课程学习工程图 C8 C3 C5 C4 C9 C6 C7 C1 C2 数据结构用C语言描述第七章 n可以用有向图表示一个工程。在这种有向可以用有向图表示一个工程。在这种有向 图中，用顶点表示活动，用有向边图中，用顶点表示活动，用有向边 表示活动表示活动Vi 必须先于活动必须先于活动Vj 进行。这种有进行。这种有 向图叫做顶点表示活动的向图叫做顶点表示活动的AOV网络网络 (Activity On Vertices)。 n在在AOV网

41、络中不能出现有向回路网络中不能出现有向回路, 即有向即有向 环。如果出现了有向环，则意味着某项活环。如果出现了有向环，则意味着某项活 动应以自己作为先决条件。动应以自己作为先决条件。 n因此，对给定的因此，对给定的AOV网络，必须先判断它网络，必须先判断它 是否存在有向环。是否存在有向环。 数据结构用C语言描述第七章 n检测有向环的一种方法是对检测有向环的一种方法是对AOV网络构造网络构造 它的拓扑有序序列。即将各个顶点它的拓扑有序序列。即将各个顶点 (代表各代表各 个活动个活动)排列成一个线性有序的序列，使得排列成一个线性有序的序列，使得 AOV网络中所有应存在的前驱和后继关系网络中所有应存

42、在的前驱和后继关系 都能得到满足。都能得到满足。 n这种构造这种构造AOV网络全部顶点的拓扑有序序网络全部顶点的拓扑有序序 列的运算就叫做拓扑排序。列的运算就叫做拓扑排序。 n如果通过拓扑排序能将如果通过拓扑排序能将AOV网络的所有顶网络的所有顶 点都排入一个拓扑有序的序列中点都排入一个拓扑有序的序列中, 则该网络则该网络 中必定不会出现有向环。中必定不会出现有向环。 数据结构用C语言描述第七章 n如果如果AOV网络中存在有向环，此网络中存在有向环，此AOV网络网络 所代表的工程是不可行的。所代表的工程是不可行的。 n例如例如, 对学生选课工程图进行拓扑排序对学生选课工程图进行拓扑排序, 得得

43、 到的拓扑有序序列为到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7 或或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 C8 C3 C5 C4 C9 C6 C7 C1 C2 数据结构用C语言描述第七章 拓扑排序的方法拓扑排序的方法 输入输入AOV网络。令网络。令 n 为顶点个数。为顶点个数。 在在AOV网络中选一个没有直接前驱的顶点网络中选一个没有直接前驱的顶点, 并输出之并输出之; 从图中删去该顶点从图中删去该顶点, 同时删去所有它发出同时删去所有它发出 的有向边的有向边; 重复以上重复以上 、

44、步步, 直到直到 全部顶点均已输出，拓扑有序序列形成，全部顶点均已输出，拓扑有序序列形成， 拓扑排序完成；或拓扑排序完成；或 图中还有未输出的顶点图中还有未输出的顶点, 但已跳出处理但已跳出处理 循环。说明图中还剩下一些顶点循环。说明图中还剩下一些顶点, 它们都它们都 有直接前驱。这时网络中必存在有向环。有直接前驱。这时网络中必存在有向环。 数据结构用C语言描述第七章 C0C1C2 C3C4C5 拓扑排序的过程拓扑排序的过程 (a) 有向无环图有向无环图 C2 C5 C1C0 C3 (b) 输出顶点输出顶点C4 C1C2 C5C3 (c) 输出顶点输出顶点C0 C4 C0C2 C5 C1 C3

45、 (d) 输出顶点输出顶点C3 数据结构用C语言描述第七章 C1C2 C5 (e) 输出顶点输出顶点C2 C5 C1 (f) 输出顶点输出顶点C1 C5 (g) 输出顶点输出顶点C5 最后得到的拓扑有序序列为最后得到的拓扑有序序列为 C4 , C0 , C3 , C2 , C1 , C5 。它满足图中给出的所有前驱和后继关系，。它满足图中给出的所有前驱和后继关系， 对于本来没有这种关系的顶点，如对于本来没有这种关系的顶点，如C4和和C2，也，也 排出了先后次序关系。排出了先后次序关系。 (h) 拓扑排序完成拓扑排序完成 数据结构用C语言描述第七章 AOV网络及其邻接表表示网络及其邻接表表示 C

46、0C1C2 C3C4C5 C0 C1 C2 C3 0 C4 C5 0 0 1 2 3 4 5 count data adj 1 3 0 1 0 3 1 dest link 3 0 5 1 5 0 0 1 5 0 数据结构用C语言描述第七章 n在邻接表中增设一个数组在邻接表中增设一个数组count ，记录各，记录各 顶点入度。入度为零的顶点即无前驱顶点。顶点入度。入度为零的顶点即无前驱顶点。 n在输入数据前在输入数据前, 顶点表顶点表VexList 和入度数组和入度数组 count 全部初始化。在输入数据时全部初始化。在输入数据时, 每输入每输入 一条边一条边, 就需要建立一个边结点就需要建立一

47、个边结点, 并将并将 它链入相应边链表中它链入相应边链表中, 统计入度信息：统计入度信息： EdgeNode * p = new EdgeNode; p-dest = k; /建立边结点建立边结点 p-link = G.VexListj.firstAdj; VexListj.firstAdj = p; /链入顶点链入顶点 j j 的边链表的前端的边链表的前端 countk+; /顶点顶点 k k 入度加一入度加一 数据结构用C语言描述第七章 n在算法中在算法中, 使用一个存放入度为零的顶点的使用一个存放入度为零的顶点的 链式栈链式栈, 供选择和输出无前驱的顶点。供选择和输出无前驱的顶点。 n拓

48、扑排序算法可描述如下：拓扑排序算法可描述如下： u建立入度为零的顶点栈建立入度为零的顶点栈; u当入度为零的顶点栈不空时当入度为零的顶点栈不空时, 重复执行重复执行 从顶点栈中退出一个顶点从顶点栈中退出一个顶点, 并输出之并输出之; 从从AOV网络中删去这个顶点和它发出网络中删去这个顶点和它发出 的边的边, 边的终顶点入度减一边的终顶点入度减一; 如果边的终顶点入度减至如果边的终顶点入度减至0, 则该顶点则该顶点 进入度为零的顶点栈进入度为零的顶点栈; u 如果输出顶点个数少于如果输出顶点个数少于AOV网络的顶点网络的顶点 个数个数, 则报告网络中存在有向环。则报告网络中存在有向环。 数据结构

49、用C语言描述第七章 拓扑排序的算法拓扑排序的算法 void TopologicalSort (AdjGraph G) Stack S; StackEmpty(S); int j; /入度为零的顶点栈初始化入度为零的顶点栈初始化 for ( int i = 0; i n; i+ ) /入度为零顶点入度为零顶点 if ( counti = 0 ) Push(S, i); /进栈进栈 for ( i = 0; i n; i+ ) /期望输出期望输出 n 个顶点个顶点 if ( StackEmpty(S) ) /中途栈空中途栈空,转出转出 cout “网络中有回路！网络中有回路！ endl; retu

50、rn; 数据结构用C语言描述第七章 else /继续拓扑排序继续拓扑排序 Pop( S, j ); /退栈退栈 cout j -dest; /另一顶点另一顶点 if ( -countk = 0 ) /顶点入度减一顶点入度减一 Push( S, k ); /顶点的入度减至零顶点的入度减至零, 进栈进栈 p = p-link; 数据结构用C语言描述第七章 用边表示活动的网络用边表示活动的网络(AOE网络网络) n如果在无有向环的带权有向图中如果在无有向环的带权有向图中, 用有向边用有向边 表示一个工程中的活动表示一个工程中的活动 (Activity), 用边上权用边上权 值表示活动持续时间值表示活

51、动持续时间 (Duration), 用顶点表用顶点表 示事件示事件 (Event), 则这样的有向图叫做用边则这样的有向图叫做用边 表示活动的网络表示活动的网络, 简称简称 AOE ( Activity On Edges ) 网络。网络。 nAOE网络在某些工程估算方面非常有用。网络在某些工程估算方面非常有用。 例如，可以使人们了解：例如，可以使人们了解： u完成整个工程至少需要多少时间完成整个工程至少需要多少时间(假设网假设网 络中没有环络中没有环)? 数据结构用C语言描述第七章 u为缩短完成工程所需的时间为缩短完成工程所需的时间, 应当加快哪应当加快哪 些活动些活动? n从源点到各个顶点从

52、源点到各个顶点, 以至从源点到汇点的有以至从源点到汇点的有 向路径可能不止一条。向路径可能不止一条。 这些路径的长度也这些路径的长度也 可能不同。可能不同。 完成不同路径的活动所需的时完成不同路径的活动所需的时 间虽然不同间虽然不同, 但只有各条路径上所有活动都但只有各条路径上所有活动都 完成了完成了, 整个工程才算完成。整个工程才算完成。 n因此因此, 完成整个工程所需的时间取决于从源完成整个工程所需的时间取决于从源 点到汇点的最长路径长度点到汇点的最长路径长度, 即在这条路径上即在这条路径上 所有活动的持续时间之和。这条路径长度最所有活动的持续时间之和。这条路径长度最 长的路径就叫做关键路

53、径长的路径就叫做关键路径(Critical Path)。 数据结构用C语言描述第七章 a9=6 1 3 2 4 a1=8 a2=12 5 6 78 a10=12 a8=18 a5=28 a6=8 a7=6 a3=14 a4=10 n要找出关键路径，必须找出要找出关键路径，必须找出关键活动关键活动, 即不即不 按期完成就会影响整个工程完成的活动。按期完成就会影响整个工程完成的活动。 n关键路径上的所有活动都是关键活动关键路径上的所有活动都是关键活动。因此。因此, 只要找到了关键活动只要找到了关键活动, 就可以找到关键路径。就可以找到关键路径。 例如例如, 下图就是一个下图就是一个AOE网。网。

54、数据结构用C语言描述第七章 定义几个与计算关键活动有关的量：定义几个与计算关键活动有关的量： 事件事件Vi 的最早可能开始时间的最早可能开始时间Ve(i) 是从源点是从源点V0 到顶点到顶点Vi 的最长路径长度。的最长路径长度。 事件事件Vi 的最迟允许开始时间的最迟允许开始时间Vli 是在保证汇点是在保证汇点Vn-1 在在Ven-1 时刻完成的前时刻完成的前 提下，事件提下，事件Vi 的允许的最迟开始时间。的允许的最迟开始时间。 活动活动ak 的最早可能开始时间的最早可能开始时间 ek 设活动设活动ak 在边在边上上, 则则ek是从源点是从源点 V0到顶点到顶点Vi 的最长路径长度。因此的最

55、长路径长度。因此, ek = Vei。 活动活动ak 的最迟允许开始时间的最迟允许开始时间 lk 数据结构用C语言描述第七章 lk是在不会引起时间延误的前提下是在不会引起时间延误的前提下, 该活该活 动允许的最迟开始时间。动允许的最迟开始时间。 lk = Vlj - dur()。 其中其中, dur()是完成是完成 ak 所需的时间。所需的时间。 时间余量时间余量 lk - ek 表示活动表示活动 ak 的最早可能开始时间和最迟允的最早可能开始时间和最迟允 许开始时间的时间余量。许开始时间的时间余量。lk = ek 表示活表示活 动动 ak 是没有时间余量的关键活动。是没有时间余量的关键活动。

56、 n为找出关键活动为找出关键活动, 需要求各个活动的需要求各个活动的 ek 与与 lk，以判别是否，以判别是否 lk = ek。 数据结构用C语言描述第七章 n为求得为求得 ek与与 lk, 需要先求得从源点需要先求得从源点 V0 到到 各个顶点各个顶点 Vi 的的 Vei 和和 Vli。 n求求Vei的递推公式的递推公式 u 从从 Ve0 = 0 开始，向前递推开始，向前递推 S2, i = 1, 2, , n-1 S2 是所有指向是所有指向Vi 的有向边的有向边的集合。的集合。 u 从从Vln-1 = Ven-1开始，反向递推开始，反向递推 S1, i = n-2, n-3, , 0 S1

57、是所有源自是所有源自Vi的有向边的有向边的集合。的集合。 , ) ,( ij j VVdurjVemaxiVe , ) ,( ji j VVdurjVlminiVl 数据结构用C语言描述第七章 n这两个递推公式的计算必须分别在拓扑有序这两个递推公式的计算必须分别在拓扑有序 及逆拓扑有序的前提下进行。及逆拓扑有序的前提下进行。 n设活动设活动ak (k=1,2,e)在带权有向边在带权有向边 上上, 其持续时间用其持续时间用dur () 表示表示, 则有则有 ek = Vei； lk = Vlj - dur()；k = 1, 2, , e。 这样就得到计算关键路径的算法。这样就得到计算关键路径的算

58、法。 为了简化算法为了简化算法, 假定在求关键路径之前已经假定在求关键路径之前已经 对各顶点实现了拓扑排序对各顶点实现了拓扑排序, 并按拓扑有序的并按拓扑有序的 顺序对各顶点重新进行了编号。顺序对各顶点重新进行了编号。 数据结构用C语言描述第七章 1 3 2 4 a1=8 a2=12 5 6 78 a10=12 a9=6 a8=18 a5=28 a6=8 a7=6 a3=14 a4=10 Ve Vl 1 2 3 4 5 6 7 8 0 8 12 22 28 40 46 58 0 8 12 22 28 40 46 58 e l 0 0 8 12 12 22 22 28 40 46 0 0 8 1

59、2 12 32 22 28 40 46 1 2 3 4 5 6 7 8 9 10 数据结构用C语言描述第七章 事件事件 Vei Vli V0 0 0 V1 6 6 V2 4 6 V3 5 8 V4 7 7 V5 7 10 V6 16 16 V7 14 14 V8 18 18 边边 活动活动 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 e 0 0 0 6 4 5 7 7 7 16 14 l 0 2 3 6 6 8 7 7 10 16 14 l - e 0 2 3 0 2 3 0 0 3 0 0 关键关键 是是 是是 是是 是是 是是 是是 数据结构用C语言描述第七章 v

60、oid graph:CriticalPath ( ) /在此算法中需要对邻接表中单链表的结点加以在此算法中需要对邻接表中单链表的结点加以 /修改修改, 在各结点中增加一个在各结点中增加一个int域域 cost, 记录该结记录该结 /点所表示的边上的权值点所表示的边上的权值。 int i, j; int p, k; int e, l; Ve = new intn; Vl = new intn; for ( i = 0; i n; i+ ) Vei = 0;/初始化初始化 for ( i = 0; i n; i+ ) /顺向计算事件最早允许开始时间顺向计算事件最早允许开始时间 Edge *p =