内蒙古大学《算法与数据结构》课件第6章图

1、6.1 图的基本概念6.2 图的存储结构6.3 图的遍历6.4 无向图的应用6.5 有向图的应用 6.6 最短路径 第六章 图 16.1 图的基本概念图定义 图是由顶点集合(V)及顶点间的关系集合E所组成的一种数据结构： Graph(V, E)其中 V = x | x 某个数据对象 是顶点的非空有限集合； E = (x, y) | x, y V /边(Edge)集合 或 E = | x, y V /弧(Arc)集合 是顶点之间关系的有限集合.2无向图无向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集;E(G)是边的有限集 合，边是顶点的无序对, 记为(v,w)或(w,

2、v)， 并且（v,w)=(w,v)有向图有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集;E(G)是有向边(也称 弧）的有限集合，弧是顶点的有序对，记为 ，v,w是顶点，v为弧尾(或始点)， w为弧头(终点). 6.1 图的基本概念3例1245136G2图G2：V(G2)=1,2,3,4,5,6 E(G2)=, , , , , , 例2157324G16图G1：V(G1)=1,2,3,4,5,6,7E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)6.1 图的基本概念4本章只讨论简单图,即有两类图形不在本章讨论

3、之列：6.1 图的基本概念5(无向)完全图(Completed graph) : n个顶点的有n(n-1)/2条边的简单无向图.6.1 图的基本概念有向完全图: n个顶点的有n(n-1)条弧的简单有向图. 稀疏图(sparse graph)： 边或弧很少的图，通常边数enlog2n稠密图(Dense graph): 无向图中，边数接近n(n-1)/2 ； 有向图中，弧数接近n(n-1)6有向网权与图的边或弧相关的数.网带权的无向图称为无向网; 带权的有向图称为有向网;6.1 图的基本概念无向网7子图已知图G(V,E)和图G(V,E), 若满足：VV且 EE 则称G为G的子图6.1 图的基本概念

