数据结构第七章.ppt

《数据结构第七章.ppt》由会员分享，可在线阅读，更多相关《数据结构第七章.ppt（100页珍藏版）》请在三一办公上搜索。

1、1,图的基本概念图的存储结构图的遍历图的连通性问题 最小生成树最短路径 活动网络,第七章 图,2,图的基本概念,图定义 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph(V,E)其中 V=x|x 某个数据对象 是顶点的有穷非空集合；E1=(x,y)|x,y V 或 E2=|x,y V&Path(x,y)其中，E1是顶点之间关系的有穷集合，也叫做边(edge)集合，此时的图称为无向图。E2 表示从 x 到 y 的一条弧，且称x为弧尾，y为弧头，这样的图称为有向图。,3,有向图与无向图 在有向图中，顶点对 是有序的。在无向图中，顶点对(x,y)是无序的。完全图 若有

2、n 个顶点的无向图有 n(n-1)/2 条边,则此图为无向完全图。有 n 个顶点的有向图有n(n-1)条边,则此图为有向完全图。,0,0,0,0,1,1,1,1,2,2,2,2,6,5,4,3,3,4,邻接顶点 如果(u,v)是 E(G)中的一条边，则称 u 与 v 互为邻接顶点。子图 设有两个图 G(V,E)和 G(V,E)。若 V V 且 EE,则称 图G 是 图G 的子图。权 某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。,5,顶点的度 一个顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。顶点 v 的入度是以 v 为终点的有向

3、边的条数,记作 ID(v);顶点 v 的出度是以 v 为始点的有向边的条数,记作 OD(v)。路径 在图 G(V,E)中,若从顶点 vi 出发,沿一些边经过一些顶点 vp1,vp2,vpm，到达顶点vj。则称顶点序列(vi vp1 vp2.vpm vj)为从顶点vi 到顶点 vj 的路径。它经过的边(vi,vp1)、(vp1,vp2)、.、(vpm,vj)应是属于E的边。,6,顶点的出度:以顶点v 为弧尾的弧的数目;顶点的入度:以顶点v为弧头的弧的数目。,有向图,顶点的度(TD)=出度(OD)+入度(ID)TD(B)=OD(B)+ID(B)=3,例如:,7,路径长度 非带权图的路径长度是指此路

4、径上边的条数。带权图的路径长度是指路径上各边的权之和。简单路径 若路径上各顶点 v1,v2,.,vm 均不 互相重复,则称这样的路径为简单路径。简单回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合,则称这样的路径为回路或环。,0,1,2,3,0,1,2,3,0,1,2,3,8,如:从A到F长度为 3 的路径A,B,C,F,9,连通图与连通分量 在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。强连通图与强连通分量 在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从v

5、j到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,10,无向图,若图中任意两个顶点之间都有路径相通，则称此图为连通图;,若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。,11,有向图,若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。否则，其各个强连通子图称作它的强连通分量。,A,B,E,C,F,12,生成树:假设一个连通图有n个顶点和e 条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。在极小连通子图中增加一条边，则一定有环。在极小连通子图中去掉一条边，则成为非连通图。,B,A,C,D,F,E,13

6、,有n个顶点，n-1条边的图必定是生成树吗？,对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。,14,图的存储结构,在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。设图 A=(V,E)是一个有 n 个顶点的图,图的邻接矩阵是一个二维数组 A.edgenn，定义：,邻接矩阵(Adjacency Matrix),15,无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。,0,1,2,3,0,1,2,16,在有向图中,统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 列 1 的个数可得顶点 j 的入度。在无向图中,统计

7、第 i 行(列)1 的个数可得顶点i 的度。,17,网络的邻接矩阵,18,#define MaxValue Int_Maxconst int NumEdges=50;/边条数const int NumVertices=10;/顶点个数typedef char VertexData;/顶点数据类型 typedef int EdgeData;/边上权值类型typedef struct VertexData vexListNumVertices;/顶点表 EdgeData EdgeNumVerticesNumVertices;/邻接矩阵,可视为边之间的关系 int n,e;/图中当前的顶点个数与边数

