数据结构第七章图课件.ppt

1、图的定义和术语图的存储结构图的遍历生成树 最短路径拓扑排序 习题 图是一种较线性表和树更为复杂的数据结构。图是一种较线性表和树更为复杂的数据结构。在在线性表线性表中，数据元素之间有中，数据元素之间有线性关系线性关系，每一个数，每一个数据元素只有一个直接前驱和一个直接后续；在据元素只有一个直接前驱和一个直接后续；在树树形形结构中，数据元素之间有着明显的结构中，数据元素之间有着明显的层次关系层次关系，即每，即每一个数据元素有一个直接前驱一个数据元素有一个直接前驱(双亲双亲)和零个或多个和零个或多个直接后续直接后续(孩子孩子)；而在；而在图图形结构中，结点之间的关形结构中，结点之间的关系是系是任意的

2、任意的，图中任意两个数据元素之间都可能相，图中任意两个数据元素之间都可能相关。由此，图的应用极为广泛。例如，城市间的最关。由此，图的应用极为广泛。例如，城市间的最短路径，火车的联票，交通网的计划，战场上的运短路径，火车的联票，交通网的计划，战场上的运输问题，庞大的施工进度图等都是图的应用。输问题，庞大的施工进度图等都是图的应用。 图的定义和术语定义：定义： 图图(graph)：是一种数据结构，由二个集合是一种数据结构，由二个集合V和和E组成，组成，记作记作G=(V,E)。其中。其中V是数据元素是数据元素(顶点顶点)的非空有限集，的非空有限集，E是是V中二元关系中二元关系(边边edge)的集合。

3、树是图的特例，而线性表是的集合。树是图的特例，而线性表是树的特例。树的特例。术语：术语： 有向图：有向图：图的每条边都是有序顶点对图的每条边都是有序顶点对(即边是有方向即边是有方向)。 弧：弧：有向图的边。并将构成该边的有序顶点对用一对有向图的边。并将构成该边的有序顶点对用一对尖括号括起来。如尖括号括起来。如E，表示从，表示从顶点顶点u到到顶点顶点v的一条的一条弧弧，称，称u为为弧尾弧尾或或初始点初始点，v为为弧头弧头或或终端点终端点。并且说。并且说v是与是与u相邻的顶点相邻的顶点，或，或v是是u的的邻接点邻接点 例如，图例如，图7.1(a)所示的为有向图，它是由集合所示的为有向图，它是由集合

4、 V=v0,v1,v2,v3 E=,组成的。组成的。图图7.1 (a)有向图有向图G1 无向图：无向图：图的每条边是无方向的，有图的每条边是无方向的，有E，必有，必有E。即用圆括号括起来即用圆括号括起来 (u,v)E表示边，并且，表示边，并且，u和和v互称为邻接点互称为邻接点 例如，图例如，图7.1(b) 为无向图，它是由集合为无向图，它是由集合 V= v0,v1,v2,v3,v4 E=(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3) ,(v2,v4)组成的。组成的。网络：网络：若图中每条边或弧都附加一个数值作为权若图中每条边或弧都附加一个数值作为权,带权图。带权

5、图。子图：子图：若若G1=V1,E1，G2=V2,E2是两个图，且是两个图，且V2被包含被包含在在V1中，中，E2被包含在被包含在E1中，则称图中，则称图G2是图是图G1的子图。的子图。度：度：无向图中，顶点的度是依附于该顶点的边数。无向图中，顶点的度是依附于该顶点的边数。有向图有向图中，中，该顶点入边的数目叫入度，该顶点出边的数目叫出度，该顶该顶点入边的数目叫入度，该顶点出边的数目叫出度，该顶点的度就是入度点的度就是入度+出度。出度。图中的顶点度数之和等于边数的图中的顶点度数之和等于边数的2倍。倍。路径：路径：在有向图在有向图(或无向图或无向图)中，如果存在首尾相接并且无重中，如果存在首尾相