4、8邻接点(或相邻点),关联: 如果 e=(u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接点或相邻点;称边e与顶点u,v关联; 如果 a= 是 E(G) 中的一条弧，则称u邻接到v 或v邻接于u,也称弧a与顶点u,v关联.6.1 图的基本概念9顶点的度（与树中结点的度不同）:无向图中，顶点v的度是与该顶点v关联的边数, 记作TD(v)有向图中，顶点v的度分成入度与出度入度：以该顶点v为终头的弧的数目,记为ID(v)出度：以该顶点v为始点的弧的数目,记为OD(v)一个顶点v的度等于该顶点的入度与出度之和,即TD(v)=OD(v)+ID(v)6.1 图的基本概念10(有向)路径顶点

5、的序列(Vi0,Vi1 , , Vik)， 满足(Vij-1,Vij)E 或 E，(1jk)路径长度沿路径边的数目或沿路径各边权值之和。简单路径序列中顶点不重复出现的路径。回路第一个顶点和最后一个顶点相同的路径。简单回路除了第一个顶点和最后一个顶点外，其 余顶点不重复出现的回路。6.1 图的基本概念11V0V1V3V2V0V1V3V0V1V2V0V1V3V06.1 图的基本概念12连通图与连通分量ABCDEHMFGIJLK无向图G的三个连通分量ABCDEFGIJLHMK无向图G6.1 图的基本概念在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是

6、连通的, 则称此图是连通图。非连通图的极大连通子图称做连通分量。13强连通图与强连通分量在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的有向路径, 则称此图是强连通图。非强连通图的极大强连通子图称做强连通分量。强连通图6.1 图的基本概念非强连通图G非强连通图G两个 强连通分量14生成树：包含图中全部n个顶点的一个极小连通子图;如果在生成树上添加1条边，必定构成一个回路.若图中有n个顶点，却少于n-1条边，必为非连通图。ABCDEHM无向图G ABCDEHM无向图G的生成树 6.1 图的基本概念15生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最

7、少的。6.1 图的基本概念FGIJLK生成森林ABCDEFGIJLHMK无向图GABCDEHM16class Graph /图是由一个顶点的非空有限集合和一个边或弧的集合组成。 public: Graph ( ); /建立一个空图 void InsertVertex ( Type & vertex ); / 在图中插入一个顶点vertex void InsertEdge(int v1，int v2 ); / 在图中插入一条边(v1，v2)或一条弧 void RemoveVertex ( int v ); / 删除一个顶点v void RemoveEdge ( int v1，int v2 );

8、/删除一条边(v1，v2)或一条弧 int IsEmpty ( ); / 判断图中是否有顶点，若无则返回1，否则返回0 DataType GetWeight ( int v1，int v2 ); / 函数返回边(v1，v2)或弧的权值 int GetFirstNeighbor ( int v ); / 函数返回顶点位置v的第一个邻接顶点的位置，若找不到，则函 / 数返回-1 int GetNextNeighbor ( int v1，int v2 ); / 函数返回顶点位置v1相对于v2的下一个邻接顶点的位置,若找不到， /则函数返回-1图的抽象数据类型说明：176.2 图的存储表示设图 G =

9、 (V, E)是一个有 n 个顶点的图，则G的邻接矩阵是如下定义的n*n的矩阵AG=Aijn*n：6.2.1 邻接矩阵或相邻矩阵若(vi，vj)E或E0 反之Aij=18无向图的邻接矩阵是对称的，有向图的邻接矩阵不一定对称的。19在无向图中, 第 i 行 (列) 1 的个数即为顶点i 的度。在有向图中, 第 i 行 1 的个数即为顶点 i 的出度，第 j 列1 的个数即为顶点 j 的入度。在邻接矩阵中：20网（带权图）的邻接矩阵Aij= 0 i=j 其它 wij 若(vi，vj)E 或 E 21用邻接矩阵表示的图的类的定义class AdjMatrix / 非带权图 int n； / 顶点的个

10、数 int matrixMaxSize MaxSize； / 邻接矩阵 public: AdjMatrix(int m) n=m； ; / AdjMatrix class AdjMatrix / 带权图 const int INFINITE=； int n； /顶点的个数 float matrixMaxSizeMaxSize； / 邻接矩阵 public: AdjMatrix(int m) n=m； 22 void CreateGraph() ; / 建立一个图G的邻接矩阵matrix void LocateVex(v) ; / 确定图G中顶点v在顶点中的位置 void GetVex(v);

11、/ 得到图G中顶点v的值 int FirstAdjVex(v); / 确定图G中顶点出v的第一个邻接点 int NextAdjVex(v,w); / 确定图G中顶点出v相对于w的下一个邻接点 void DFSTraverse(int v)； / 从顶点v开始对图进行深度优先遍历 void BFSTraverse(int v)； / 从顶点v开始对图进行广度优先遍历; / AdjGraph23假定图以邻接矩阵G存储:int AdjMatrix :FirstAdjVex(int v) int w=0; while(wn & matrixvw=0)w+; if(wn) return w; else

12、-1; 算法的时间复杂度为：(n)24假定图以邻接矩阵G存储 int NextAdjVex(int v,int w) u=w+1; while(un & matrixvu=0)u+; if(ufirstout) /书上没有 return gheadv-firstout.adjvex； else return -1; /书上没有/ FirstAdjVex转int NextAdjVex(int v，int w) p=gheadv-firstout；while (p & p-adjvex!=w) p=p-link；if (!p | !p-link) return -1； /书上为0else retu

13、rn p-link-adjvex；/ NextAdjVex326.2.3 邻接多重表表示法 邻接多重表是只用来存储无向图的另一种存储结构 .在邻接多重表表示法中每一条边只对应一个边结点（EdgeNode），每一个顶点也对应一个顶点结点（VNode）。在边结点中，每一条边对应的边结点有五个域：EdgeNode mark vex1 vex2 link1 link2 33其中：mark是标志域，标记该边是否被遍历 过；vex1与vex2是该边所关联的两个顶点在图中的序号；link1是指向下一条与顶点vex1相关联的边；link2是指向下一条与顶点vex2相关联的边。其中：data是存放该顶点相关信息

14、；firstEdge是指向第一条与顶点相关联的边。VNode data firstEdge 34邻接多重表类型说明如下：class EdgeNode / 边结点 Tag mark； /访问标记 int vex1,vex2； / 该边所指向的顶点的序号 EdgeNode *link1，*link2； / 指向下一条边的指针 public: EdgeNode(int adj) ;/ EdgeNodeclass VNode / 顶头结点DataType data； / 顶点的信息EdgeNode *firstEdge / 指向与该顶点所关联的一条的指针35public: VNode (DataTyp

15、e e) data=e; firstEdge=NULL;/ VNodeclass MulistGragh /邻接多重表 int n； / 顶点的个数Node VheadMaxSize； public: MulistGragh (int m) n=m； void CreateGraph(g ) ； / 建立图gvoid LocateVex(u) ； / 得到顶点v在图中的序号 void GetVex(v) ； / 得到顶点v的值void PutVex(v，value) ； / 把v的值赋为value void FirstAdjVex(v) ； / 得到顶点v的第一个邻接顶点 void NextA

16、djVex(v, w); / 确定图G中顶点出v相对于w的下一个邻接点36void DFSTraverse(int v)； / 从顶点v开始对图进行深度优先遍历void BFSTraverse(int v); / 从顶点v开始对图进行广度优先遍历; /MulistGragh376.2.4 十字链表十字链表是只用来存储有向图的另一种存储结构。可以把十字链表看成是将有向图的邻接表和逆邻接表结合起来而得到的一种链表 有向图中每一条弧对应于一个弧结点（ArcNode），每个顶点也对应于一个顶点结点（Vnode）。在弧结点中，每一条弧对应的弧结点有五个域。弧结点 mark hvex tvex hlink

17、tlink38其中：mark表示是否遍历过，hvex表示该弧的弧尾顶点在图中的位置，tvex表示该弧的弧头顶点在图中的位置，hlink指向弧头相同的下一条弧，tlink指向弧尾相同的下一条弧。其中：data存放该顶点相关信息，firstin指向该顶点为弧头的第一个弧结点，firstout指向该顶点为弧尾的第一个弧结点。顶点结点 ：datafirstinfirstout39有向图以及十字链表 40十字链表类型说明如下：class ArcNode / 弧结点 Tag mark； /访问标记 int hvex,tvex; /与该弧所关联的两个顶点的序号 ArcNode *hlink,*tlink；

18、/ 分别指向与该弧所关联的两个顶点的下一条弧 public: ArcNode(int adj); ;/ ArcNodeclass VNode / 顶头结点 DataType data； / 顶点的信息 ArcNode *firstin,*firstout； /分别指向该顶点第一条入弧和出弧public: VNode (DataType e) data=e;firstin=firstout=NULL;/ VNode 41class MulistGragh / 十字链表 int n； / 顶点的个数 Node VheadMaxSize； public: MulistGragh (int m) n=

19、m； void CreateGraph(g)； / 建立图g void LocateVex(v)； / 得到顶点v在图中的序号 void GetVex(v)； / 得到顶点v的值 void PutVex(v，value)； / 把v的值赋为value void FirstAdjVex(v) / 得到顶点v的第一个邻接点 void NextAdjVex(v / 得到顶点v的下一个邻接点 void DFSTraverse(int v)； / 从顶点v开始对图进行深度优先遍历 void BFSTraverse(int v)； / 从顶点v开始对图进行广度优先遍历;/ MulistGragh426.3

20、 图的遍历从图中某一顶点出发，按照某种搜索路径访问图中所有的顶点，使得每个顶点被访问一次且仅被访问一次，这个过程称为图的遍历。深度优先遍历(搜索)广度优先遍历(搜索)图的两种遍历方法43从图中某一起始点 v 开始，访问v，然后从 v 出发，访问它的第一个邻接点 w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问， 如此进行下去，直到某一顶点所有的邻接点都被访问完。则退回到上一步刚访问过的顶点，看是否还有其它没有被访问的邻接点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回上一步进行搜索。重复上述过程，直

21、到连通图中所有顶点都被访问过为止。6.3.1 深度优先遍历DFS ( Depth First Search )DFS算法思想：44深度优先遍历DFS ( Depth First Search )深度优先搜索的示例深度优先搜索过程 深度优先生成树DFS序列：ABEGCFDHI45 为了避免重复访问,设置一个辅助数组 visitedn. 它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就把 visitedi置为 1，以防它多次被访问。图中可能存在回路，且图的任一顶点都可能与其它顶点相邻，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。深度优先遍历DFS算法思想:46

22、连通图的深度优先遍历算法如下: void DFS(int v) /从顶点v出发访问包含该顶点v的最大连通子图中的所有顶点 visitedv=1； visit(v)； /或coutv; for (w=FirstAdjVex(v)；w!=-1；w=NextAdjVex(v,w) if (!visitedw) DFS(w)； / DFS47 图的深度优先遍历算法如下:void DFSTraverse( ) /深度优先求图的连通分量 int visitedn； /设置访问标志数组 for (v=0；vn；v+) visitedv=0； /初始化访问标志数组 for (v=0；vn；v+) if (!v

23、isitedv) DFS(v)； /每次从尚未访问过的顶点中选取一个顶点v，从顶点/v出发进行调用DFS(v)/ DFSTraverse48假定图以邻接矩阵G存储:int FirstAdjVex(int v) int w=0; while(wn & matrixvw=0)w+; if(wn) return w; else -1; 算法的时间复杂度为：(n)49假定图以邻接矩阵G存储 int NextAdjVex(int v,int w) u=w+1; while(un & matrixvu=0)u+; if(ufirstout) return gheadv-firstout.adjvex； e

24、lse return -1;/ FirstAdjVex算法的时间复杂度为：(1)51int NextAdjVex(int v，int w) p=gheadv-firstout； while (p & p-adjvex!=w) p=p-link； if (!p | !p-link) return -1； else return p-link-adjvex；/ NextAdjVex假定图以邻接表G存储：算法的时间复杂度为：(TD(v)52算法分析：图中有 n 个顶点，e 条边。如果用邻接矩阵存储图，则查找每一个顶点的所有相邻顶点，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。 如

25、果用邻接表存储图，在每一个单链 表中可以找到某个顶点 v 的所有邻接顶点 w。由于总共有 2e 个边结点(无向图)，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。53在访问了起始顶点 v 之后，由 v 出发，依次访问 v 的所有未被访问过的邻接点 w1, w2, , wt，然后再顺序访问 w1, w2, , wt 的所有未被访问过的邻接点。再从这些访问过的顶点出发，再访问它们的所有未被访问过的邻接点， ，如此重复,直到图中所有顶点都被访问完为止。6.3.2 广度优先遍历BFS ( Breadth First Search )54广度优先遍历的示例

26、 广度优先搜索过程 广度优先生成树BFS序列：ABCDEFGFI55为了实现逐层访问，算法中使用了一个队列，以保存正在访问的顶点，以便向下一层访问。广度优先遍历是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先遍历不是一个递归的过程，其算法也不是递归的。与深度优先遍历过程一样，为避免重复访问，需要一个辅助数组 visitedn，对被访问过的顶点加以标记。56图的广度优先遍历（BFS）算法思想：（1）清队列Q；（2）对出发顶点v做：v入队；标记v；（3）当队列Q不空反复做： (a) 出队头元素到u；访问u; (b) 将u的未被访问的邻接点w入队

27、；标记w；57图的广度优先搜索算法：void BFS(int v) /广度优先求图的连通分量 Q=new Queue( )； /清队列Q Q.Enter(v)； /将起始顶点v入队 visitedv=1； /标记v while (!Q.IsEmpty() /队列Q不空 u=Q.Leave()； /出队头元素到u visited(u)； /访问u for (w=FirstAdjVex(u)；w!=-1；w=NextAdjVex(u，w) if (!visitedw) Q.Enter(w)； /将u的每个未被访问的邻接点w 入队 visitedw=1； / BFS58BFS从出发点只能遍历一个连通

28、分量，若对任意图的遍历需要对每个分量中一个未被访问的顶点为出发点进行BFS遍历。算法如下：void BFSTraverse() /广度优先求图的连通分量 int visitedn； /设置访问标志数组 for (v=0；vn；v+) visitedv=0； /初始化访问标志 for (v=0；v n; /输入顶点个数 G = new gheadn; /创建顶点表数组 for ( int i = 0; i data; G.gheadi.data=data; VertexPosi=data; cin head tail weight; /weight可省 while(head!=-1) j = L

29、ocateVex ( head ); k = LocateVex ( tail ); InsertEdge ( k, j, weight );/weight可省 616.4 无向图的应用6.4.1 最小生成树(MST)( Minimum-cost Spanning Tree )生成树： 包含连通无向图中全部顶点的极小连通子图。 按照生成树的定义，n 个顶点的连通无向图的生 成树有 n 个顶点、n-1 条边。 生成树不唯一。最小生成树(MST): 连通无向网中边权之和最小的生成树。62假设在n个城市之间要建立通信网络线，要求使得每个城市之间连通且费用最少。MST典型用途：数学模型：顶点表示城市，

30、有n个；边表示线路；边的权值表示线路的经济代价；连通网表示n个城市间通信网。问题抽象： n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST281234567101614181225242263求一个连通无向网中最小生成树的方法: Prim算法 Kruskal算法都是利用MST的性质构造最小生成树64MST性质内容如下：设G=（V，E）是连通无向网，对V的非空真子集U V，若（u，v）是一条具有最小权值的边，其中uU，vV-U，则必存在一棵包含边(u，v)的最小生成树。uvUV-UV图G65证明：（反证法:假设满足条件的边（u，v）不在任一

31、最小生成树中）设G的任何MST都不包含（u,v）。设T是G的一棵MST，将（u,v）加入T，形成回路。去掉（u,v）得到T , 因 wuvwuv，所以T 的边权之和小于T 的边权之和，与T是MST矛盾。UuuV-UvvMST的性质：66Prim算法的基本思想： （1）设T是G上最小生成树中边的集合，初始为空. 选取任意一个顶点u加入U；（2）在所有uU，vV-U的边 (u，v)E中找一条权 最小的边 (u，v) 加入集合T中，同时v加入U； （3）重复（2），直到U=V为止。671237456281612222510251418Prim算法过程示例 T= U=168Prim算法过程示例1237

32、456281612222510251518 Min10, 28=10 T=(1,6) U=1,6691237456281612222510251518Prim算法过程示例 Min25, 28=25 T=(1,6),(6,5) U=1,6,5701237456281612222510251518Prim算法过程示例 Min28，25，22=22 T=(1,6),(6,5),(5,4) U=1,6,5,4712812374561612222510251518Prim算法过程示例 Min28，25，18，12=12 T=(1,6),(6,5),(5,4),(4,3) U=1,6,5,4,372123

33、7456281612222510251518Prim算法过程示例 Min15，25，18=15 T=(1,6),(6,5),(5,4),(4,3),(3,2),(2,7) U=1,6,5,4,3,2,7731237456281612222510251518Prim算法过程示例 Min28，25，18，16=16 T=(1,6),(6,5),(5,4),(4,3),(3,2) U=1,6,5,4,3,2741237456281612222510251518Prim算法过程示例 U=V, 算法结束 T=(1,6),(6,5),(5,4),(4,3),(3,2),(2,7)75在构造过程中，还设置了

34、一个辅助数组closedgen，每个元素closedgev有两个域： lowcost 存放生成树顶点集合内顶点到生成树外各顶点的各 边上的当前最小权值； adjvex 记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。存储: 邻接矩阵。Prim算法的实现:lowcostadjvex76利用Prim算法求最小生成树的算法:class AddArray int adjvex; float lowcost; ;/ AddArrayvoid MinSpanTree_Prim(int u,AddArray closedge, AddArray edge,AdjMatrix G)/ 设图以邻

35、接矩阵存储，用Prim算法从顶点u出发构造网G的最小生/成树且保存到数组edge中 for(v=0；vn；v+) Uv=0； Uu=1； for (v=0；v n；v+) /初始化辅助数组closedge if（u!=v) closedgev.adjvex=u; closedgev.lowcost=G.matrixuv; 77 for (t=1；tn；t+) /选择其余的n-1个顶点 k=minimum(closedge)； /求出T的下一个顶点k顶点 u=closedgek.adjvex； edgek.lowcost=matrixku; /保存选中边的权值 edgek.adjvex=u; /

36、保存选中边的顶点 Uk=1； for (j=0；jn；j+) if (Uj=0 & G.matrixkjclosedgej.lowcost) closedgej.lowcost=matrixkj； closedgej.adjvex=k； / for / MinSpanTree_Prim78 iclosedge1 23456UV-UedgeAdjvexLowcost 028000010001，2，3，4，5，6510AdjvexLowcost 0280052501000，51，2，3，4，6425AdjvexLowcost 02804225250104240，5，41，2，36322Adjvex

37、Lowcost 028312422525v0103180，5，4，31，2，6212AdjvexLowcost 2163124225240103180，5，4，3，21，6116AdjvexLowcost 2163124225240101140，5，4，3，2，16614AdjvexLowcost 2163124225240101140，5，4，3，2，1，6 表6.1 从顶点0出发利用Prim算法构造最小生成树过程中辅助数组各分量的值的变化79设连通无向网有 n 个顶点, 则该算法的时间复杂度为O(n2)。Prime算法分析它适用于边稠密的网络。802、Kruscal 算法基本思想: 先构造

38、一个只含 n 个顶点的零图 ST ，然后从权值最小的边开始，若它的添加不使 ST 产生回路，则在 ST上加上这条边，如此重复，直至加上 n-1 条边为止。81已知连通无向网G = ，初始 ST=; k = 0; / k 记选中的边数 while (kn-1) 从边集 E 中选取权值最小的边(u,v); 若(u,v)加入ST后不使ST中产生回路，则将 边(u,v)加入到TE中，从E中去掉边(u,v) ； k+;Kruscal 算法思想描述:8250461321025152422161812285046132504613210504613210121550461321012155046132101

39、216应用Kruscal算法构造最小生成树的过程原图83155046132101216222515504613210121622应用Kruscal算法构造最小生成树的过程原图5046132102515242216181228846.5 有向图的应用 有向图可以用来表示工程的实施、产品的流 图、程序流程和学生的课程安排等。6.5.1 拓扑排序 图可以用来描述一个工程或一个系统的进行过程。除最简单的工程外，几乎所有的工程都可分成若干个活动的子工程，完成了这些子工程也就完成了整个工程。 85例如在工程的实施中，一个工程往往由若干个子工程组成，除了很小的工程外，一般都把工程分为若干个称做“活动”的子工

40、程。完成了这些活动，该工程就可以结束。而这些子工程间有两种关系：一是它们之间有先后顺序关系，即一个工程结束后另一个子工程才能开始；二是它们之间无先后顺序关系，即两个子工程谁先谁后都互不影响。6.5.1 拓扑排序86例如学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求有先修课程，有些则不要求。即有的课程之间有先后顺序关系，而有的课程可以并行地学习。AOV (Activity On Edges）网: 用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网。6.5.1 拓扑排序87 C1 高等数学 C2 计算机基础 C3 离散数学 C1, C2 C4 数

41、据结构 C3, C2 C5 高级语言 C2 C6 编译原理 C5, C4 C7 操作系统 C4, C9 C8 普通物理 C1 C9 计算机原理 C8 课程代号课程名称先修课程88学生课程学习工程图6.5.1 拓扑排序89拓扑(有序)序列：在AOV网中若将各个顶点 (代表各个活动)排列成一个线性有序的序列v1,v2,vn，使得若从顶点vi到vj有一条有向路径,则在序列中顶点vi必须排在顶点vj之前。拓扑排序在AOV网中找一个拓扑序列的过程。6.5.1 拓扑排序90例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9

42、, C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6拓扑序列并不唯一91BDAC对于有向图不能求得它的拓扑有序序列。因为图中存在一个有向回路 B, C, D6.5.1 拓扑排序92拓扑排序的算法思想：输入一个AOV网。令 n 为顶点个数。(1) 在AOV网中选一个没有前驱的顶点, 并输出之.(2) 从图中删去该顶点, 同时删去与该顶点关联的弧.(3) 重复以上 (1)、(2) 步, 直到全部顶点均已输出，拓扑序列形成，拓扑排序完成;或图中还有未输出的顶点，这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时说明AOV网中一定存

43、在有向回路。93拓扑排序的过程94拓扑排序的过程95拓扑排序的过程96拓扑排序的过程最后得到的拓扑序列为 C4 ,C0,C3 ,C2 ,C1 ,C5 。97在算法中增设一个数组indegree ,记录各个顶点的 入度。(2) 算法思想中第2步提到的“删去顶点”和“删去弧”在算法实现中并不真正删除。而“删去顶点”只是作删除标记，“删去弧”是把与该弧相关联的弧头顶点的入度减1。拓扑排序算法实现98图的存储：邻接表(出边表)。建立邻接表：每输入一条弧，就需要建立一个弧结点，并将它链入第 i个链表中，并统计顶点k的入度。 EArcNode * p = new EArcNode(k);/建立弧结点, d

44、est 域为 k plink = ghead i. firstout ;ghead i. firstout = p; /链入顶点 i 的链表的前端indegreek+; /顶点 k 入度加1 99在拓扑排序算法中，为了减少判断入度为零的顶点，使用一个存放入度为零的顶点的链式栈，供选择和输出无前驱的顶点。只要出现入度为零的顶点，就将它加入栈中。使用顶点栈的拓扑排序算法可以描述如下： (1) 建立入度为零的顶点栈; int top = -1; /入度为零的顶点栈初始化 for ( int i = 0; i int top = -1; for ( int i = 0; i ik; /读入一条弧 wh

45、ile(i!=-1) EArcNode * p = new EArcNode(k); /建立弧结点, adjvex域为 k plink = ghead i. firstout ; ghead i. firstout = p; /链入顶点 i 的边链表的前端 indegreek+; /顶点 k 入度加1 cinik; 拓扑排序的算法为：104 top=-1; /建立初始顶点入度为0栈 for(i=0；i-1) i=top; top=indegreetop; coutlink) k=p-adjvex； if(!(-indegreek) indegreek=top；top=k; /for/while

46、if(countn) return false；return true；/TopologicalSort106 建立有向图的邻接表和入度数组indegree 107int top = -1; for ( int i = 0; i 事件弧活动权值活动的持续时间AOE网112AOE网在某些工程预算方面非常有用。 它可以使人们了解到： (1) 完成整个工程至少需要多少时间(假设 网中没有有向回路)? (2) 为缩短完成工程所需的时间, 应当加快 哪些活动? 从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活

47、动都完成了，整个工程才算完成。113(源点)(汇点)完成整个工程所需的时间取决于从源点到汇点的最长路径长度(最长路径可能不止一条)，即在这条路径上所有活动的持续时间之和。解决问题(1)(完成工程的最短时间)114路径长度最长的路径称为关键路径(Critical Path)。关键路径上的所有活动称为关键活动。关键路径为: (v0,v1,v4,v6,v8 )或(v0,v1,v4,v7,v8 )关键路径为长度为18关键活动为：a1, a4, a7, a9, a10, a8, a11115解决问题(2)(为缩短工程所需时间, 应当加快哪些活动)要找出关键路径，必须找出关键活动，只有提高关键活动的功效，

48、才可能缩短整个工期。116定义几个与计算关键活动有关的量：1. eei-事件Vi 的最早开始时间ee4=7ee5=7 从源点V0 到顶点Vi 的最长路径长度。1172. lei-事件Vi 的最迟开始时间 在保证汇点Vn-1 在不推迟整个工程完成的前提下，事件Vi 允许的最迟开始时间。le5=18-4-4 10ee5=7ee4=7le4=18-11 =7它等于een-1 减去从Vi到Vn-1的最长路径长度。118 3. ek-活动ak 的最早开始时间 设活动ak 在弧上，则ek是从源点V0到顶点Vi 的最长路径长度。 因此, ek = eei。 i j ake9=ee5=7e7=ee4=7119

49、4. lk-活动ak 的最迟开始时间 lk是在不推迟整个工程完成的前提下，该活动允许的最迟开始时间. lk = lej - dur()。其中，dut()是完成ak 所需的时间。 i j akl5=le4- a5 =7-1=6e5=ee2=4l4=le4-1 =7-1=6e4=ee1=6120 表示活动ak 的最迟开始时间和最早开始时间的时间余量。lk = ek表示活动ak 是没有时间余量的, 是关键活动。为找出关键活动, 需要求各个活动的 ek 与 lk，以判别是否 lk = ek.为求得ek与 lk，需要先求得从源点V0到各个顶点Vi 的 eei 和 lei。5. lk-ek-时间余量lk

50、= lej - dut()ek = eei i j ak121（1）求eei（2）求lei（3）求ek（4）求lk（5）计算lk-ek求关键活动的步骤122（1）如何求eei？其中P(j)表示以顶点j为弧头的所有弧的尾顶点集合。 eei是从源点V0 到顶点Vi 的最长路径长度。123（2）如何求lei？其中S(j)是以顶点j为弧尾的所有弧的弧头顶点集合。124（4）求li li = lev - dut()（3）求ei ei =eeuu vaiv（5）计算lk-ek eeu=lev - dut()？125876534210a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a

51、10=2a11=4V0V1V2V3V4V5V6V7V80645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动 ek lk l-e00002266046258377077071031616014140033顶点 eei leiek = eeilk = lej - dut()AOE网126（1）建立AOE网（存储结构为邻接表）。（2）从源点V0出发，令ee0=0，一边进行拓扑排序，一边计算其余各顶点的eei。若图中有回路则算法结束.（3）从汇点Vn-1出发, len-1=een-1,按逆拓扑有序的顺序求 lei, i=n-2, , 0。求AOE网中关

52、键活动的算法思想127（4）根据各顶点的ee和le值，求每条弧的最早开始时间ek和最迟开始时间 lk。 若某条弧满足条件 ek=lk，则该条弧是关键活动。128求关键活动算法如下：bool TopologicalSort(Stack &T) /求以邻接表存储的有向图中各顶点事件的最早发生时间ee。/S是入度为零顶点栈，T为拓扑序列顶点栈。若该有向图无回路，/则该算法返回true且栈T返回该有向图的一个拓扑序列，否则返回 /false。 Stack S; FindInGegree(indegree)； /求各顶点的入度indegree0.n-1且建立入度为零顶点栈S count=0; ee0.n

53、-1=0; /初始化 for (k=0; klink) /对顶点j的每个后继顶点入度减1 k=p-adjvex; if(-indegreek=0) S.Push(k); /若入度为0，则入栈S if(eej+ p-cost )eek) eek=eej+ p-cost ; /对j的每个后继顶点k修改eek if(countlink;) k=p-adjvex; if (lek-p-cost)cost; 131for(j=0;jlink) k=p-adjvex; tag=(eej=lek-p-cost )?*: ; coutjkcost)eejcost )tag; /CriticalPath132关

54、键路径算法分析:第一个for 语句O(n)；第二个for 语句O(n+e)；第三个for 语句O(n)；第四个for 语句O(n+e)；总共花费时间为O(n+e)。1336.6 最短路径 (Shortest Path)134 6.6.2 每一对顶点之间的最短路径 Floyd算法 6.6.1 求从某个源点到其余各点的最短路径 Dijkstra算法6.6 最短路径 (Shortest Path)135问题的提法： 给定一个网G = 与源点v0，求从v0到G中其它顶点的最短路径。 规定各边(或弧)上的权值大于或等于0。6.6.1 求单源最短路径Dijkstra算法Dijkstra算法的基本思想 按照

55、路径长度递增的次序产生各条最短路径。136 这条路径必定只含一条弧，并且这条弧的权值最小。第一条最短路径长度的求法:6.6.1 求单源最短路径Dijkstra算法137 它只可能有两种情况: 或者是直接从源点到某顶点v2(只含一条弧)； 或者是，从源点经过顶点v1，再到达该顶点v2(由两条弧组成)。第二条最短路径长度的求法:138 其余最短路径的求法： 它或者是直接从源点到某顶点vk(只含一条弧)或者是从源点经过已求得最短路径的顶点，再到达该顶点。139例： Min10,30,100=106.6.1 求单源最短路径Dijkstra算法602010305010003421101406020103

56、05010003421例：10 Min60,30,100=306.6.1 求单源最短路径Dijkstra算法14160201030501003421100 Min50,90=506.6.1 求单源最短路径Dijkstra算法14260201030501003421100 Min60=606.6.1 求单源最短路径Dijkstra算法143602010305010034211006.6.1 求单源最短路径Dijkstra算法0-1: 100-3: 300-3-2: 500-3-2-4: 60按照路径长度递增的次序产生各条最短路径。144引入一个辅助数组dist。它的每一个分量disti表示当前找

57、到的从源点v0到终点vi 的最短路径的长度。初始状态：若从源点v0到顶点vi有边或弧，则disti为该边或弧上的权值若从源点v0到顶点vi 没有边或弧，则disti为+ 。每次求得一条最短路径之后，其终点vk 加入集合U，然后对所有的vi V-U，修改其disti值。Dijkstra算法思想：145在算法中，还应引入两个辅助数组find和path。findi=1当且仅当已求得从v0到vi的最短路径。初始find0=1， find1.n-1=0；pathi用来记录从v0到vi的最短路径上vi的前驱顶点。若pathi=i-1， pathi-1=i-2， path1=0， 则逆序列v0 ，v1，v2

58、，vi 就是v0vi的最短路径上的顶点序列。 Dijkstra算法思想：146Dijkstra算法可描述如下：(1) 初始化： 设源点为v0，则find0=1; 其它find1.n-1=0; disti cost0i, i= 1, 2, , n-1; (2) 求出最短路径的长度： distk min disti , i V- U ; findk=1;(3) 修改： 对于每一个 i V- U; /即findi=0 disti min disti, distk + costki , 若U = V, 则算法结束，否则转(2)。存储：邻接矩阵147计算最短路径的图邻接矩阵类的定义const int n

59、 =20； /图中最大顶点个数Const int Max=9999; /9999表示无穷大class Graph /图的类定义 float costnn； float dist n； /最短路径长度数组 int pathn； /最短路径顶点序列数组 int findn； /最短路径顶点集public: void ShortestPath_DIJ (int，int，int)； int mininum ( int )；/ Graph148用Dijkstra描述的单源最短路径算法为：void ShortestPath_DIJ(int v0，int dist，int path) /求从源点为v0从到其它顶点的最短路经。for(v=0；vn；v+) findv=0； pathv=0； distv=costv0v； findv0=1；for(i=1；i n；i+)