第7章 图(new).ppt

1、第7章 图,图（Graph）是一种比线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构，用来描述元素之间“多对多”的关系。,在线性结构中，结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。 在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。 在图结构中，对结点（图中常称为顶点）的前趋和后继个数不加限制的，即结点之间的关系是任意的。,本章内容,一、图的概念 二、图的存储结构 三、图的遍历 四、图的连通性问题 五、有向无环图及其应

2、用 六、最短路经,一、图的概念,（1）图的定义 （2）图的基本术语,一、图的概念,（1）图的定义 图（Graph）是由一个顶点集 V 和一个边集 E 构成的数据结构：G = ( V, E ) V ：是顶点的有穷非空集合，也叫图的顶点集，表示为V(G)； E ：是顶点之间关系的有穷集合，即边（或弧）的有限集合，也叫做边(edge)集，表示为V(E)。可为空集。,一、图的概念,（2）图的基本术语 有向图与无向图 有向图：边用表示，且x与y是有序的。 a. 有向图中的边称为“弧” b. x弧尾或初始点 y弧头或终端点 无向图：边用(x, y) 表示，且顶x与 y是无序的。 注意：本章的图不考虑图中每

3、个顶点到自身的边或弧。,图(a)为无向图，其中G1的顶点集合和边集合分别为： V(G1)=1，2，3，4，5，6，7， E(G1)=(1，2)，(l，3)，(2，3)，(3，4)，(3，5)，(5，6)，(5，7)。 图(c)为有向图，其中G3的顶点集合和弧集合分别为 V(G3)=1，2，3，4，5，6， E(G3)=，,（2）图的基本术语,完全图、稀疏图、稠密图 完全图：具有最多边数的图 在具有n 个顶点图中： 有向图：最大弧数为 n(n-1) 无向图：最大边数为 n(n-1)/2 稀疏图：边数很少的图(enlogn) 稠密图：边数很多的图（接近完全图）,（2）图的基本术语,子图 设有两个图

4、G=(V,E)和G=(V,E)，若V是V的子集，即VV，且E是E的子集，即EE，则称G是G的子图。 例如： 图(b)是图(a)的子图，而图(c)不是图(a)的子图。,（2）图的基本术语,端点和邻接点 无向图：若存在一条边(i,j)，则称i和j为此边的两个端点，并称它们互为邻接点。称：边(i,j)与顶点i、j相关联。 有向图：若存在一条边，则称此边是顶点i的一条出边，同时也是顶点j的一条入边；称i和j分别为此边的起始端点(简称为起点)和终止端点(简称终点)。称：i邻接到j，j邻接自i；边(i,j)与顶点i、j相关联。,（2）图的基本术语,顶点的度：与顶点v相关的边或弧的数目称作顶点v的度。 无向

5、图：与顶点v相关的边的数目 有向图：顶点v的入度与出度之和。 入度ID(v) ：以顶点v为弧头的弧的数目； 出度OD(v) ：以顶点v为弧尾的弧的数目。 若一个图中有n个顶点和e条边，每个顶点的度为D(i)(1in)，则有：,（2）图的基本术语,路径、回路 路径：在一个图G=(V,E)中,从顶点vi到顶点vj的一条路径是一个顶点序列(vi,v1,v2,vm,vj)，若此图G是无向图，则边(vi,v1)，(v1,v2)，(vm-1,vm)，(vm,vj)属于E(G)；若此图是有向图，则，属于E(G)。 路径长度：一条路径上经过的边（或弧）的数目。,若一条路径上的起点与终点相同，则此路径被称为回路

6、（环）。 若一条路径上顶点不重复出现，则称此路径为简单路径。例：下图中，(v0,v2,v1)就是一条简单路径，其长度为2。 除起点与终点外，其他顶点不重复出现的回路被称为简单回路（简单环）。例：下图，(v0,v2,v1,v0)就是一条简单回路，其长度为3。,（2）图的基本术语,连通图、非连通图 在无向图G中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的。 若图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。,（2）图的基本术语,连通分量 P157 无向图G中的极大连通子图（用最多的边数来连通最多个顶点的子图）称为G的连通分量。 显然：任何连通图的连通分量只有一个，即本身，而非