6、接并且无重复边的边序列复边的边序列, (或或 (v0,v1),(v1,v2),(vn-2,vn-1)，那么称这个序列是一条从顶点到，那么称这个序列是一条从顶点到v0到到vn-1的一条路径，记着的一条路径，记着(v0,v1,v2,vn-2,vn-1)。序列中的。序列中的边数边数称为称为路径长度路径长度。在有向图中，路径是有方向的；而在无。在有向图中，路径是有方向的；而在无向图中，路径无方向。向图中，路径无方向。简单路径：简单路径：在一条路径中，若除起点和终点外，所有顶点彼在一条路径中，若除起点和终点外，所有顶点彼此各不相同。此各不相同。回路：回路：在一条路径中，若起点和终点是同一顶点。在一条路径

7、中，若起点和终点是同一顶点。简单回路：简单回路：有简单路径组成的回路称为简单回路。有简单路径组成的回路称为简单回路。连通：连通：在无向图在无向图G中，若从顶点中，若从顶点vi到顶点到顶点vj有路径存在。有路径存在。连通图：连通图：在无向图在无向图G中，若任意二个顶点之间都是连通的中，若任意二个顶点之间都是连通的.连通分量：连通分量：在非连通的无向图在非连通的无向图G中，极大连通子图中，极大连通子图(在满足在满足连通条件下，尽可能多的包含连通条件下，尽可能多的包含G中的顶点和这些顶点之间中的顶点和这些顶点之间的边的边) . 如图如图7.2中，图中，图G有三个连通分量。有三个连通分量。 (a)(a

8、)有向图有向图G (b)G (b)图图G G的三个连通分量的三个连通分量强连通：强连通：在有向图在有向图G中，若从顶点中，若从顶点vi到顶点到顶点vj有路径存在，有路径存在，并且从顶点并且从顶点vj到顶点到顶点vi也有路径存在。也有路径存在。强连通图：强连通图：在有向图在有向图G中，若任意二个顶点之间都是强连通中，若任意二个顶点之间都是强连通的。的。 强连通分量：在非强连通的有向图强连通分量：在非强连通的有向图G中，极大强连通中，极大强连通子图称为有向图的强连通分量。如图子图称为有向图的强连通分量。如图7.3中，有向图中，有向图G有两有两个强连通分量。个强连通分量。生成树：生成树：在一个有在一

9、个有n顶点的连通图顶点的连通图G中，存在一个极小的连中，存在一个极小的连通子图通子图G，G包含图包含图G的所有顶点，但只有的所有顶点，但只有n-1条边，并且条边，并且G是连通的。是连通的。(a)有向图G (b)图G的二个强连通分量 图7.3 有向图及其强连通分量 图的存储结构 常用的图的存储结构有邻接矩阵、邻接表、十字链表、常用的图的存储结构有邻接矩阵、邻接表、十字链表、多重链表等方法。本节介绍最为常用的邻接矩阵和邻接表多重链表等方法。本节介绍最为常用的邻接矩阵和邻接表方法。对图的存储结构的选择取决于具体的应用。方法。对图的存储结构的选择取决于具体的应用。1、 邻接矩阵邻接矩阵(1)存储形式存

10、储形式 邻接矩阵是用一个邻接矩阵是用一个二维数组二维数组来表示图中顶点间的相邻来表示图中顶点间的相邻关系的数据结构。关系的数据结构。 设图设图G=(V,E)，有，有n1个顶点，则所对应图个顶点，则所对应图G的邻接矩的邻接矩阵阵A是按如下定义的一个是按如下定义的一个nn的二维数组。的二维数组。否否则则0 0E E) )v v, ,v v( (对对有有向向图图为为j ji iE,vvjiji)( 1A若若若图若图G是一个网络，其邻接矩阵是一个网络，其邻接矩阵 i ij jj ji ij ji ii ij j) )的的权权值值为为w wv v, ,且且( (v vE E, ,) )v v, ,若若(

11、 (v v w wAji借助于邻接矩阵很容易判定任意两个顶点之间是否有边借助于邻接矩阵很容易判定任意两个顶点之间是否有边(或或弧弧)相连，并容易求得各个顶点的度，操作方便。相连，并容易求得各个顶点的度，操作方便。 (2)邻接矩阵法的特点：邻接矩阵法的特点：1. 存储空间：对于无向图而言，它的邻接矩阵是对称矩阵，存储空间：对于无向图而言，它的邻接矩阵是对称矩阵，所以可采用压缩存储法（下三角），其存储空间只需所以可采用压缩存储法（下三角），其存储空间只需n(n+1)/2。但对于有向图而言，因为它的弧是有方向的，它的邻接矩阵不但对于有向图而言，因为它的弧是有方向的，它的邻接矩阵不一定是对称矩阵，所以

12、需要一定是对称矩阵，所以需要n2个存储空间。个存储空间。2. 便于运算：采用邻接矩阵表示法，便于判定图中任意两个便于运算：采用邻接矩阵表示法，便于判定图中任意两个顶点之间是否有边相连，即根据顶点之间是否有边相连，即根据Ai，j=0或或1来判断。另外还来判断。另外还便于求得各个顶点的度。便于求得各个顶点的度。 2、 邻接表邻接表(1)存储形式存储形式 对一个有对一个有n个顶点图的顶点进行编号，顶点的编号从个顶点图的顶点进行编号，顶点的编号从1到到n。图的。图的邻接表邻接表存储结构与存储结构与树的孩子表示法相同树的孩子表示法相同。将图。将图G中每个顶点中每个顶点vi的所有的所有邻接点邻接点用用一个

13、单链表一个单链表(邻接点链表邻接点链表)表示，表示，在在vi的邻接点链表中存放的邻接点链表中存放vj(有有(vi,vj)或或E)的编号，的编号，以及其它与该边或弧相关的信息。一个图有以及其它与该边或弧相关的信息。一个图有n个顶点个顶点就有就有n个个邻接点链表邻接点链表(度为度为0的顶点，所对应的邻接点链表为空表的顶点，所对应的邻接点链表为空表)。这。这n个邻接点个邻接点链表的头指针又构成一个线性表链表的头指针又构成一个线性表，用一个指针数，用一个指针数组存储该线性表，这样就构成了图的邻接表的存储结构。例组存储该线性表，这样就构成了图的邻接表的存储结构。例如，在图如，在图7.1中，中，G1和和G

14、2的的邻接表如图的的邻接表如图7.5所示，图中下标所示，图中下标对应顶点对应顶点vi的编号。的编号。 (a)G1的邻接表 (b)G2的邻接表 图7.5 邻接表存储结构 逆邻接表：逆邻接表：对于为网络的图对于为网络的图G=(V,E)，在，在node结构中可以添结构中可以添加一个权值域。而对于有向图，图加一个权值域。而对于有向图，图7.5(a)所示为按所示为按G1出度建立出度建立的邻接表，在该邻接表中求每个顶点的邻接表，在该邻接表中求每个顶点vi的出度和以的出度和以vi为尾的弧为尾的弧方便，但若要求顶点的入度，必须遍历整个邻接表。所以，方便，但若要求顶点的入度，必须遍历整个邻接表。所以，有时为了使

15、求顶点有时为了使求顶点vi的入度和以的入度和以vi为头的弧方便，可以建立该为头的弧方便，可以建立该有向图的逆邻接表，即在有向图的逆邻接表，即在vi的邻接点链表中存放的邻接点链表中存放vj(有有E)的编号。如图的编号。如图7.6所示为图所示为图7.1(a)中中G1的逆邻接表。的逆邻接表。图7.6 G1的逆邻接表 生成无向带权图的邻接表的算法：生成无向带权图的邻接表的算法：Const n:=图顶点数； e:=图中边数；Type edge=edgenode; edgenode=record adj:1.n; weight:weighttype next:edge; end; vexnode=reco

16、rd data:datatype; link:edge; end; dajlish=arrar1.nof vexnode;Procedure create(var g:dajlish );Begin for i:=1 to n do begin read(gi.data); gi.link:=nil; end; for k:=1 to e do begin read(i,j,w); new(s); s.adj:=j; s.weight:=w; s.next:=gi.link; gi.link:=s; End;End; 思考并实现：1、分别在无向图和有向图的邻接表上统计各顶点的度（有向图为入度和

17、出度）。2、统计图（有向图和无向图）的顶点度数和。2、 边集数组表示法边集数组表示法v1v5v2v3v4254371边数123456起点112234终点253545权4532177.3 图的遍历 与树的遍历相同，把按一定的规律沿着图中的边访问图的每个顶点，并且使每一个顶点只被访问一次的过程称为图的遍历。 因为在图中任意两个顶点之间都可能有关系。为保证每一个顶点只被访问一次，必须对访问过的顶点进行标记，一般是用一个辅助数组visiti作为对顶点的标记。当顶点vi未被访问，visiti值为0；当顶点vi已被访问，则visiti值为1。 图的遍历方法通常有先深度遍历和先广度遍历两种。但经常称这两种遍

18、历为深度优先搜索DFS和广度优先搜索BFS。7.3.1 深度优先搜索深度优先搜索DFS(Depth First Search) 图的深度优先搜索是树的先序遍历的推广，其定义(递归)如下： (1)从图G=(V,E)中选任意某个未访问过的顶点vi作为搜索的出发点。 (2)访问vi。 (3)以vi的每一个未被访问过的邻接点w为出发点，深度优先搜索图G。 (4)直至图G中所有与vi有路径相通的顶点都被访问过。 (5)若图G中尚有顶点未曾访问过，则转到(1)；否则，搜索结束。 其中实箭头代表访问方向，虚箭头代表回溯方向，箭头旁边的数其中实箭头代表访问方向，虚箭头代表回溯方向，箭头旁边的数字代表搜索顺序，

19、字代表搜索顺序，A为起始顶点。为起始顶点。8ADGBEHCFI1236710114155149131216访问序列为：访问序列为：A、B、C、F、E、G、D、H、I。深度优先搜索算法：Procedure dfs(i:1.n);图用邻接表存储，其他方式的存储只需稍作修改，gi为表头结点表Begin write(gi.v);输出是最为简单的访问方式 visitedi:=true; p:=gi.link; while pnil do begin j:=p.adj;j为i的一个后继 if not visitedj then dfs(j);递归 p:=p.next; 回溯 end;end/; 7.3.2

20、 广度优先搜索广度优先搜索BFS(Breadth First Search) 图的广度优先搜索与按层次遍历树相似，定义如下： (1)从图G=(V,E)中选任意某个未访问过的顶点vi作为搜索的出发点。 (2)访问vi。 (3)依次访问vi的各个未曾访问过的邻接点。分别从这些邻接点出发进行广度优先搜索，直至图中所有与vi有路径相通的顶点都被访问过。 (4)若图中尚有顶点未曾访问过，则转到(1)；否则，搜索结束。 ADGBEHCFI14657823访问序列为：访问序列为：A、B、E、D、C、G、F、H、I。广度优先搜索算法：Procedure bfs(i:1.n);图用邻接表g表示Begin cre

21、ate(q); 建队，置队空 write(gi.v); 访问vi visitedi:=true; 标记已经访问的结点 push(q,i); 进队列 while not empty(q) do 广度优先遍历，直到队列空为止，表示所有节点都被访问过了 begin i:=pop(q); 取顶点，对首元素出队 p:=gi.link; 取边表指针 while pnil do 还有后继顶点 begin if not visitedp.adj then begin write(gp.adj.v); 访问当前顶点 visitedp.adj:=true; push(q,p,adj); 当前顶点入队 end; p

22、:=p.next; 从边表中取下一个邻接边 end; end;End;生成树 1、概念 生成树是一个连通图G的一个极小的连通子图。包含图G的所有顶点，但只有n-1条边，并且是连通的。在生成树中，不存在回路路径，但若在生成树中任意增加一条边，则必构成回路。一个连通图的生成树不是惟一的，例如，对一个连通图进行深度优先，在搜索过程中经过的边和图的顶点，构成深度优先生成树；若进行广度优先搜索，则构成广度优先生成树。非连通图有若干个连通分量组成，每一个连通分量都存在生成树，这样就构成生成森林。2、 最小生成树最小生成树(最小支撑树最小支撑树) 若有一个连通的无向图G，它有n个顶点，并且它的边是有权值的。

23、在图G上构造生成树G(n个顶点，n-1条边，G是连通的)，因为生成树的非惟一性，则有多个G存在，而最小生成树是n-1条边的权值之和最小的G。最小生成树也是非惟一的，但图G所有最小生成树的n-1条边的权值之和相同，并且为最小值。 例如，用带权的连通无向图G表示n个城市之间的交通网，最小生成树问题是：如何确定n-1条线路连通这n个城市，并且代价最小。 在带权的连通无向图G=(V,E)上，构造最小生成树有普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法，它们都是利用最小生成树中简称为MST的性质：U是顶点集V的一个非空子集，若(u,v)是一条具有最小权值的边，其中uU，vV-U，则必存在一棵

24、包含边(u,v)的最小生成树。(1)普里姆普里姆(Prim)算法算法 该算法是利用MST性质，描述如下： 假设G=(V,E)是带权的连通无向图，从u0V开始构造G上最小生成树G=(U,TE)，初始U=u0，TE=。重复以下步骤：在所有的uU(生成树中的顶点)，vV-U(尚不在生成树中的顶点)，且(u,v)E中找一条权值最小的边(u0,v0)并入TE，同时v0并入U，直至U=V时结束。此时，TE中包含n-1条边，并使n个顶点连通，且权值之和最小。如图7.8所示，其为在一个带权的连通无向图G中，构造最小生成树的过程。 为实现这个算法需要引入辅助数组辅助数组closest和lowcost记录从U到V

25、-U的权值最小的边。closesti=j(iV-U ,jU) ，表示顶点i到j的一条边(j,i)，同时(j,i)是U到V-U中的顶点i权值最小的边。(j,i)的权值存放在lowcosti中。图7.8 普里姆算法构造最小生成树过程 在图7.8(c)中，U=0,2,5，V-U=1,3,4，对于U-V中的顶点1到U中的顶点的边有：(0,1)=6，(2,1)=5，(5,1)=，所以，U到顶点1权值最小的边是(2,1)=5，则 closest1=2。同样，可求出closest3=5，closest4=2。它们所对应的lowcost数组分别是：lowcost1=(2,1)=5，lowcost3= (5,3

26、)=2，lowcost4=(2,4)=6。 图7.9所示为图7.8构造最小生成树过程中，辅助数组closest和lowcost的变化情况，在这里，对于顶点jU，其lowcostj=0。顶点编号：0、1、2、3 若图G=(V,E)采用邻接矩阵表示，邻接矩阵所对应的二维数组是costMAX，MAX。则普里姆算法如下： (1)初始化(U=0),closesti=0;lowcosti=cost0,i;lowcost0=0；(i=0,2,n-1)。 (2)每次扫描数组lowcost，找出值最小且不为0的lowcostk，得到最小生成树的一条边(closestk,k)，将其输出； (3)令lowcostk

27、=0，将k并入U中； (4)修改数组closesti和lowcosti（lowcosti0及iV-U）； (5)重复(2)、(3)、(4)，直到U=V（或循环n-1次）结束。 下标下标i 0 1 2 3 4 5 U V-U 1closesti 0 0 0 0 0 0 01,2,3,4,5Lowcosti 0 6 1 52closesti 0 2 0 0 2 2 0,2 1,3,4,5lowcosti 0 5 0 5 6 43 closesti 0 2 0 5 2 2 0,2,5 1,3,4,lowcosti 0 5 0 2 6 04closesti 0 2 0 5 2 2 0,2,3,5 1,

28、4lowcosti 0 5 0 0 6 05closesti 0 2 0 5 1 20,1,2,3,5 4lowcosti 0 0 0 0 3 06closesti 0 2 0 5 1 20,1,2,3,4,5 lowcosti 0 0 0 0 0 0 图图7.9 图图7.8构造最小生成树过程中辅助数组的值构造最小生成树过程中辅助数组的值 Prim算法求最小生成树：procedure prim(v0:integer); var lowcost,closest:array1.maxn of integer; i,j,k,min:integer; begin for i:=1 to n do be

29、gin 给lowcost和closest赋初值，此时U=v0 lowcosti:=costv0,i; lowcosti存放的是顶点I到v0的权值 closesti:=v0; closesti存放的是v0 end; for i:=1 to n-1 do begin 寻找离生成树最近的未加入顶点k min:=maxlongint; for j:=1 to n do if (lowcostj min) and (lowcostj0) then begin min:=lowcostj; k:=j; end; lowcostk:=0; 将顶点k加入生成树 for j:=1 to n do 修正各点的lo

30、wcost和closest值 if costk,j lwocostj then begin lowcostj:=costk,j; closestj:=k; end; end; end;prim (2)克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法 该算法是按边权值递增次序,构造最小生成树的算法。算法描述如下： 设带权的连通无向图G=(V,E)，有n个顶点。最小生成树的初始状态为有n个顶点但无边的非连通图T=(V,)，图中每个顶点自成一个连通分量。 (1)将E中的边按权值的递增顺序排序，选择权值最小的边，若与该边相关的顶点落在T中不同连通分量上，则将其加入到T中；否则，将其舍弃。 (2)循环至所

31、有顶点在同一连通分量上。如何识别一条边所相关的顶点是否落在一个连通分量上？在此采用集合的方法，即将在一个连通分量上的所有顶点看成一个集合。当从E中取得一条边(xi,xj)后，若xi和xj在同一个集合u中，则将该边舍弃；否则，则将该边加入到T中，并将xj所在的集合v并入集合u。为此引入辅助数组sets。图7.10 克鲁斯卡尔算法构造最小生成树的过程 克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法 初始化：图G中的n个顶点，构成n个连通分量。顶点xi对应的连通分量用集合i表示，所以setsi=i，即表示第i个顶点在集合i中。 依次取出的E中的边(按边权值递增顺序)，设取出的边(xi,xj)。 判断

32、：若setsi=setsj，则表示xi和xj在同一个集合中，返回；否则，xi和xj在不同集合中，则表示xi和xj落在不同连通分量上，转到。 将边(xi,xj)并入T，同时将xj所在集合v(与xj连通的顶点)并入xi所在集合u(与xi连通的顶点)，即：由v=setsj和u=setsi，扫描辅助数组sets，若setsk=v，则将setsk=u。返回。 重复、，取出n-1条边。 例如，图7.10所示为依照克鲁斯卡尔算法构造一棵最小生成树的过程。sets是辅助数组状态。克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法1、请用标记数组方法和解决该问题！2、请

33、用有根树的方法解决该问题！3、比较两种处理方法的优劣。最短路径 采用图结构来表示实际交通图，图中顶点代表城市，边表示城市之间的交通联系，边上的权为城市之间的距离，可能有这样一种问题存在。例如，A城到B城是否有通路；A城到B城的哪条通路代价最低(距离最短)。上述的问题就是最短路径问题。 这里讨论的图是带权有向图，并称路径的起始点为源点，路径的最后端点为终点。下面讨论两种最常见的最短路径问题，并给出最短路径问题的算法。1、求某源点到其余各顶点的最短路径、求某源点到其余各顶点的最短路径 定义：给定带权值的有向图G=(V,E)，E中每条弧有非负的权。指定V中的一个顶点v作为源点，求从v出发到G中其余各

34、顶点的最短路径，被称为单源最短路径问题。 算法：采用迪杰斯特拉(Dijkstra)算法，解决单源最短路径问题。即按路径长度递增的次序产生最短路径。 图G采用邻接矩阵cost存储。把G=(V,E)的顶点集合V划分成U和V-U，U为从v出发，已确定最短路径终点集合，初始状态为v，V-U为尚未确定最短路径顶点集合.定义一个辅助数组distj：保存从源点v到vj的目前最短路径长度，初值为（v,vj）,若v到vj没有边，则权值为无穷大。以后每加入一个新的中间点vk时， 要判断distj与distk+costk,j的大小，若后者更小，则distj:=distk+costk,j. 再定义一个数组s,sj=1

35、表示节点vj已经加入集合U,sj=0 表示节点vj为待加入集合U的节点。初始时，除了源点sv=1,其它节点vi对应的si=0; 再定义一个数组pathi,用来表示从源点v到节点vi所经过的最短路径上的顶点序列或者边序列。 算法描述如下： (1)从S集合以外的顶点（待求出最短路径的终点）所对应的dist数组元素中，查找出值最小的元素distk,该元素值就是从源点v到vk的最短路径长度。Pathk就是最短路径上的顶点序列。 (2)将sk修改为1（即并入已经确定了最短路径的顶点集合）。 (3)以vk作为新考虑的中间点，对Sj=0的所有vj点，比较distj与distk+costk,j的大小，若后者大

36、于前者，则将distj:=distk+distk,j,pathj:=pathm+j重复以上运算n-2次（第一个节点和最和一个节点除外），即可在disti数组中得到源点v到vi的最短路径，在path数组中得到相应的最短路径。v1v2v3v4V5s10001Dist01049207Pathv1V1,v2V1,v3V1,v5,v4V1,v52154317107133428495v1v2v3v4V5s11111Dist01027207Pathv1V1,v2V1,v2,v3V1,v5,v4V1,v5v1v2v3v4V5s10000Dist010497Pathv1V1,v2V1,v3V1,v5v1v2v3

37、v4V5s11001Dist01027207Pathv1V1,v2V1,v2,v3V1,v5,v4V1,v5v1v2v3v4V5s11011Dist01027207Pathv1V1,v2V1,v2,v3V1,v5,v4V1,v5Dijkstra算法：Procedure dijkstra(cost,dist,path,i);求源点vi到其余顶点的最短路径，cost为图的邻接矩阵，dist和path为变量型参数，其中path基类型为集合Begin for j:=1 to n begin if ji then sj:=1;distj:=costi,j; if distjmaxint then pat

38、hj:=i+j else pathj:=; end; for k:=1 to n-2 do begin w:=maxint; m:=i; for j:=1 to n do if (sj=0)and(distjw) then m:=j; w:=distj;end; if mI then sm:=1 else exit;剩余重点的dist均为maxint时，无需计算下去 for j:=1 to n do 对sj=0的元素的dist做必要修改 if (sj=0)and(distm+costm,j)then begin distj:=distm+costm,j; pathj:=pathm+j; end

39、; end;End;2、 每对顶点之间的最短路径每对顶点之间的最短路径 对带有权值的有向图G=(V,E)中任意一对顶点(u,v)，求u到v的最短路径，被称为每对顶点之间的最短路径问题。对该问题的解决有两种方法：其一，每次以一个顶点为源点，重复执行Dijkstra算法。这样，便可求得每对顶点之间的最短路径。总时间复杂度为o(n3)。其二，采用弗洛伊德(Floyd)算法，这里主要讨论该算法。 对有向图G，采用带权邻接矩阵cost存储。同时定义一个二维数组AN，N，其每一个分量Ai，j的值是顶点i到顶点j的最短路径。弗洛伊德算法的基本思想是： (1)初始时，对图中任意两个顶点vi和vj，如果从vi到

40、vj存在弧，则从vi到vj存在一条长度为costi，j的路径，但该路径不一定是最短路径，还需要进行n次试探，即考虑从vi出发途经vk(k=1,2,n)到达vj是否距离更短。 初始化Ai，j=costi，j（没有考虑途经其它顶点）。 (2)对图中任意两个顶点vi和vj之间的路径，考虑途经vk的路径(vi,vk,vj)是否存在。若存在，则比较途经vk是否距离更短，即：比较Ai，k+Ak，j和Ai，j (前者为途经vk的距离，而后者为没有考虑途经vk的距离)，较小者送Ai，j。 (3)重复(2)，从vi出发，考虑途经vk(k=1,2,3,n-1)到达vj的距离是否更短。 n次比较之后，辅助数组中的每

41、一个分量Ai，j中存放的值，是从vi出发，已考虑了途经图G中所有顶点，到达vj的最短路径。算法时间复杂度O(n3)Floyed(cost,A,p);Begin for i:=1 to n do for j:=1 to n do begin aI,j:=costI,j; if aI,jmaxint then pI,j:=i+j else pI,j:=; end; for k:=1 to n do 枚举所有的中间点 for i:=1 to n do for j:=1 to n do begin if (i=k)or(j=k)or (i=j) then continue; if aI,k+ak,ja

42、I,j then begin aI,j:=aI,k+ak,j; pI,j:=pI,j+pk,j; end; end;End; 具体实例请见书上184页例题。拓扑排序 一个无回环的有向图称为有向无环图有向无环图，简称为DAG图，DAG图在计算机系统，以及工程、管理、经济领域中有着重要的作用。检查一个有向图是否存在回环，可以采用拓扑排序方法进行。7.6.1 顶点活动网顶点活动网(AOV网) 实际应用中，常用有向图来描述工程的进度、系统实施过程。工程可以分为若干个称为活动(activity)的子工程，而且这些子工程之间通常有一定的先后关系。以顶点为活动，以有向边表示先后关系的有向图，被称为AOV网。

43、在AOV网中，若从顶点vi到顶点vj有一条有向路径，则vi是vj的前驱；vj是vi的后续。若是网中一条弧，则vi是vj的直接前驱；vj是vi的直接后续。 在AOV网中，不应该有回环出现，因为存在回环意味着某项活动以自身的完成为先决条件。显然，这是不合理的。所以，对给定的AOV网，必须检测网中是否存在回环。回环检测的方法是：对有向图构造其顶点拓扑有序序列，若网中所有顶点都在它的拓扑序列中，则AOV必定不存在回环。 课程编号 课程名称 先决条件 C1 程序设计程序设计 无无 C2 离散数学离散数学 C1 C3 数据结构数据结构 C1 ,C2 C4 汇编语言汇编语言 C1 C5 算法分析算法分析 C

44、3 ,C4 C6 计算机体系结构计算机体系结构 C11 C7 编译方法编译方法 C5 ,C3 C8 操作系统操作系统 C3 ,C6 C9 高等数学高等数学 C10 线性代数线性代数 C9 C11 普通物理普通物理 C9 C12 数值分析数值分析 C9 ,C10 ,C1图7.12 课程之间的优先关系以及表示该关系的AOV网 例如，一个计算机软件专业的学生必须学习一系列基本课程(如图7.12(a)所示) ，构成的AOV网中有如下两个拓扑序列： C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 和 C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C

45、8 拓扑排序拓扑排序对一个AOV网进行拓扑排序过程，就是在一个只有部分顶点之间有先后关系的AOV网中，构造一个任意顶点之间都有先后关系的线性序列。即：对任意vi和vj，若它们属于该线性序列，则vi和vj之间必有先后关系，可能是vi是vj的(直接)前驱，也可能vj是vi的(直接)前驱。例如，图7.12(b)中，C5和C3,C4,C7之间有先后关系，而得到的拓扑序列： C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8表示C5和任意顶点之间的都有先后关系，C1,C2,C3,C4是C5的(直接)前驱，而C5是C7,C9,C10,C11,C6,C12,C8的(直接)前驱。得到

46、该序列的过程称为拓扑排序。拓扑排序的方法如下： (1)在AOV网中选择一个没有直接前驱的顶点，并将其输出。 (2)从AOV网中删除该顶点和所有以它为尾的弧。 (3)重复(1)和(2)，直至所有顶点都被输出，或者当前AOV网中不存在没有前驱（存在有前驱）的顶点为止。前一种情况表示AOV网中无回环存在，而后一种情况则说明AOV网中存在回环。图7.13 AOV网及其拓扑有序序列产生的过程 按上述方法对图7.13(a)中所示的AOV网进行拓扑排序，得到的拓扑序列为： v5-v0-v3-v2-v1-v4 为了在计算机中实现上述操作，AOV网采用邻接表作为存储结构。另外，在邻接表的头结点中增加一个存放顶点

47、入度的数据域，入度为0的顶点即为没有前驱的顶点。当删除一条边后，与该边相关联的弧头顶点的入度减1。 图7.14 图7.13(a)的AOV网所对应的邻接表 图7.13(a)的AOV网所对应的邻接表如图7.14所示。用一个栈存放AOV网中入度为0的顶点。具体算法描述如下： (1)将邻接表中所有入度为0的顶点编号进栈（可用入度域）。 (2)栈为空，转到(3)。栈不为空，首先，栈顶元素vi出栈并输出；然后，在邻接表中查找以顶点vi为尾的弧，将顶点vk的入度减1，若顶点vk的入度为0，则顶点vk进栈。重复(2)。 (3)判断输出的顶点数，若不等于n，则AOV网中有回环存在。 拓扑排序算法的具体描述为：P

48、rocedure topsort(GL);Gl为图的邻接表Begin top:=0; for i:=1 to n do if GLi.indegree=0 then gi.indegree:=top;top:=i; m:=0;用m记录输出顶点的个数。 while top 0 do begin (1) j:=top; (2)top:=gltop.indegree;退栈 (3) write(glj.data);输出顶点j的值 (4)m:=m+1; (5)p:=glj.link; (6)while pnil do begin (a)k:=p.adjvex; (b)dec(glk.indegree);

49、 (c)if glk.indegree=0 then glk.indegree:=top;top:=k; (d) p:=p.next; end; if mn then (the network has a cycle)End; 时间复杂度分析：n个顶点和e条边的AOV网而言，建立邻接表的时间为O(e)；搜索入度为0顶点时间为O(n)；在拓扑排序中，若无回环存在，则每个顶点进一次栈，出一次栈，入度减1的操作也总共执行e次，所以，总的时间复杂度为O(n+e)。 例题：士兵排序190页请完成该题关键路径关键路径 对整个工程和系统，人们关心的是两个方面对整个工程和系统，人们关心的是两个方面的问题：的问

50、题： 1 1）工程能否顺利进行）工程能否顺利进行 对对AOVAOV网进行拓扑排序网进行拓扑排序 2 2）估算整个工程完成所必须的最短时间）估算整个工程完成所必须的最短时间 对对AOEAOE网求关键路径网求关键路径AOE-AOE-网网nAOEAOE网网(Activity On Edge Network)(Activity On Edge Network)：即：即边表示活动的网。边表示活动的网。AOEAOE网是一个带权的有向网是一个带权的有向无环图。其中：无环图。其中：n顶点表示事件（顶点表示事件（EventEvent）n弧表示活动（弧表示活动（ActivityActivity）n权值表示活动持续