《图的基本概念及拓扑排序 (2)精.ppt》由会员分享，可在线阅读，更多相关《图的基本概念及拓扑排序 (2)精.ppt（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图的基本概念及拓扑排序第1页，本讲稿共53页什么是图？o什么是图?可用一句话概括，即：图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型.因为它显得太抽象，不便于理解，所以有必要给出另外的回答.第2页，本讲稿共53页1 1 图的基本术语图的基本术语图：图：记为记为 G(V,E)其中：其中：V 是是G的顶点集合，是有穷非空集；的顶点集合，是有穷非空集；E 是是G的边的边集合，是有穷集。集合，是有穷集。有向图：有向图：无向图：无向图：图图G G中的每条边都是有方向的；中的每条边都是有方向的；图图G G中的每条边都是无方向的；中的每条边都是无方向的；oo若若若若 n n 个顶点的
2、无向图有个顶点的无向图有个顶点的无向图有个顶点的无向图有 n n(n n-1)/2-1)/2 条边条边条边条边,称为称为称为称为无向完全图无向完全图无向完全图无向完全图oo若若若若 n n 个顶点的有向图有个顶点的有向图有个顶点的有向图有个顶点的有向图有n(n-1)n(n-1)条边条边条边条边,称为称为称为称为有向完全图有向完全图有向完全图有向完全图V=vertex E=edge第3页，本讲稿共53页例：例：判断下列判断下列4种图形各属什么类型？种图形各属什么类型？无向无向无向图无向图(树树)有向图有向图有向有向完全图完全图完全图完全图第4页，本讲稿共53页稀疏图：稠密图：设有两个图设有两个图
3、 G(V,E)和和 G(V,E)。若。若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子图。子 图：边较少的图。通常边数边较少的图。通常边数n2边很多的图。无向图中，边数接近边很多的图。无向图中，边数接近n n(n n-1)/2-1)/2；有向图中，边数接近有向图中，边数接近n n(n n-1)-1)补补 图：图：定义定义1：设图：设图G1=和图和图G2=是图是图G=的子图的子图.如果如果E2=E-E1且且G2=，则称图，则称图G2是相对于图是相对于图G的子图的子图G1的补图的补图.定义定义2：给定图：给定图G=，若存在图，若存在图G1=，并且，并且E1E=和图和图是完全图
4、，则是完全图，则G1称为相对于完全图的称为相对于完全图的G的补图，简称的补图，简称G1是是G的补图的补图.第5页，本讲稿共53页 带权图：带权图：即边上带权的图。其中即边上带权的图。其中权权是指每条边可以标上具有是指每条边可以标上具有某种含义的数值（即与边相关的数）。某种含义的数值（即与边相关的数）。带权图带权图网网 络：络：路径：路径：在图在图在图在图 GG(V,E)(V,E)中中中中,若从顶点若从顶点若从顶点若从顶点 vi vi 出发出发出发出发,沿一些边经过一些顶点沿一些边经过一些顶点沿一些边经过一些顶点沿一些边经过一些顶点 vp1,vp2,vpmvp1,vp2,vpm，到达顶点，到达顶
5、点，到达顶点，到达顶点vjvj。则称顶点序列。则称顶点序列。则称顶点序列。则称顶点序列 (vi vp1 vp2.vpm vj(vi vp1 vp2.vpm vj)为从顶点为从顶点为从顶点为从顶点vi vi 到顶点到顶点到顶点到顶点 vj vj 的路径。它经过的边的路径。它经过的边的路径。它经过的边的路径。它经过的边(vi,vp1)(vi,vp1)、(vp1,vp2)(vp1,vp2)、.、(vpm,vj)(vpm,vj)应当是属于应当是属于应当是属于应当是属于E E的边。的边。的边。的边。非带权图的路径长度是指此路径上非带权图的路径长度是指此路径上非带权图的路径长度是指此路径上非带权图的路径长
6、度是指此路径上 边的条数边的条数边的条数边的条数；带权图的路径长度是指路径上带权图的路径长度是指路径上带权图的路径长度是指路径上带权图的路径长度是指路径上各边的权之和各边的权之和各边的权之和各边的权之和。路径长度：路径长度：第6页，本讲稿共53页连通图：连通图：在在在在无向无向无向无向图中图中图中图中,若从顶点若从顶点若从顶点若从顶点v v1 1到顶点到顶点到顶点到顶点v v2 2有路径有路径有路径有路径,则称顶点则称顶点则称顶点则称顶点v v1 1与与与与v v2 2是是是是连通连通连通连通的。如果图中任意一对顶点都是连通的。如果图中任意一对顶点都是连通的。如果图中任意一对顶点都是连通的。如
7、果图中任意一对顶点都是连通的的的的,则称此图是则称此图是则称此图是则称此图是连通图连通图连通图连通图。非连通图的极大连通子图非连通图的极大连通子图非连通图的极大连通子图非连通图的极大连通子图叫做叫做叫做叫做连通分量连通分量连通分量连通分量。强连通图：强连通图：在在在在有向有向有向有向图中图中图中图中,若对于每一对顶点若对于每一对顶点若对于每一对顶点若对于每一对顶点v vi i和和和和v vj j,都存在一条从都存在一条从都存在一条从都存在一条从v vi i到到到到v vj j和和和和从从从从v vj j到到到到v vi i的路径的路径的路径的路径,则称此图是则称此图是则称此图是则称此图是强连通
8、图强连通图强连通图强连通图。非强连通图的极大强连通子图非强连通图的极大强连通子图非强连通图的极大强连通子图非强连通图的极大强连通子图叫做叫做叫做叫做强连通分量强连通分量强连通分量强连通分量。第7页，本讲稿共53页生成树：生成树：邻接点：顶点顶点v的度的度是与它相关联的边的条数。记作是与它相关联的边的条数。记作TD(v)。在在有向图有向图中中,顶点的度等于该顶点的顶点的度等于该顶点的入度入度与与出度出度之和。之和。顶点顶点 v 的入度的入度是以是以 v 为终点的有向边的条数为终点的有向边的条数,记作记作 ID(v);顶点顶点 v 的出度的出度是以是以 v 为始点的有向边的条数为始点的有向边的条数
9、,记作记作 OD(v)。若若(u,v)是是 E(G)中的一条边，则称中的一条边，则称 u 与与 v 互为互为邻接顶点邻接顶点度、入度和出度：是一个是一个是一个是一个极小连通子图极小连通子图极小连通子图极小连通子图，它含有图中全部顶点，但只有，它含有图中全部顶点，但只有，它含有图中全部顶点，但只有，它含有图中全部顶点，但只有n n-1-1条边条边条边条边。oo如果在生成树上添加如果在生成树上添加如果在生成树上添加如果在生成树上添加1 1条边，必定构成一个环。条边，必定构成一个环。条边，必定构成一个环。条边，必定构成一个环。oo若图中有若图中有若图中有若图中有n n个顶点，却少于个顶点，却少于个顶
10、点，却少于个顶点，却少于n n-1-1条边，必为非连通图。条边，必为非连通图。条边，必为非连通图。条边，必为非连通图。最小生成树：最小生成树：若无向连通带权图若无向连通带权图若无向连通带权图若无向连通带权图G=,TG=,T是是是是GG的一棵生成树，的一棵生成树，的一棵生成树，的一棵生成树，T T的各边权之和称为的各边权之和称为的各边权之和称为的各边权之和称为T T的权，记做的权，记做的权，记做的权，记做WW（T T），），），），GG的所有生成树中权值最小的生成树称为最小生成树。的所有生成树中权值最小的生成树称为最小生成树。的所有生成树中权值最小的生成树称为最小生成树。的所有生成树中权值最小的
11、生成树称为最小生成树。最小生成树算法：Prim算法和算法和kruskal算法算法第8页，本讲稿共53页简单路径：路径上各顶点路径上各顶点 v v1 1,v,v2 2,.,v,.,vm m 均不互相重复。均不互相重复。回 路：例：例：若路径上第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点v vm m 重合，则称重合，则称这样的路径为这样的路径为回路或环回路或环。第9页，本讲稿共53页图的数学表示o点:用整数0,1,2,V-1表示o边:用无序数对(u,v)表示,或者表示成u-v第10页，本讲稿共53页7.2 7.2 图的存储结构图的存储结构重点介绍：重点介绍：邻接矩阵邻接
12、矩阵(数组数组)表示法表示法邻接表邻接表(链式链式)表示法表示法o主要有下面四种方法：o邻接矩阵o邻接表o十字链表o多重链表第11页，本讲稿共53页一、邻接矩阵（数组）表示法一、邻接矩阵（数组）表示法oo建立一个建立一个建立一个建立一个邻接矩阵（表示各个顶点之间关系）邻接矩阵（表示各个顶点之间关系）邻接矩阵（表示各个顶点之间关系）邻接矩阵（表示各个顶点之间关系）。oo设图设图设图设图 A=(A=(V V,E E)有有有有 n n 个顶点，则图的邻接矩阵是一个二维数组个顶点，则图的邻接矩阵是一个二维数组个顶点，则图的邻接矩阵是一个二维数组个顶点，则图的邻接矩阵是一个二维数组 A.EdgennA.
13、Edgenn，定义为：，定义为：，定义为：，定义为：1235v4 4A例例例例1 1：邻接矩阵：邻接矩阵：邻接矩阵：邻接矩阵：A.Edge=（1 2 3 4 5 ）123450 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0顶点表：顶点表：顶点表：顶点表：第12页，本讲稿共53页例例2：有向图的邻接矩阵有向图的邻接矩阵v1v2v3v4A邻接矩阵：A.Edge=(v1 v2 v3
14、 v4)v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 注：注：在有向图的邻接矩阵中，在有向图的邻接矩阵中，第第i i行含义：以结点行含义：以结点v vi i为起点的边为起点的边(即出边）；即出边）；第第i i列含义：以结点列含义：以结点v vi i为终点的弧为终点的弧(即入边）。即入边）。顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 第13页，本讲稿共53页特别讨论特别讨论：网（即有权图）的邻接矩阵网（即有权图）的邻接矩阵定义为：定义为：A.Edge i j=Wij 或（或（v
15、i,vj）VR 无边（弧）无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：以有向网为例：邻接矩阵：N.Edge=(1 2 3 4 5 6 )顶点表：5 7 4 8 9 5 6 5 3 1 第14页，本讲稿共53页图的邻接矩阵表示示例int adjlistmax_vex_nummax_vex_num;说明：adjlistij 若无权图无重边则直接用0 1表示I j两点 是否直接邻接 若无权图有重边则直接用0 1.表示是I j两点之间边的个数 若有权图则用来表示I j两点之间的距离 或者其他权值 第15页，本讲稿共53页二、邻接表（链式）表示法二、邻接表（链式）表示法oo对每
16、个顶点对每个顶点对每个顶点对每个顶点v vi i 建立一个建立一个建立一个建立一个单链表单链表单链表单链表，把与，把与，把与，把与v vi i有关联的有关联的有关联的有关联的边边边边（即度或出度边）（即度或出度边）（即度或出度边）（即度或出度边）链接链接链接链接起来，表中每个结点都设为起来，表中每个结点都设为起来，表中每个结点都设为起来，表中每个结点都设为2 2个域；个域；个域；个域；adjvexnextarc权权值值datafirstarc表结点表结点表结点表结点头结点头结点头结点头结点邻接点域，邻接点域，表示表示v vi i一个邻接点一个邻接点的位置的位置链域，链域，指向指向vivi下一个
17、边或弧下一个边或弧的结点的结点数据域，存储数据域，存储顶点顶点vi 的序号的序号链域，链域，指向单指向单链表的第一个链表的第一个结点结点第16页，本讲稿共53页邻接表的邻接表的缺点：缺点：邻接表的优点：邻接表的优点：空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；一般用于稀疏图一般用于稀疏图判断两顶点间是否有边或弧，需搜索两结点判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。对应的单链表，没有邻接矩阵方便。邻接表 邻接矩阵存储比较邻接矩阵的优点：邻接矩阵的优点：判断两顶点间是否有边或弧，可以直接判断判断两顶点间是否有边或弧，可以直接判断速度很快速度很快
18、 一般用于存储稠密图一般用于存储稠密图邻接矩阵的邻接矩阵的缺点：缺点：存储空间大存储空间大 会影响算法的空间效率会影响算法的空间效率 甚至时间效甚至时间效率率第17页，本讲稿共53页讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1.1.联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，链表邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。中结点个数等于一行中非零元素的个数。2.2.区别：区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶
19、点编号无点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复杂度而邻接表的空间复杂度为为O(n+e)O(n+e)。3.3.用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-n(n-1)/2)1)/2)；而邻接表多用于稀疏图的存储（；而邻接表多用于稀疏图的存储（ene1.容易证明对于任意距离值x,di=x的点一定是正确的,而且白色点(没有计算出距离的点)的距离一定至少为x+1o更进一步,根据每个点的parent值,可以计算出它到s的一条最短路第24页，本讲稿共5
20、3页Bfs算法中路径的打印Print-Path(G,s,v)if(v=s)then print s else if v=NIL then print“no path from”s”to”v”exits”else Print-path(G,s,v)print v第25页，本讲稿共53页机器人问题机器人问题1.Dr.Kong是设计了一个可以前进或者后退的机器人，该机器人在每一个位置i会得到一个2.移动的步数指令Ki（i=1，2n），聪明的机器人会自己判断是要前进Ki步还是要后退Ki步。3.例如：给定指令序列（3，3，1，2，5），表示机器人在第一个位置时，可以前进3步到第4个位置，此时后退是不起作
21、用的，出界：机器人在第2个位置时，可以前进3步到第5个位置，此时后退时不起作用的，出界：机器人在第3个位置的时，可以前进1步到第4个位置，也可以后退一步到第2个位置等等.4.你认为，对于给定的两个位置A，B，聪明的机器人从A位置到B位置至少需要判断几次？5.input6.第一行：M 表示以下有M组测试数据（0M=8）7.接下来每组有两行数据8.头一行：N A B（1=N=50,1=A,B=N）9.下一行：K1 K2Kn（0=Kinab;9.for(int i=1;itemp;13.if(i+temp=1)16.argsii-temp=true;17.rda=0;svisiteda=true;t
22、queueq;u q.push(a);vwhile(!q.empty()wx int temp=q.front();y q.pop();zfor(int i=0;i=n;i+)aabb if(argstempi&!visitedi)cc dddi=dtemp+1;eevisitedi=true;ff q.push(i);gg hh iijjcoutdbendl;第28页，本讲稿共53页二、深度优先遍历二、深度优先遍历(DFS)第29页，本讲稿共53页深度优先搜索深度优先搜索深度优先搜索深度优先搜索(DFSDFSDFSDFS)基本思想：基本思想：仿树的先序遍历过程。仿树的先序遍历过程。Depth
23、_First Searchv1v1v2v3v8v7v6v4v5DFS DFS 结果结果结果结果例例1 1：v2v4v8v5v3v6v7例例2 2：v2 v1 v3 v5 DFS 结果结果v4 v6起点起点起点起点遍历步骤遍历步骤第30页，本讲稿共53页深度优先搜索（遍历）步骤：深度优先搜索（遍历）步骤：详细归纳：详细归纳：o在访问图中某一起始顶点在访问图中某一起始顶点 v 后，由后，由 v 出发，访问出发，访问它的任一邻接顶点它的任一邻接顶点 w1；o再从再从 w1 出发，访问出发，访问与与 w1邻接邻接但还但还未被访问未被访问过的顶点过的顶点 w2；o然后再从然后再从 w2 出发，进行类似的
24、访问，出发，进行类似的访问，o如此进行下去，直至到达所有的邻接顶点都被访问过的顶点如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为为止。止。o接着，退回一步，接着，退回一步，退到前一次刚访问过的顶点退到前一次刚访问过的顶点，看是否还有其它没，看是否还有其它没有被访问的邻接顶点。有被访问的邻接顶点。如果有，如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，如果没有，就就再退回一步再退回一步进行搜索。重复上述过程，直到连通图中所进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。有顶点都被访问过为止
25、。简单归纳：简单归纳：o 访问起始点访问起始点 v;o 若若v的第的第1个邻接点没访问过，深度遍历此邻接点；个邻接点没访问过，深度遍历此邻接点；o若当前邻接点已访问过，再找若当前邻接点已访问过，再找v的第的第2个邻接点重新遍历。个邻接点重新遍历。第31页，本讲稿共53页基本算法o新发现的结点先扩展o得到的可能不是一棵树而是森林,即深度优先森林(Depth-first forest)o特别之处:引入时间戳(timestamp)n发现时间dv:变灰的时间n结束时间fv:变黑的时间n1=dv fv=2|V|o初始化:time为0,所有点为白色,dfs森林为空o对每个白色点u执行一次DFS-VISIT
26、(u)第32页，本讲稿共53页DFS-VISIT算法o初始化:time为0,所有点为白色,dfs森林为空o对每个白色点u执行一次DFS-VISIT(u)o时间复杂度为O(n+m)第33页，本讲稿共53页第34页，本讲稿共53页DFS树的性质o括号结构性质o对于任意结点对(u,v),考虑区间du,fu和dv,fv,以下三个性质恰有一个成立:n完全分离nu的区间完全包含在v的区间内,则在dfs树上u是v的后代nv的区间完全包含在u的区间内,则在dfs树上v是u的后代o三个条件非常直观第35页，本讲稿共53页DFS树的性质o定理1(嵌套区间定理):在DFS森林中v是u的后代当且仅当dudvfv=0;
27、w=NextAdjVex(G,u,w)o if(!visitedw)Push(G,w)/将没访问的邻接点压栈 o o DestroyStack(S);/释放栈o/DFS第37页，本讲稿共53页数据结构书上的深度优先搜索算法obool visitedmax;/访问标志数组oStatus(*VisitFunc)(int v);/函数变量ovoid DESTraverse(Graph G,status(*visit)(int v)o /对图G进行深度优先搜索（图G连通与否都可以）o visitFunc=visit;/使用全局变量Visitfunc，使DFS函数不必设置函数指针o /访问标志数组初始化
28、为全部没有访问o for(v=0,vG.vecnum;+v)visitdv=false;o for(v=0;v=0;w=nextAdjvex(G,v,w)o if(!visitedw)DFS(G,w);/对v的尚未访问过的邻接点w递归调用DFSo如果是连通图此处的DFS只会被执行一次如果是非连通图此处DFS执行的次数就是连通分支数第38页，本讲稿共53页图的连通性问题o对于无向图o 若是连通图则从图中任意顶点出发进行广搜或者深搜便可以访问到图中的任意顶点o 非连通图则需要多次调用DFS才可全部访问 每次DFS可以访问一个连通分量中的所有顶点 调用DFS的次数为图的连通分支数o 另外采用并查集也
29、可以解决这个问题，并且空间效率比较低。最后若能归并成一个几何则说明为连通的，若最后是多个集合则说明是非连通图对于有向图：o以后在学习的过程中会做深入的探讨第39页，本讲稿共53页深搜示例：http:/ 一块矩形地 其中W代表的是水.代表的是陆地 其中我们认为每个方格和它的 八个方向全部是邻接的问其中有多少池塘题目分析 访问一次水方格，我们可以将其8个方向的水方格全部访问，这样我们对一个水方格进行深搜就可以将与其之间有路径的所有点全部访问。既是可以访问一个连通分支（也就是一个湖）。搜索的次数就是湖的个数第40页，本讲稿共53页示例代码：1.#include 2.using namespace s
30、td;3.int a101101;/记录矩形方格对应的是水还是陆地4.int sum,n,m;/sum记录湖的个数n 矩形地的行数m矩形地的列数5.int flag101101;/标记每个方格是否已经被访问过6./定义的个方向7.int d82=1,0,1,1,0,1,-1,1,-1,0,-1,-1,0,-1,1,-1;8./检查x y是否出界9.bool check(int x,int y)10.11.if(x0&x0&y=m)12.return 1;13.return 0;14.15./以一个方格开始深度优先搜索16.void dfs(int x,int y)17.18.if(flagxy
31、|!axy)/点已经访问或者是陆地则停止访问 19.return;20.flagxy=1;/标记当前结点已经访问21.for(int i=0;inm)o omemset(flag,0,sizeof(flag);/全部方格标记为没有访问omemset(a,0,sizeof(a);/方格全部标记为陆地osum=0;/初始化湖的个数为ofor(i=1;i=n;i+)ofor(j=1;jc;oif(c=W)aij=1;/是水的方格标记为水 o ofor(i=1;i=n;i+)ofor(j=1;j=m;j+)/对是水且未被访问过的方格进行深搜oif(aij&!flagij)/每次访问访问一个连通分支即一
32、个湖odfs(i,j),sum+;ocoutsumendl;o oreturn 0;oo对于无向图的连通分支数的判断既可以用广度优先搜索 也可以用深度优先搜索o大家一定要试着写一下此题的广度优先搜索代码第42页，本讲稿共53页推荐题目搜索经典题目 迷宫求解：用一个矩形表示地图，其中矩形由方格组成，每个方格为路或者是墙。给你一个起点位置和一个终止位置，问你是否能从 开头位置到达终点位置，我们认为起始位置和终点位置是不重合的，并且我们只能走直路，不可以走斜路。我们保证起点和终点都是空位置。要求你求一下这条路径是否存在，存在的话。求出路径的长度 输入说明：第一行 m n 代表矩形是m行n列的 p q
33、 r s，（p，q）开始位置，（r，s）目标位置 接下来的m行 每行共n个01代码，其中0代表是通路，1代表是墙。输出说明：有路径输出yes并输出最短路径各一行，没有路径直接输出no 占一行 示例输入：2 2 0 0 1 1 0 1 0 0 示例输出：yes 2 思路深搜只能求是否有通路，广搜是否有通路和最短路径都可以求出来深搜只能求是否有通路，广搜是否有通路和最短路径都可以求出来ohttp:/ 拓扑排序问题第44页，本讲稿共53页 C1 高等数学高等数学 C2 程序设计基础程序设计基础 C3 离散数学离散数学 C1,C2 C4 数据结构数据结构 C3,C2 C5 高级语言程序设计高级语言程序
34、设计 C2 C6 编译方法编译方法 C5,C4 C7 操作系统操作系统 C4,C9 C8 普通物理普通物理 C1 C9 计算机原理计算机原理 C8 第45页，本讲稿共53页学生课程学习工程图学生课程学习工程图第46页，本讲稿共53页o检测有向环的一种方法是对检测有向环的一种方法是对AOV网络构造它的拓网络构造它的拓扑有序序列。即将各个顶点扑有序序列。即将各个顶点(代表各个活动代表各个活动)排列排列成一个线性有序的序列，使得成一个线性有序的序列，使得AOV网络中所有应网络中所有应存在的前驱和后继关系都能得到满足。存在的前驱和后继关系都能得到满足。o这种构造这种构造AOV网络全部顶点的拓扑有序序列
35、的运网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。算就叫做拓扑排序。o如果通过拓扑排序能将如果通过拓扑排序能将AOV网络的所有顶点都排网络的所有顶点都排入一个拓扑有序的序列中，则该入一个拓扑有序的序列中，则该AOV网络中必定网络中必定不会出现有向环；相反，如果得不到满足要求的不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明拓扑有序序列，则说明AOV网络中存在有向环，网络中存在有向环，此此AOV网络所代表的工程是不可行的。网络所代表的工程是不可行的。第47页，本讲稿共53页o例如，对学生选课工程图进行拓扑排序，得到的例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为拓扑有序
36、序列为oC1,C2,C3,C4,C5,C6,C8,C9,C7或或 C1,C8,C9,C2,C5,C3,C4,C7,C6第48页，本讲稿共53页o可以用可以用有向图有向图表示一个工程。在这种有向图中，表示一个工程。在这种有向图中，用顶点表示活动用顶点表示活动，用有向边用有向边表示活动。表示活动。Vi 必须先于活动必须先于活动Vj 进行。这种有向图叫做顶点表示进行。这种有向图叫做顶点表示活动的活动的AOV网络网络(Activity On Vertices)。o在在AOV网络中，如果活动网络中，如果活动Vi 必须在活动必须在活动Vj 之前进之前进行，则存在有向边行，则存在有向边，AOV网络中不能出网
37、络中不能出现有向回路，即有向环。在现有向回路，即有向环。在AOV网络中如果出现网络中如果出现了有向环，则意味着某项活动应以自己作为先决了有向环，则意味着某项活动应以自己作为先决条件。条件。o因此，对给定的因此，对给定的AOV网络，必须先判断它是否存网络，必须先判断它是否存在有向环。在有向环。第49页，本讲稿共53页进行拓扑排序的方法 输入输入AOV网络。令网络。令 n 为顶点个数。为顶点个数。在在AOV网络中选一个没有直接前驱的顶点网络中选一个没有直接前驱的顶点,并并输出之输出之;从图中删去该顶点从图中删去该顶点,同时删去所有它发出的同时删去所有它发出的有向边有向边;重复以上重复以上 、步步,
38、直到直到n全部顶点均已输出，拓扑有序序列形成，拓扑全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或排序完成；或n图中还有未输出的顶点，但已跳出处理循环。这图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时再也找不到没有前驱的顶点了。这时AOV网络中网络中必定存在有向环。必定存在有向环。第50页，本讲稿共53页 最后得到的拓扑有序序列为最后得到的拓扑有序序列为 C4,C0,C3,C2,C1,C5。它满足图中给出的所有前驱和后继关系，对于本来。它满足图中给出的所有前驱和后继关系，对于本来
39、没有这种关系的顶点，如没有这种关系的顶点，如C4和和C2，也排出了先后次序，也排出了先后次序关系。关系。拓扑排序的过程第51页，本讲稿共53页拓扑排序算法1.bool TopLogicalSort(Graph gf)2.3.SqStack s;4.FindInDegree(gf);/求出各点的入度求出各点的入度5.InitStack(s);6.for(int i=0;i gf.vexnum;+i)7.if(!gf.degreei)Push(s,i);/0入度顶点全部入栈入度顶点全部入栈8.count=0;/记录已经输出顶点的个数记录已经输出顶点的个数9.while(!IsStackEmpty(s)10.11.Pop(s,i);12.couti“”gf.verticesi.data nextarc)16.17.-gf.degreep-adjvex;18.if(!gf.degreep-adjvex)Push(s,p-adjvex);19.20.21.22.if(count gf.vexnum)return false;/未访问到所有顶点说明有回路未访问到所有顶点说明有回路23.return true;24.第52页，本讲稿共53页o本次讲课的内容在算法导论322-336页o哪里不懂的可以仔细的看一下。第53页，本讲稿共53页