7、连通图有多个连通分量。,（2）图的基本术语,强连通图、非强连通图 在有向图G中，若从顶点vi到顶点vj有路径，则称从vi到vj是连通的。 若图G中的任意两个顶点vi和vj都连通，即从vi到vj和从vj到vi都存在路径，则称图G是强连通图，否则称为非强连通图。 如：右边两个图都是强连通图。,（2）图的基本术语,强连通分量 P157 有向图G中的极大强连通子图称为G的强连通分量。显然，强连通图只有一个强连通分量，即本身，非强连通图有多个强连通分量。,(a)有向图G (b)图G的二个强连通分量,（2）图的基本术语,权、网 图中每一条边都可以附有一个对应的数值,这种与边相关的数值称为权。权可以表示从一

8、个顶点到另一个顶点的距离或花费的代价等。边上带有权的图称为带权图，也称作网，或网图。,（2）图的基本术语,（2）图的基本术语,有根图、图的根 有向图中，若从顶点v出发，有路径可以连通到图中其余各顶点，则称该有向图为有根图，顶点v称为图的根。,（2）图的基本术语,生成树、生成森林 生成树是连通图中的极小连通子图（用最少的边数来连通最多个顶点的子图） 。 n个顶点的生成树具有n-1条边。 在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的边所依附的两个顶点之间有了第二条路经。若生成树中减少任意一条边，则必然成为非连通的。,（2）图的基本术语,生成树、生成森林 非连通图的生成树组成一个

9、生成森林。 若非连通图中有n个顶点，m个连通分量，则生成森林由m棵生成树组成。,树和图的区别与联系,树型结构是图型结构的一个特例： 树是无简单回路的连通图； 是具有最少边的连通图。,图的基本操作,输入图G的顶点和边，建立图G。 在图G中，从顶点v出发深度优先遍历图G。 在图G中，从顶点v出发广度优先遍历图G。,二、图的存储结构,(1)图的数组存储表示(邻接矩阵表示法) (2)图的邻接表存储表示 (3)有向图的十字链表存储表示 (4)无向图的邻接多重表存储表示,(1)图的数组存储表示(邻接矩阵),数组表示法： 用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。用一维数

10、组存储图中顶点的信息，用二维数组（矩阵）表示图中各顶点之间的邻接关系，故数组表示法又称为邻接矩阵表示法。,(1)图的数组存储表示(邻接矩阵),假设图G（V，E）有n个确定的顶点，即Vv0,v1,vn-1，则表示G中各顶点相邻关系为一个nn的矩阵，矩阵的元素为： Aij=,1 vi到vj有边或弧 0 vi到vj无边或弧,有向图及其邻接矩阵,无向图及其邻接矩阵,(1)图的数组存储表示(邻接矩阵),无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不对称的。 在有向图中： 第 i 行 1 的个数就是顶点 i 的出度， 第 j 列 1 的个数就是顶点 j 的入度。 在无向图中： 第 i 行 (

11、列) 1 的个数就是顶点i 的度。,(1)图的数组存储表示(邻接矩阵),若G是带权图（网图），则邻接矩阵可定义为： Aij= 其中，wij表示边(vi,vj)或上的权值。,wij vi到vj有边或弧（i!=j） vi到vj无边或弧（i!=j） 0 主对角线上的元素,(1)图的数组存储表示(邻接矩阵),0 9 6 3 9 0 4 5 A 6 4 0 7 3 5 0 8 7 8 0,邻接矩阵的特点： (1)邻接矩阵表示法直观，易理解，算法简便，应用较广，特别适合于以顶点为主的运算。 (2)图的邻接矩阵表示是惟一的。 (3)无向图的邻接矩阵一定是一个对称矩阵。因此，按照压缩存储的思想，在具体存放邻接

12、矩阵时只需存放上(或下)三角形阵的元素即可。 (4)不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵，因此，当图的顶点较多时，可以采用三元组表的方法存储邻接矩阵。,(1)图的数组(邻接矩阵)存储表示,邻接矩阵的特点： (4)对于无向图，邻接矩阵的第i行(或第i列)非零元素(或非元素)的个数正好是第i个顶点的度。 (5)对于有向图，邻接矩阵的第i行(或第i列)非零元素(或非元素)的个数正好是第i个顶点的出度(或入度)。 (6)用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的