8、 MTGraph;,用邻接矩阵表示的结构定义,19,邻接表(Adjacency List),邻接表:是图的一种链式存储结构。弧的结点结构adjvex;/该弧所指向的顶点的位置nextarc;/指向下一条弧指针 info;/该弧相关信息的指针,顶点的结点结构,data;/顶点信息firstarc;/指向第一条依附该顶点的弧,20,无向图的邻接表,同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边(边结点),结点中有另一顶点的下标 dest 和指针 link。,21,有向图的邻接表和逆邻接表,A,B,C,data adj,ABC,012,dest link,dest link,邻接表(

9、出边表),data adj,ABC,012,dest link,逆邻接表(入边表),1,0,2,0,1,1,22,网络(带权图)的邻接表,B,A,C,D,6,9,5,2,8,data adj,ABCD,0123,dest cost link,1 5,3 6,2 8,3 2,1 9,(出边表),(顶点表),23,带权图的边结点中保存该边上的权值 cost。顶点 i 的边链表的表头指针 adj 在顶点表的下标为 i 的顶点记录中，该记录还保存了该顶点的其它信息。在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。设图中有 n 个顶点，e 条边，则用邻接表表示无向图时，需要 n 个顶

10、点结点，2e 个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个顶点结点，e 个边结点。,24,图的邻接表存储表示#define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置 struct ArcNode*nextarc;/指向下一条弧指针 InfoType*info;/该弧相关信息的指针 ArcNode;typedef struct VNode VertexType data;/顶点信息 ArcNode*firstarc;/指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_N

11、UM;,25,typedef struct AdjList vertices;Int vexnum,arcnum;/图的当前顶点数和弧数Int kind;/图的种类标志ALGraph;,26,typedef char VertexData;/顶点数据类型typedef int EdgeData;/边上权值类型typedef struct node/边结点 int dest;/目标顶点下标 EdgeData cost;/边上的权值 Struct node*link;/下一边链接指针 EdgeNode;,邻接表表示的图的定义（为算法）,27,typedef struct/顶点结点 VertexDa