13、局限性。,数据结构类型定义： P148 无向图的建立： P149 对于稀疏图，其边或弧较少，邻接矩阵的非零元素较少，属稀疏矩阵，因此会造成一定存储空间的浪费。,(1)图的数组存储表示(邻接矩阵),(2)图的邻接表存储表示,邻接表表示法类似于树的孩子链表表示法。对图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。这个单链表就称为顶点vi的邻接表，再将所有点的邻接表表头放到数组中，就构成了图的邻接表。,(2)图的邻接表存储表示,邻接表(Adjacency List) ： 顶点表：用来存储顶点信息，用一维数组存

14、储。由顶点域（vexdata）和指向第一条邻接边的指针域（link）构成； 边表（邻接表）：用来存储依附于某个顶点的所有边（或弧）的信息，用单链表存储。由邻接点域(adjvex)和指向下一条邻接点的指针域(next)构成。对于带权图的边表需再增设一个存储边上信息（如权值等）的域（info）。,顶点域 边表头指针 顶点表,（a） 邻接表的结点结构,邻接点域 边上信息 指针域,（b）带权图的边表结构,邻接点域 指针域 边表（链表结点）,(2)图的邻接表存储表示,邻接表存储表示的定义如下： define MaxVerNum 100 /*最大顶点数为100*/ typedef struct node

15、/*边表结点*/ int adjvex; /*邻接点域*/ struct node * next; /*指向下一个邻接点的指针域*/ /*若要表示边上权值信息，则应增加一个数据域info*/ EdgeNode; typedef struct vnode /*顶点表结点*/ VertexType vexdata; /*顶点域*/ EdgeNode * link; /*边表头指针*/ VertexNode; typedef struct VertexNode adjlistMaxVertexNum; /*邻接表*/ int n,e; /*顶点数和边数*/ ALGraph; /*ALGraph是以邻

16、接表方式存储的图类型*/,(3)有向图的十字链表存储表示,十字链表（Orthogonal List）： 是有向图的一种存储方法； 是邻接表与逆邻接表的结合： 把每一条边的边结点分别组织到以起始顶点（弧尾）为头结点的链表和以终点顶点（弧头）为头结点的链表中。,弧结点中，弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。它们的头结点即为顶点结点。,顶点值域 指针域 指针域,弧尾结点 弧头结点 弧上信息 指针域 指针域,指向入边中的第一个结点,指向出边中的第一个结点,指向顶点tvex的下一条出弧,指向顶点hvex的下一条入弧,顶点结点结构：,弧结点结构：,存储顶点信息,弧尾顶点在图中的位置,弧头

17、顶点在图中的位置,存储弧的信息,弧结点,顶点结点,有向图的十字链表存储表示的C语言描述如下： #define MAX_VERTEX_NUM 20 弧结点 typedef struct ArcBox int tvex,hvex; /*弧的尾顶点和头顶点的位置*/ struct ArcBox * hlink, *tlink; /*分别为弧头相同和弧尾相同的弧的链域*/ InfoType info; /*弧的相关信息*/ ArcBox; typedef struct VexNode VertexType vex: ArcBox *fisrin,* firstout; /*分别指向该顶点第一条入弧和出

18、弧*/ VexNode; typedef struct VexNode xlistMAX_VERTEX_NUM; /*表头*/ int vexnum,arcnum; /*有向图的顶点数和弧数*/ OLGraph;,顶点结点,(3)有向图的十字链表存储表示,在有向图的十字链表中，既容易找到以vi为尾的弧，也容易找到以 vi为头的弧，因而容易求得顶点的出度和入度（如需要，可在建立十字链表的同时求出）。,(4)无向图的邻接多重表存储表示,无向图的邻接表适合于对顶点的操作。 考虑用图中一条边的信息用一个结点来表示，则对图的边进行操作将变得容易。 邻接多重表(Adjacency Multilist) ：

19、是无向图的另一种链式存储结构。,(4)无向图的邻接多重表存储表示,图的邻接多重表的顶点表结点结构和边表结点结构：,顶点结点结构,边表结点结构,顶点信息,指向依附于该顶点的第一个边结点,标记该条边是否被访问过,该边依附的顶点vi的位置,该边依附的顶点vj的位置,指向下一个依附于顶点vi的边结点,指向下一个依附于顶点vj的边结点,边信息,邻接多重表存储表示的C语言描述如下： #define MAX_VERTEX_NUM 20 typedef emnu unvisited,visited VisitIf; typedef struct EBox VisitIf mark: /*访问标记*/ int

20、ivex,jvex; /*该边依附的两个顶点的位置*/ struct EBox *ilink, *jlink; /*分别指向依附这两个顶点的下一条边*/ InfoType info; /*该边信息*/ EBox; typedef struct VexBox VertexType vex; EBox *fistedge; /*指向第一条依附该顶点的边*/ VexBox; typedef struct VexBox adjmulistMAX_VERTEX_NUM; int vexnum,edgenum; /*无向图的当前顶点数和边数*/ AMLGraph;,顶点表结点结构,边表结点结构,(4)无向

21、图的邻接多重表存储表示,对无向图而言，其邻接多重表和邻接表的差别，仅仅在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。因此，除了在边结点中增加一个标志域外，邻接多重表所需的存储量和邻接表相同。在邻接多重表上，各种基本操作的实现亦和邻接表相似。,三、图的遍历,从图中某顶点出发访遍图中每个顶点，且每个顶点仅访问一次，此过程称为图的遍历 (Traversing Graph)。 图的遍历较树的遍历更复杂：图中有回路，从图中某一顶点出发访问图中其它顶点时，可能又会回到出发点，而图中或许还有顶点没有访问到。 图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。,三、图的

22、遍历,图的遍历顺序： 深度优先搜索（DFS） 广度优先搜索（BFS）。 对每种搜索顺序，访问各顶点的顺序不是唯一的。,（1）深度优先搜索,深度优先搜索（Depth_First Search，DFS） 类似于树的先序遍历，是树的先序遍历的推广。,（1）深度优先搜索,DFS的过程：P153 从图中某个指定的顶点V0出发，首先访问V0，然后从该顶点的邻接点中任选一个顶点V1进行访问，再从V1的邻接点中任选一个V2进行访问，直到刚访问的某个顶点Vk的邻接点都已被访问过，回退到顶点Vk-1，访问其未被访问过的其他邻接点，重复此步骤，直到图中所有与顶点V0相连通的顶点都被访问过，对于连通图，则遍历完成；对

23、于非连通图，此时图中还有未被访问过的顶点，则可以从未被访问过的顶点中任选一个继续访问，直到图中的所有顶点都被访问过为止。,假设从顶点v1出发进行搜索，在访问了顶点v1之后，选择邻接点v2。因为v2未曾访问，则从v2出发进行搜索。依次类推，接着从v4 、v8 、v5 出发进行搜索。在访问了v5之后，由于v5的邻接点都已被访问，则搜索回到 v8。由于同样的理由，搜索继续回到v4、v2，直至v1，此时由于v1的另一个邻接点未被访问，则搜索又从v1到v3，再继续进行下去由此，得到的顶点访问序列为： v1 v2 v4v8 v5 v3v6v7,深度优先搜索的示例,深度优先搜索的示例,图中可能存在回路，且图

24、的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。 为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited ，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visited i 为 1，防止它被多次访问。 将图中没有标示绘图方向的边去掉，即可得到深度优先生成树,深度优先搜索过程 深度优先生成树,深度优先搜索练习： 给出深度优先搜索序列和深度优先生成树,整个图的DFS遍历TraverseGraph() ： 假定给定图G的初态是所有顶点均未被访问过； 在G中任选一个顶点i作为遍历的初始点，进行深度优先搜索，

25、即调用函数DFSM() 。 若图中还有未被访问过的顶点，则重复步骤2。 从第i个顶点出发深度优先搜索DFSM() ： 访问i顶点； 访问标志置为已被访问，即visitedi=1； 搜索i未被访问的邻接点j，若存在邻接点j，则以j为新的出发点递归调用DFSM()。 对于连通图，从一个顶点出发，调用DFSM函数即可将所有顶点都遍历到。 以邻接矩阵为存储结构的深度优先搜索遍历算法：P154，算法7.2。其中，i是初始顶点编号,visited 是一个全局数组,初始时所有元素均为0，表示所有顶点尚未访问过。),（2）广度优先搜索,广度优先搜索（Breadth_First Search） 类似于树的按层次

26、遍历的过程。,（2）广度优先搜索,BFS的过程 ：P155 从图中的某个顶点V出发，并在访问此顶点之后依次访问V的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,首先访问v1 和v1的邻接点v2和v3，然后依次访问v2 的邻接点v4 和v5 及v3 的邻接点v6和v7，最后访问v4 的邻接点v8。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由些完成了图的遍历。得到的顶点访问序列为： v1v2 v