12、ta data;/顶点数据域 EdgeNode*firstAdj;/边链表头指针 VertexNode;typedef struct/图的邻接表 VertexNode VexList NumVertices;/邻接表 int n,e;/图中当前的顶点个数与边数 AdjGraph;,28,邻接表的构造算法(无向图)void CreateGraph(AdjGraph G)cin G.n G.e;/输入顶点个数和边数 for(int i=0;i G.VexListi.data;/输入顶点信息 G.VexListi.firstAdj=NULL;for(i=0;i tail head weight;Ed

13、geNode*p=new EdgeNode;p-dest=head;p-cost=weight;,29,/链入第 tail 号链表的前端 p-link=G.VexListtail.firstAdj;G.VexListtail.firstAdj=p;p=new EdgeNode;p-dest=tail;p-cost=weight;/链入第 head 号链表的前端 p-link=G.VexListhead.firstAdj;G.VexListhead.firstAdj=p;,30,图的遍历,从图中某一顶点出发访遍图中所有的顶点，且使每个顶点仅被访问一次，这一过程就叫做图的遍历(Traversing

14、 Graph)。图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited。,31,辅助数组 visited 的初始状态为 0,在图的遍历过程中,一旦某一个顶点 i 被访问,就立即让 visited i 为 1,防止它被多次访问。两种图的遍历方法:深度优先搜索 DFS(Depth First Search)广度优先搜索 BFS(Breadth First Search),32,深度优先搜索DFS(Depth First Search),深度优先搜索过程,6,7,前

15、进回退,深度优先生成树,33,DFS 在访问图中某一起始顶点 v 后,由 v 出发,访问它的任一邻接顶点 w1;再从 w1 出发,访问与 w1邻 接但还没有访问过的顶点 w2;然后再从 w2 出发,进行类似的访问,如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。,34,图的深度优先搜索算法void Graph_Traverse(AdjGraph G)int*

16、visited=new int NumVertices;for(int i=0;i G.n;i+)visited i=0;/访问数组 visited 初始化 for(int i=0;i G.n;i+)if(!visitedi)DFS(G,i,visited);/从顶点 i 出发开始搜索 delete visited;/释放 visited,35,void DFS(AdjGraph G,int v,int visited)cout GetValue(G,v);/访问顶点 v visitedv=1;/顶点 v 作访问标记 int w=GetFirstNeighbor(G,v);/取 v 的第一个邻

17、接顶点 w while(w!=-1)/若邻接顶点 w 存在 if(!visitedw)DFS(G,w,visited);/若顶点 w 未访问过,递归访问顶点 w w=GetNextNeighbor(G,v,w);/取顶点 v 排在 w 后的下一个邻接顶点,36,广度优先搜索BFS(Breadth First Search),广度优先搜索过程,A,C,D,E,G,B,F,I,H,A,C,D,E,G,B,F,H,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,广度优先生成树,I,37,BFS在访问了起始顶点 v 之后,由 v 出发,依次访问 v 的各个未被访问过的邻接顶点

18、w1,w2,wt,然后再顺序访问 w1,w2,wt 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，如此做下去，直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况。因此,广度优先搜索不是一个递归的过程。,38,为了实现逐层访问,算法中使用了一个队列,以记忆正在访问的这一层和下一层的顶点,以便于向下一层访问。为避免重复访问,需要一个辅助数组 visited，给被访问过的顶点加标记。,图的广度优先搜索算法void Graph_Traverse(AdjGraph G)for

19、(int i=0;i G.n;i+)if(!visitedi)BFS(G,i,visited);,39,void BFS(AdjGraph G,int v,int visited)cout q;InitQueue(,40,visitedw=1;EnQueue(,41,连通分量(Connected component)当无向图为非连通图时,从图中某一顶点出发,利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点,只能访问到该顶点所在的最大连通子图(连通分量)的所有顶点。若从无向图的每一个连通分量中的一个顶点出发进行遍历,可求得无向图的所有连通分量。,图的连通性问题,42,求连通分量的

20、算法需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。,43,A,C,D,E,I,B,F,O,G,H,J,N,M,L,K,非连通无向图的三个连通分量,A,H,K,C,D,E,I,B,F,O,G,J,N,M,L,非连通图的连通分量的极小连通子图,44,重连通分量(Biconnected Component),在无向连通图G中,当且仅当删去G中的顶点v及所有依附于v的所有边后,可将图分割成两个或两个以上的连通分量，则称顶点v为关节点。没

21、有关节点的连通图叫做重连通图。在重连通图上,任何一对顶点之间至少存在有两条路径,在删去某个顶点及与该顶点相关联的边时,也不破坏图的连通性。一个连通图G如果不是重连通图，那么它可以包括几个重连通分量。,45,在一个无向连通图G中,重连通分量可以利用深度优先生成树找到。在图中各顶点旁标明的深度优先数,给出进行深度优先搜索时各顶点访问的次序。深度优先生成树的根是关节点的充要条件是它至少有两个子女。其它顶点 u 是关节点的充要条件是它至少有一个子女 w,从 w 出发,不能通过 w、w 的子孙及一条回边所组成的路径到达 u 的祖先。,46,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,

22、G,H,J,A,B,C,D,E,F,G,H,J,I,I,1,2,3,4,5,6,7,8,9,10,根有两 个子女,关节点,关节点,关节点,47,连通图和它的连通分量,48,最小生成树(minimum cost spanning tree),使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。构造最小生成树的准则必须使用且仅使用该网络中的n-1 条边来联结网络中的 n 个顶点；不能使用产生回路的边；各边上的权值的总和达到最小。,49,普里姆(Prim)算法,普里姆算法的基本思想：从连通

23、网络 N=V,E 中的某一顶点 u0 出发,选择与它关联的具有最小权值的边(u0,v),将其顶点加入到生成树顶点集合U中。以后每一步从一个顶点在 U 中,而另一个顶点不在 U 中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合 U 中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合 U 中为止。采用邻接矩阵作为图的存储表示。,50,25,25,10,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,5,0,4,6,1,3,2,5,0,4,6,1,3,2,10,原图(a)(b),5,0,4,6,1,3,2,10,(c)(d)(e)(f),5,0,4,

24、6,1,3,2,10,22,12,5,0,4,6,1,2,10,25,14,22,16,12,3,25,22,12,51,在构造过程中，还设置了两个辅助数组：lowcost 存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；nearvex 记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。例子,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,12,52,若选择从顶点0出发，即u0=0，则两个辅助数组的初始状态为：然后反复做以下工作：在 lowcost 中选择 nearvexi-1&lowcosti最小的边,用 v 标记它。则选中的权值最小

25、的边为(nearvexv,v),相应的权值为 lowcostv。,0 28 10,-1 0 0 0 0 0 0,lowcost,nearvex,0 1 2 3 4 5 6,53,将 nearvexv 改为-1,表示它已加入生成树顶点集合。将边(nearvexv,v,lowcostv)加入生成树的边集合。取 lowcosti=min lowcosti,Edgevi，即用生成树顶点集合外各顶点 i 到刚加入该集合的新顶点 v 的距离 Edgevi 与原来它们到生成树顶点集合中顶点的最短距离lowcosti 做比较,取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离。,54,如果生成树顶点

26、集合外顶点 i 到刚加入该集合的新顶点 v 的距离比原来它到生成树顶点集合中顶点的最短距离还要近，则修改nearvexi:nearvexi=v。表示生成树外顶点i到生成树内顶点v当前距离最近。,0 28 10,-1 0 0 0 0 0 0,lowcost,nearvex,0 1 2 3 4 5 6,选 v=5,选边(0,5),55,顶点v=5加入生成树顶点集合：,0 28 25 10,-1 0 0 0 5-1 0,lowcost,nearvex,0 1 2 3 4 5 6,选 v=4,选边(5,4),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(0,5,

27、10)加入生成树,12,0,4,6,1,3,2,10,25,5,56,0 1 2 3 4 5 6,顶点v=4加入生成树顶点集合：,0 28 22 25 10 24,-1 0 0 4-1-1 4,lowcost,nearvex,选 v=3,选边(4,3),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(5,4,25)加入生成树,12,5,0,4,6,1,3,2,10,25,22,57,顶点v=3加入生成树顶点集合：,0 28 12 22 25 10 18,-1 0 3-1-1-1 3,lowcost,nearvex,0 1 2 3 4 5 6,选 v=2,选

28、边(3,2),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(4,3,22)加入生成树,12,5,0,4,6,1,3,2,10,25,22,12,58,lowcost,nearvex,0 1 2 3 4 5 6,顶点v=2加入生成树顶点集合：,0 16 12 22 25 10 18,-1 2-1-1-1-1 3,选 v=1,选边(2,1),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(3,2,12)加入生成树,12,5,0,4,1,3,2,10,25,22,16,12,59,顶点v=1加入生成树顶点集合：,0 16

29、12 22 25 10 14,-1-1-1-1-1-1 1,lowcost,nearvex,0 1 2 3 4 5 6,选 v=6,选边(1,6),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(2,1,16)加入生成树,12,5,0,4,6,1,3,2,10,25,14,22,16,12,60,lowcost,nearvex,0 1 2 3 4 5 6,顶点v=6加入生成树顶点集合：,0 16 12 22 25 10 14,-1-1-1-1-1-1-1,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(1,6,14)加

30、入生成树,12,5,0,4,6,1,3,2,10,25,14,22,16,12,61,最后生成树中边集合里存入得各条边为：(0,5,10),(5,4,25),(4,3,22),(3,2,12),(2,1,16),(1,6,14),利用普里姆算法建立最小生成树void Prim(Graph G,MST/及最短带权路径,62,nearvexu=-1;/加到生成树顶点集合 int k=0;/存放最小生成树结点的变量 for(i=0;i G.n;i+)if(i!=u)/循环n-1次,加入n-1条边 EdgeData min=MaxValue;int v=0;for(int j=0;j NumVerti

31、ces;j+)if(nearvexj!=-1/求生成树外顶点到生成树内顶点具有最/小权值的边,v是当前具最小权值的边,63,if(v)/v=0表示再也找不到要求顶点 Tk.tail=nearvexv;/选边加入生成树 Tk.head=v;Tk+.cost=lowcostv;nearvexv=-1;/该边加入生成树标记 for(j=0;j G.n;j+)if(nearvexj!=-1,64,/循环n-1次,加入n-1条边分析以上算法,设连通网络有 n 个顶点,则该算法的时间复杂度为 O(n2),它适用于边稠密的网络。注意：当各边有相同权值时，由于选择的随意性，产生的生成树可能不唯一。当各边的权值

32、不相同时，产生的生成树是唯一的。,65,活动网络(Activity Network),计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。,用顶点表示活动的网络(AOV网络),66,C1 高等数学 C2 程序设计基础 C3 离散数学 C1,C2 C4 数据结构 C3,C2 C5 高级语言程序设计 C2 C6 编译方法 C5,C

33、4 C7 操作系统 C4,C9 C8 普通物理 C1 C9 计算机原理 C8,课程代号 课程名称 先修课程,67,学生课程学习工程图,C8,C3,C5,C4,C9,C6,C7,C1,C2,68,可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边表示活动Vi 必须先于活动Vj 进行。这种有向图叫做顶点表示活动的AOV网络(Activity On Vertices)。在AOV网络中不能出现有向回路,即有向环。如果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的AOV网络，必须先判断它是否存在有向环。,69,检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即

34、将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中,则该网络中必定不会出现有向环。,70,如果AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。例如,对学生选课工程图进行拓扑排序,得到的拓扑有序序列为 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,71,拓扑排序的方法,输入AOV网络。

35、令 n 为顶点个数。在AOV网络中选一个没有直接前驱的顶点,并输出之;从图中删去该顶点,同时删去所有它发出的有向边;重复以上、步,直到 全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或 图中还有未输出的顶点,但已跳出处理循环。说明图中还剩下一些顶点,它们都有直接前驱。这时网络中必存在有向环。,72,C0,C1,C2,C3,C4,C5,拓扑排序的过程,(a)有向无环图,C2,C5,C1,C0,C3,(b)输出顶点C4,C1,C2,C5,C3,(c)输出顶点C0,C4,C0,C2,C5,C1,C3,(d)输出顶点C3,73,C1,C2,C5,(e)输出顶点C2,C5,C1,(f)输出顶点C1,

36、C5,(g)输出顶点C5,最后得到的拓扑有序序列为 C4,C0,C3,C2,C1,C5。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。,(h)拓扑排序完成,74,AOV网络及其邻接表表示,C0,C1,C2,C3,C4,C5,C0 C1 C2 C3 0 C4 C5 0,012345,count data adj,130103,1,dest link,3 0,5,1,5 0,0,1,5 0,75,在邻接表中增设一个数组count，记录各顶点入度。入度为零的顶点即无前驱顶点。在输入数据前,顶点表VexList 和入度数组count 全部初始化。在

37、输入数据时,每输入一条边,就需要建立一个边结点,并将它链入相应边链表中,统计入度信息：EdgeNode*p=new EdgeNode;p-dest=k;/建立边结点 p-link=G.VexListj.firstAdj;VexListj.firstAdj=p;/链入顶点 j 的边链表的前端 countk+;/顶点 k 入度加一,76,在算法中,使用一个存放入度为零的顶点的链式栈,供选择和输出无前驱的顶点。拓扑排序算法可描述如下：建立入度为零的顶点栈;当入度为零的顶点栈不空时,重复执行 从顶点栈中退出一个顶点,并输出之;从AOV网络中删去这个顶点和它发出的边,边的终顶点入度减一;如果边的终顶点入

38、度减至0,则该顶点进入度为零的顶点栈;如果输出顶点个数少于AOV网络的顶点个数,则报告网络中存在有向环。,77,拓扑排序的算法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;return;,78,else/继续拓扑排序 Pop(S,j);/退栈 cout d

39、est;/另一顶点 if(-countk=0)/顶点入度减一 Push(S,k);/顶点的入度减至零,进栈 p=p-link;,79,用边表示活动的网络(AOE网络),如果在无有向环的带权有向图中,用有向边表示一个工程中的活动(Activity),用边上权值表示活动持续时间(Duration),用顶点表示事件(Event),则这样的有向图叫做用边表示活动的网络,简称 AOE(Activity On Edges)网络。AOE网络在某些工程估算方面非常有用。例如，可以使人们了解：完成整个工程至少需要多少时间(假设网络中没有环)?,80,为缩短完成工程所需的时间,应当加快哪些活动?从源点到各个顶点,

40、以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同,但只有各条路径上所有活动都完成了,整个工程才算完成。因此,完成整个工程所需的时间取决于从源点到汇点的最长路径长度,即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。,81,a9=6,1,3,2,4,a1=8,a2=12,5,6,7,8,a10=12,a8=18,a5=28,a6=8,a7=6,a3=14,a4=10,要找出关键路径，必须找出关键活动,即不按期完成就会影响整个工程完成的活动。关键路径上的所有活动都是关键活动。因此,只要找到

41、了关键活动,就可以找到关键路径。例如,下图就是一个AOE网。,82,定义几个与计算关键活动有关的量：,事件Vi 的最早可能开始时间Ve(i)是从源点V0 到顶点Vi 的最长路径长度。事件Vi 的最迟允许开始时间Vli 是在保证汇点Vn-1 在Ven-1 时刻完成的前提下，事件Vi 的允许的最迟开始时间。活动ak 的最早可能开始时间 ek 设活动ak 在边上,则ek是从源点V0到顶点Vi 的最长路径长度。因此,ek=Vei。活动ak 的最迟允许开始时间 lk,83,lk是在不会引起时间延误的前提下,该活动允许的最迟开始时间。lk=Vlj-dur()。其中,dur()是完成 ak 所需的时间。时间

42、余量 lk-ek 表示活动 ak 的最早可能开始时间和最迟允许开始时间的时间余量。lk=ek 表示活动 ak 是没有时间余量的关键活动。为找出关键活动,需要求各个活动的 ek 与 lk，以判别是否 lk=ek。,84,为求得 ek与 lk,需要先求得从源点 V0 到各个顶点 Vi 的 Vei 和 Vli。求Vei的递推公式 从 Ve0=0 开始，向前递推 S2,i=1,2,n-1S2是所有指向Vi的有向边的集合。从Vln-1=Ven-1开始，反向递推 S1,i=n-2,n-3,0S1是所有源自Vi的有向边的集合。,85,这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。设活动ak

43、(k=1,2,e)在带权有向边 上,其持续时间用dur()表示,则有 ek=Vei；lk=Vlj-dur()；k=1,2,e。这样就得到计算关键路径的算法。为了简化算法,假定在求关键路径之前已经对各顶点实现了拓扑排序,并按拓扑有序的顺序对各顶点重新进行了编号。,86,1,3,2,4,a1=8,a2=12,5,6,7,8,a10=12,a9=6,a8=18,a5=28,a6=8,a7=6,a3=14,a4=10,VeVl,1 2 3 4 5 6 7 8,0 8 12 22 28 40 46 58 0 8 12 22 28 40 46 58,el,0 0 8 12 12 22 22 28 40 4

44、60 0 8 12 12 32 22 28 40 46,1 2 3 4 5 6 7 8 9 10,87,事件 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 14l-e 0 2 3 0 2 3 0 0 3 0 0关键 是 是 是 是 是 是,88,利用关键路径法求AOE网的各关键活动void graph:Cri

45、ticalPath()/在此算法中需要对邻接表中单链表的结点加以/修改,在各结点中增加一个int域 cost,记录该结/点所表示的边上的权值。int i,j;int p,k;int e,l;Ve=new intn;Vl=new intn;for(i=0;i*p=NodeTablei.adj;/该顶点边链表链头指针p while(p!=NULL)/找所有后继邻接顶点 k=pdest;/i的后继邻接顶点k if(Vei+pcost Vek)Vek=Vei+pcost;p=plink;/找下一个后继,89,for(i=0;i n;i+)Vli=Ven-1;/逆向计算事件的最迟开始时间 for(i=n

46、-2;i;i-)/按逆拓扑有序顺序处理 p=NodeTablei.adj;/该顶点边链表链头指针p while(p!=NULL)k=pdest;/i的后继邻接顶点k if(Vlk-pcost Vli)Vli=Vlk-pcost;p=plink;/找下一个后继,90,for(i=0;i”“是关键活动”endl;p=plink;/找下一个后继,91,注意,在拓扑排序求Vei和逆拓扑有序求Vli时,所需为 O(n+e),求各个活动的ek和lk时所需时间为O(e),总 共花费时间仍然是O(n+e)。所有顶点按拓扑有序的次序编号仅计算 Vei 和 Vli 是不够的，还须计算 ek 和 lk。不是任一关键

47、活动加速一定能使整个工程提前。想使整个工程提前，要考虑各个关键路径上所有关键活动。,92,最短路径(Shortest Path),最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。问题解法 边上权值非负情形的单源最短路径问题 Dijkstra算法 边上权值为任意值的单源最短路径问题 Bellman和Ford算法所有顶点之间的最短路径 Floyd算法,93,边上权值非负情形的单源最短路径问题,问题的提法：给定一个带权有向图D与源点 v，求从 v 到D中其它顶点的最短路径。限定各边上的权值大于或等于0。为

48、求得这些最短路径,Dijkstra提出按路径长度的递增次序,逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。举例说明,94,Dijkstra逐步求解的过程,1,0,4,3,2,10,100,30,50,20,60,10,源点 终点 最短路径 路径长度,v0 v1(v0,v1)10 v2(v0,v1,v2)(v0,v3,v2),60,50 v3(v0,v3)30 v4(v0,v4)(v0,v3,v4)(v0,v3,v2,v4)100,90,60,95,引入辅助数组dist。它的每一个分量dist

49、i表示当前找到的从源点 v0到终点 vi 的最短路径的长度。初始状态：若从源点v0到顶点 vi 有边,则disti为该边上的权值；若从源点v0到顶点 vi 无边,则disti为。假设 S 是已求得的最短路径的终点的集合，则可证明：下一条最短路径必然是从v0 出发，中间只经过 S 中的顶点便可到达的那些顶点vx(vxV-S)的路径中的一条。每次求得一条最短路径后,其终点vk 加入集合S，然后对所有的vi V-S，修改其 disti值。,96,Dijkstra算法,初始化：S v0;distj Edge0j,j=1,2,n-1;/n为图中顶点个数 求出最短路径的长度：distk min disti

50、,i V-S;S S U k;修改：disti min disti,distk+Edgeki,对于每一个 i V-S;判断：若 S=V,则算法结束，否则转。,97,void ShortestPath(MTGraph G,int v)/MTGraph是一个有 n 个顶点的带权有向图,各边上的权值由Edgeij给出。/distj,0 jn,是当前求到的从顶点v 到顶点 j 的最短路径长度,用数组pathj,0 jn,存放求到的最短路径。EdgeData distG.n;/最短路径长度数组 int pathG.n;/最短路径数组 int SG.n;/最短路径顶点集,计算从单个顶点到其它各顶点最短路径