27、3 v4 v5 v6 v7 v8,广度优先搜索的示例,将图中同层次的顶点间所依附的边和不同层次的顶点间未作为邻接关系直接访问的边去掉，可得到广度优先生成树。,广度优先搜索过程 广度优先生成树,广度优先搜索示例,广度优先搜索练习： 给出广度优先搜索序列和广度优先生成树,（2）广度优先搜索,广度优先搜索在搜索访问一层时，需要记住已被访问的顶点，以便在访问下层顶点时，从已被访问的顶点出发搜索访问其邻接点。在广度优先搜索中需要设置一个队列Queue，使已被访问的顶点顺序由队尾进入队列。在搜索访问下层顶点时，先从队首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的各个邻接点。 为了避免重复访问，设

28、置一个标志顶点是否被访问过的辅助数组 visited ，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visited i 为 1，防止它被多次访问。,广度优先搜索思想： 设图G的初态是所有顶点均未访问，则广度优先搜索的基本思想是： 从图中的某个顶点V出发，访问之；并将其访问标志置为已被访问，即visitedv=1；顶点入队； 出队，从出队的顶点出发，依次访问其未被访问过的邻接点，设置访问标志为1，即并依次将各访问到的顶点入队； 重复步骤2，直到队列空为止。此时图中所有与顶点v相通的顶点都被访问完。 对于非连通图，需要多次重复上述过程，才能将所有顶点都访问完。 以邻

29、接矩阵为存储结构的广度优先搜索遍历算法：P156，算法7.3。,四、图的连通性问题,（1）图的连通分量 无向图的连通分量 有向图的连通分量 （2）最小生成树 普里姆算法 克鲁斯卡尔算法,无向图的连通分量,在对无向图进行遍历时，对于连通图，仅需调用遍历过程(DFS或BFS)一次，从图中任一顶点出发，便可以遍历图中的各个顶点。对非连通图，则需多次调用遍历过程，每次调用得到的顶点集连同相关的边就构成图的一个连通分量。,有向图的连通分量,在对有向图进行遍历时，对于强连通图，仅需调用遍历过程(DFS或BFS)一次，从图中任一顶点出发，便可以遍历图中的各个顶点。对非强连通图，则需多次调用遍历过程，每次调用

30、得到的顶点集连同相关的边就构成图的一个强连通分量。,（2）最小生成树,使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。如深度优先生成树、广度优先生成树。 图(b) 和(c) 为图 (a) 的两棵生成树。其中 (b) 是通过DFS得到的，称为深度优先生成树；(c) 是通过BFS得到的，称为广度优先生成树。,生成树,由连通的带权图得到的生成树是一棵带权的树。 图的最小生成树：所有边上权值之和最小的生成树。 求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题。,假设把n个城市看作图的n个顶点，边表示两个城市之间的线路，每条边上的权值表示铺设该线路所

31、需造价。铺设线路连接n个城市，但不形成回路，要求以最少的线路铺设造价来连接各个城市，即求线路铺设造价最优问题。实际上是在图的生成树中选择权值之和最小的生成树。 构造最小生成树的算法： 克鲁斯卡尔(Kruskal)算法 普里姆(Prim)算法。,普里姆(Prim)算法,普里姆算法： 按逐个将顶点连通的方式来构造最小生成树。 算法的基本过程：P158,应用普里姆算法构造最小生成树的过程:,普里姆算法求解最小生成树的过程,克鲁斯卡尔(Kruskal)算法,克鲁斯卡尔算法 是一种按权值递增的次序选择合适的边来构造最小生成树的方法。 算法的基本过程：P159,应用克鲁斯卡尔算法构造最小生成树的过程:,克

32、鲁斯卡尔算法算法求解最小生成树的过程,五、有向无环图及其应用,工程中的活动： 通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动。这些活动完成时，整个工程也就完成了。 工程需要考虑的问题： 工程能否顺利进行； 完成工程所必需的最短时间。,五、有向无环图及其应用,（1）拓扑排序 （2）关键路径,拓扑排序,例 计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动，下图给出了若干门所开设的课程，其中有些课程的开设有先后关系，有些则没有先后关系，有先后关系的课程必须按先后关系开设，如开设数据结构课程之前必须先学完程

33、序设计基础及离散数学，而开设离散数学则必须先并行学完高等数学。,课程名称及相应的课程安排次序,课程安排的AOV网,在下图中，我们用一种有向图来表示课程开设，在这种有向图中，顶点表示活动，有向边表示活动的制约关系，这种有向图叫做顶点表示活动的网(Activity On Vertex Network)简称为AOV网。,拓扑排序,拓扑序列(Topological Order) ： 假设G=(V，E)是一个具有n个顶点的有向图，若V中所有顶点排成一个线性序列vl，v2，vn，且任意两个有路径相通的顶点在此序列中出现的先后次序表示了活动进行的先后次序，则称此序列为拓扑序列。 拓扑排序(Topologic

34、al Sort) ： 将AOV网中所有顶点排列成一个拓扑序列的过程或操作。,拓扑排序,由于AOV网中有些活动之间没有次序要求，它们在拓扑序列的位置可以是任意的，因此拓扑排序的结果不唯一。 对前面的图进行拓扑排序，可得一个拓扑序列： C1，C3，C2，C4，C7，C6，C5 也可得到另一个拓扑序列： C2，C7，C1，C3，C4，C5，C6 还可以得到其它的拓扑序列。学生按照以上任何一个拓扑序列都可以完成所要求的全部课程学习。,拓扑排序,AOV网中不应该出现有向环 有回路的AOV网不存在拓扑序列 判定判断一个工程能否顺利进行的方法判断其AOV网中是否存在回路,拓扑排序方法如下： 从有向图中选择一

35、个入度为0的顶点，并输出。若图中没有入度为0的顶点，则该图必有回路，拓扑排序失败。 从AOV网中删去该顶点，并且删去从该顶点发出的全部有向边其后继顶点的入度减1，则图中可能出现新的入度为0的顶点。 重复上述操作，直到剩余的AOV网中找不到入度为0的顶点为止。 若全部顶点均已输出，拓扑排序成功；若图中还有未输出的顶点，则说明AOV网中必定存在回路。,拓扑排序,拓扑序列为：C4 , C0 , C3 , C2 , C1 , C5 。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。,拓扑排序的过程：,拓扑排序,拓扑排序算法实现： 计算顶点的度，存入一

36、维数组； 查找入度为0的顶点，并检查该顶点是否已输出；将入度为0的顶点入栈。 删除度为0的顶点v：将其后继顶点的入度减1邻接矩阵中：查找矩阵中顶点v所在行的非0元素所在的列，将列在入度数组中对应的元素值减1。若有新的入度为0的顶点，则将其压栈。,拓扑排序,#define maxsize 20 typedef structure char vex; / int vex; int ind; vexd; vexd indegreemaxsize; typedef structure vexd elemmaxsize; int top; vstack;,拓扑排序,拓扑排序算法实现：邻接矩阵表示法 定义

37、入度数组indegree ，数组初始化为0； 定义栈s，栈置空； 按列统计邻接矩阵中非0元素个数，并存入入度数组indegree 中对应顶点的位置处；若入度为0则压入栈s； 栈非空，则栈顶顶点出栈并输出顶点；否则：判断图中顶点是否已全部输出（设置一个计数器用来计算输出顶点的个数），若输出顶点数小于图中顶点数，则图中存在有向环，拓扑排序失败。 在邻接矩阵中依次查找顶点v所在行的非0元素所在的列，并将该列在入度数组indegree 中对应的元素值减1。若出现新的入度为0的顶点，则将其压入栈s中，转第4步。,拓扑排序,逆拓扑排序法： 找出图中一个出度为0的顶点v，输出顶点v；若图中无出度为0的顶点，

38、则图中有回路，拓扑排序失败。 删除顶点v及其所有与之有关的弧使其前驱顶点的出度减1，则可能出现新的出度为0的顶点。 重复上述步骤，直到找不到出度为0的顶点为止。 此时，若图中的顶点全部输出，则拓扑排序成功按各顶点输出的先后次序产生的序列即是一个逆拓扑序列，该过程称为逆拓扑排序；否则未被输出的顶点可能构成了回路。,关键路径,AOE网(Activity On Edges) 如果在无有向环的带权有向图中： 用有向边表示一个工程中的各项活动(Activity)，边上的权值表示活动的开销（如：持续时间)； 用顶点表示事件(Event)，则这样的有向图叫做用弧表示活动的网，简称AOE网(Activity

39、On Edges) 。 AOE网是一个带权的有向无环图。,下图就是一个AOE网，该网中有11个活动和9个事件。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如事件E表示a4和a5活动已经完成，a7和a8活动可以开始。每个弧上的权值表示完成相应活动所需要的时间，如完成活动a1需要6天，a8需要7天。其中 A表示开始事件，I表示结束事件。,关键路径,AOE网常用于表示工程的计划或进度： 最短工期 工程进度的关键活动 实际工程中，通常只有一个开始点和一个结束点，因此，AOE网存在唯一的入度为0的开始点（源点）和唯一的出度为0的结束点（汇点）。,本章只讨论单源点和单汇点的情况。 实际应用

40、中，对于某些有多个开始事件的工程，其AOE网中存在多个入度为0的顶点，只要加一个虚拟源点，使这个虚拟源点到原来所有入度为0的点都有一条长度为0的边，变成只有一个源点。 对于有多个结束事件的工程的情况作类似的处理。,关键路径,在AOE网络中, 有些活动顺序进行，有些活动并行进行。 在AOE网中，从源点到汇点的所有路径中，具有最长路径长度（指路径上各活动持续时间之和，不是路径上弧的数目）的路径称为关键路径。关键路径上的活动称为关键活动。,关键路径,关键路径,在AOE网中，可以有多条关键路径。 关键路径的长度就是完成整个工程的最短时间（最短工期），也就是关键路径上各活动持续时间的总和。 只要找出AO

41、E网中的关键活动，也就找到了关键路径(Critical Path) 。,几个定义,事件j的最早发生时间 ve(j)：从源点到顶点j的最长路径长度。 含义： 所有以顶点j为弧头的活动都已结束； 所有以顶点j为弧尾的活动都可以开始。 规定源点事件的最早发生时间为0。,几个定义,事件j的最早发生时间 ve(j)的计算： 从ve(0) = 0开始，向前递推 dut()是完成ak 所需的时间（权值）,几个定义,事件i 的最迟发生时间 vl(i)：保证工期的前提下，事件i允许的最晚发生时间。 事件i 的最迟发生时间 vl(i)不能迟于其后继事件vj的vl(j)减去活动的dut()（ vl(i) ) ）。

42、汇点vn-1事件：最早发生时间 = 最迟发生时间，即：ve(n-1)=vl(n-1)。,几个定义,事件i 的最迟发生时间 vl(i)的计算： 从vl(n-1) = ve(n-1)开始，反向递推 这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。,几个定义,活动ak 的最早开始时间 ae(k)：设活动ak 在边上，事件i发生后，ak才能开始，因此， ae(k) = ve(i)。 活动ak 的最晚开始时间 al(k)：在不会引起时间延误的前提下，活动ak允许的最晚开始时间。 al(k)=vl(j)-dut()。,几个定义,松弛时间（时间余量）：不延误工程工期的前提下活动ak可以延迟的

43、时间。是活动ak 的最晚开始时间和最早开始时间的时间差。即：al(k) ae(k) 关键活动：松弛时间为0的活动。 即：al(k) = ae(k),求AOE网的关键路径的步骤： 对AOE网进行拓扑排序。如发现回路，工程无法进行。 找关键活动。为找出关键活动, 需要求各个活动的 ae(k) 与 al(k)，以判别是否al(k) = ae(k)。 为求得ae(k)与 al(k)，需要先求得从源点到各个顶点事件 j 的 ve(i) 和 vl(i)。,关键路径,求AOE网的关键活动的步骤： (1)对AOE网进行拓扑排序。如发现回路，工程无法进行，则退出；否则继续下一步。 (2)按拓扑次序，依次求各事件

44、i的最早开始时间ve(i)值；对于源点,置ve(0)=0 。 (3)按逆拓扑序列求每个事件j的最迟开始时间vl(j)；对于汇点，置vl(n-1)=ve(n-1)。 (4)求每个活动ak的最早开始时间ae(k)和最晚开始时间ae(k)。ae(k)=ve(i) al(k)=vl(j)-dut() (5)找出ae(k)=al(k)的活动ak，即为关键活动。,例：右图，拓扑排序：A，B，C，E，D，F，G，H，I 计算各事件的ve(i)： ve(A)=0,ve(B)=ve(A)+dut(a1)=6 ve(C)=ve(A)+dut(a2)=4 ve(D)=ve(A)+dut(a3)=5 ve(E)=ma

45、xve(B)+dut(a4),ve(C)+dut(a5)=max7,5=7 ve(F)=ve(E)+dut(a7)=16 ve(G)=ve(E)+dut(a8)=14 ve(H)=ve(D)+dut(a6)=7 ve(I)=maxve(F)+dut(a10),ve(G)+dut(a11),ve(H)+dut(a9) =max(18,18,11=18,计算各事件的vl(i) ： vl(I)=ve(I)=18 vl(F)=vl(I)-dut(a10)=16 vl(G)=vl(I)-dut(a11)=14 vl(H)=vl(I)-dut(a9)=14 vl(E)=min(vl(F)-dut(a7),

46、vl(G)-dut(a8)=min7,7=7 vl(D)=vl(H)-dut(a6)=12 vl(C)=vl(E)-dut(a5)=6 vl(B)=vl(E)-dut(a4)=6 vl(A)=minvl(B)-dut(a1),vl(C)-dut(a2),vl(D)-dut(a3) =min0,2,7=0,活动a1：ae(1)=ve(A)=0,al(1)=vl(B)-6=0,d(1)=0 活动a2：ae(2)=ve(A)=0,al(2)=vl(C)-4=2,d(2)=2 活动a3：ae(3)=ve(A)=0,al(3)=vl(D)-5=7,d(3)=7 活动a4：ae(4)=ve(B)=6,al

47、(4)=vl(E)-1=6,d(4)=0 活动a5：ae(5)=ve(C)=4,al(5)=vl(E)-1=6,d(5)=2 活动a6：ae(6)=ve(D)=5,al(6)=vl(H)-2=12,d(6)=7 活动a7：ae(7)=ve(E)=7,al(7)=vl(F)-9=7,d(7)=0 活动a8：ae(8)=ve(E)=7,al(8)=vl(G)-7=7,d(8)=0 活动a9：ae(9)=ve(H)=7,al(9)=vl(G)-4=10,d(9)=3 活动a10：ae(10)=ve(F)=16,al(10)=vl(I)-2=16, d(10)=0 活动a11：ae(11)=ve(G)

48、=14,al(11)=vl(I)-4=14, d(11)=0,关键活动：a11、a10、a8、a7、a4、a1 关键路径： A-B-E-F-I； A-B-E-G-I。,计算各活动ak的ae(k)=ve(i)、 al(k)=vl(j)-dut()和松弛时间d(k) ：,练习,下图是一个具有8个活动和6个事件的AOE网，试求其关键路径。,拓扑序列：1，2，3，4，5，6 由ve (i)和vl (i)的递推公式，依次求出所有事件的最早发生时间ve (i)和最迟发生时间vl (i)，如下：,求出所有活动ak的最早开始时间ae(k)、最迟开始时间al (k)以及d(k)=al(k)-ae(k)，如下：,

49、六、最短路经,（1）从某个源点到其余各顶点的最短路经 （2）每一对顶点之间的最短路经,六、最短路经,交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通? 在有多条通路的情况下，哪一条路最短? 交通网络可用带权图来表示。顶点表示城市名称，边表示两个城市有路连通，边上权值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径，不是指路径上边数之和最少，而是指路径上各边的权值之和最小。无权图实际上是有权图的一种特例，可以把无权图的每条边或弧的权值看成是1，每条路径上所经过的边或弧数即为路径长度。,（1）从某个源点到其余各顶点的最短路经,给定一个带权有向图G与源点v，求

50、从v到G 中其它顶点的最短路径。 为求得这些最短路径，迪杰斯特拉Dikstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。,（1）从某个源点到其余各顶点的最短路经,求解过程：P166,迪杰斯特拉算法的求解过程：,3、4、5选最小值dist4，4已解； 4的直接后继3、5 修改： dist3=15 path3= dist5=23 path5=,path2= dist2=3 path5= dist3=30,选最小值dist2 2已解； 2的直接 后继3、4 修改: dist3=28 path3=; dist4=11 path4=;,迪杰斯特拉算法求最短路径过程及结果,3,8,12,4,(f),第四次求得的结果,1,2,3,5,4,3、5中选dist3 3已解； 3无直接后继,只有一个未解顶点5 标为已解。 5无除1之外的直接后继，求解结束。,练习,求下图0号顶点到其他各个顶点的最短路径,设G=(V，E)是一个带权有向图，指定的顶点v0为源点，求v0到图的其余各顶点的最短路径。如上图所示，若以顶点0为v0，它到其余各顶点的最短路径分别为： 顶点0 顶点1：无路径