数据结构第七章图

数据结构第七章图第一页，共六十五页，2022年，8月28日图的定义和术语图的存储结构图的遍历生成树

最短路径拓扑排序

习题第二页，共六十五页，2022年，8月28日图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间有线性关系，每一个数据元素只有一个直接前驱和一个直接后续；在树形结构中，数据元素之间有着明显的层次关系，即每一个数据元素有一个直接前驱(双亲)和零个或多个直接后续(孩子)；而在图形结构中，结点之间的关系是任意的，图中任意两个数据元素之间都可能相关。由此，图的应用极为广泛。例如，城市间的最短路径，火车的联票，交通网的计划，战场上的运输问题，庞大的施工进度图等都是图的应用。

第三页，共六十五页，2022年，8月28日图的定义和术语定义：图(graph)：是一种数据结构，由二个集合V和E组成，记作G=(V,E)。其中V是数据元素(顶点)的非空有限集，E是V中二元关系(边edge)的集合。树是图的特例，而线性表是树的特例。术语：

有向图：图的每条边都是有序顶点对(即边是有方向)。

弧：有向图的边。并将构成该边的有序顶点对用一对尖括号括起来。如<u,v>∈E，表示从顶点u到顶点v的一条弧，称u为弧尾或初始点，v为弧头或终端点。并且说v是与u相邻的顶点，或v是u的邻接点

第四页，共六十五页，2022年，8月28日例如，图7.1(a)所示的为有向图，它是由集合

V={v0,v1,v2,v3}E={<v0,v1>,<v0,v2>,<v2,v3>,<v3,v0>}

组成的。图7.1(a)有向图G1

无向图：图的每条边是无方向的，有<u,v>∈E，必有<v,u>∈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)}

组成的。第五页，共六十五页，2022年，8月28日网络：若图中每条边或弧都附加一个数值作为权,带权图。子图：若G1={V1,E1}，G2={V2,E2}是两个图，且V2被包含在V1中，E2被包含在E1中，则称图G2是图G1的子图。度：无向图中，顶点的度是依附于该顶点的边数。有向图中，该顶点入边的数目叫入度，该顶点出边的数目叫出度，该顶点的度就是入度+出度。图中的顶点度数之和等于边数的2倍。路径：在有向图(或无向图)中，如果存在首尾相接并且无重复边的边序列<v0,v1>,<v1,v2>,…,<vn-2,vn-1>(或(v0,v1),(v1,v2),…,(vn-2,vn-1))，那么称这个序列是一条从顶点到v0到vn-1的一条路径，记着(v0,v1,v2,…,vn-2,vn-1)。序列中的边数称为路径长度。在有向图中，路径是有方向的；而在无向图中，路径无方向。简单路径：在一条路径中，若除起点和终点外，所有顶点彼此各不相同。第六页，共六十五页，2022年，8月28日回路：在一条路径中，若起点和终点是同一顶点。简单回路：有简单路径组成的回路称为简单回路。连通：在无向图G中，若从顶点vi到顶点vj有路径存在。连通图：在无向图G中，若任意二个顶点之间都是连通的.连通分量：在非连通的无向图G中，极大连通子图(在满足连通条件下，尽可能多的包含G中的顶点和这些顶点之间的边).如图7.2中，图G有三个连通分量。(a)有向图G(b)图G的三个连通分量

第七页，共六十五页，2022年，8月28日强连通：在有向图G中，若从顶点vi到顶点vj有路径存在，并且从顶点vj到顶点vi也有路径存在。强连通图：在有向图G中，若任意二个顶点之间都是强连通的。

强连通分量：在非强连通的有向图G中，极大强连通子图称为有向图的强连通分量。如图7.3中，有向图G有两个强连通分量。生成树：在一个有n顶点的连通图G中，存在一个极小的连通子图G′，G′包含图G的所有顶点，但只有n-1条边，并且G′是连通的。(a)有向图G(b)图G的二个强连通分量

图7.3有向图及其强连通分量第八页，共六十五页，2022年，8月28日图的存储结构常用的图的存储结构有邻接矩阵、邻接表、十字链表、多重链表等方法。本节介绍最为常用的邻接矩阵和邻接表方法。对图的存储结构的选择取决于具体的应用。1、邻接矩阵(1)存储形式邻接矩阵是用一个二维数组来表示图中顶点间的相邻关系的数据结构。设图G=(V,E)，有n≥1个顶点，则所对应图G的邻接矩阵A是按如下定义的一个n×n的二维数组。第九页，共六十五页，2022年，8月28日若图G是一个网络，其邻接矩阵

借助于邻接矩阵很容易判定任意两个顶点之间是否有边(或弧)相连，并容易求得各个顶点的度，操作方便。

(2)邻接矩阵法的特点：1.存储空间：对于无向图而言，它的邻接矩阵是对称矩阵，所以可采用压缩存储法（下三角），其存储空间只需n(n+1)/2。但对于有向图而言，因为它的弧是有方向的，它的邻接矩阵不一定是对称矩阵，所以需要n2个存储空间。2.便于运算：采用邻接矩阵表示法，便于判定图中任意两个顶点之间是否有边相连，即根据A[i，j]=0或1来判断。另外还便于求得各个顶点的度。第十页，共六十五页，2022年，8月28日2、邻接表(1)存储形式对一个有n个顶点图的顶点进行编号，顶点的编号从1到n。图的邻接表存储结构与树的孩子表示法相同。将图G中每个顶点vi的所有邻接点用一个单链表(邻接点链表)表示，在vi的邻接点链表中存放vj(有(vi,vj)或<vi,vj>∈E)的编号，以及其它与该边或弧相关的信息。一个图有n个顶点就有n个邻接点链表(度为0的顶点，所对应的邻接点链表为空表)。这n个邻接点链表的头指针又构成一个线性表，用一个指针数组存储该线性表，这样就构成了图的邻接表的存储结构。例如，在图7.1中，G1和G2的的邻接表如图7.5所示，图中下标对应顶点vi的编号。

第十一页，共六十五页，2022年，8月28日(a)G1的邻接表(b)G2的邻接表图7.5邻接表存储结构第十二页，共六十五页，2022年，8月28日

逆邻接表：对于为网络的图G=(V,E)，在node结构中可以添加一个权值域。而对于有向图，图7.5(a)所示为按G1出度建立的邻接表，在该邻接表中求每个顶点vi的出度和以vi为尾的弧方便，但若要求顶点的入度，必须遍历整个邻接表。所以，有时为了使求顶点vi的入度和以vi为头的弧方便，可以建立该有向图的逆邻接表，即在vi的邻接点链表中存放vj(有<vj,vi>∈E)的编号。如图7.6所示为图7.1(a)中G1的逆邻接表。图7.6G1的逆邻接表第十三页，共六十五页，2022年，8月28日生成无向带权图的邻接表的算法：Constn:=图顶点数；e:=图中边数；Typeedge=^edgenode;edgenode=recordadj:1..n;weight:weighttypenext:edge;end;vexnode=recorddata:datatype;link:edge;end;dajlish=arrar[1..n]ofvexnode;Procedurecreate(varg:dajlish);Beginfori:=1tondobeginread(g[i].data);g[i].link:=nil;end;fork:=1toedobeginread(i,j,w);new(s);s^.adj:=j;s^.weight:=w;s^.next:=g[i].link;g[i].link:=s;End;End;

第十四页，共六十五页，2022年，8月28日思考并实现：1、分别在无向图和有向图的邻接表上统计各顶点的度（有向图为入度和出度）。2、统计图（有向图和无向图）的顶点度数和。第十五页，共六十五页，2022年，8月28日2、边集数组表示法v1v5v2v3v4254371边数123456起点112234终点253545权453217第十六页，共六十五页，2022年，8月28日7.3图的遍历与树的遍历相同，把按一定的规律沿着图中的边访问图的每个顶点，并且使每一个顶点只被访问一次的过程称为图的遍历。因为在图中任意两个顶点之间都可能有关系。为保证每一个顶点只被访问一次，必须对访问过的顶点进行标记，一般是用一个辅助数组visit[i]作为对顶点的标记。当顶点vi未被访问，visit[i]值为0；当顶点vi已被访问，则visit[i]值为1。图的遍历方法通常有先深度遍历和先广度遍历两种。但经常称这两种遍历为深度优先搜索DFS和广度优先搜索BFS。第十七页，共六十五页，2022年，8月28日7.3.1深度优先搜索DFS(DepthFirstSearch)图的深度优先搜索是树的先序遍历的推广，其定义(递归)如下：

(1)从图G=(V,E)中选任意某个未访问过的顶点vi作为搜索的出发点。(2)访问vi。(3)以vi的每一个未被访问过的邻接点w为出发点，深度优先搜索图G。(4)直至图G中所有与vi有路径相通的顶点都被访问过。(5)若图G中尚有顶点未曾访问过，则转到(1)；否则，搜索结束。其中实箭头代表访问方向，虚箭头代表回溯方向，箭头旁边的数字代表搜索顺序，A为起始顶点。8ADGBEHCFI1236710114155149131216访问序列为：A、B、C、F、E、G、D、H、I。第十八页，共六十五页，2022年，8月28日深度优先搜索算法：Proceduredfs(i:1..n);{图用邻接表存储，其他方式的存储只需稍作修改，g[i]为表头结点表}Beginwrite(g[i].v);{输出是最为简单的访问方式}visited[i]:=true;p:=g[i].link;whilep<>nildobeginj:=p^.adj;{j为i的一个后继}ifnotvisited[j]thendfs(j);{递归}p:=p^.next;{回溯}end;end/;第十九页，共六十五页，2022年，8月28日7.3.2广度优先搜索BFS(BreadthFirstSearch)

图的广度优先搜索与按层次遍历树相似，定义如下：(1)从图G=(V,E)中选任意某个未访问过的顶点vi作为搜索的出发点。(2)访问vi。(3)依次访问vi的各个未曾访问过的邻接点。分别从这些邻接点出发进行广度优先搜索，直至图中所有与vi有路径相通的顶点都被访问过。(4)若图中尚有顶点未曾访问过，则转到(1)；否则，搜索结束。ADGBEHCFI14657823访问序列为：A、B、E、D、C、G、F、H、I。第二十页，共六十五页，2022年，8月28日广度优先搜索算法：Procedurebfs(i:1..n);{图用邻接表g表示}Begincreate(q);{建队，置队空}write(g[i].v);{访问vi}visited[i]:=true;{标记已经访问的结点}push(q,i);{进队列}whilenotempty(q)do{广度优先遍历，直到队列空为止，表示所有节点都被访问过了}begini:=pop(q);{取顶点，对首元素出队}p:=g[i].link;{取边表指针}whilep<>nildo{还有后继顶点}beginifnotvisited[p^.adj]thenbeginwrite(g[p^.adj].v);{访问当前顶点}visited[p^.adj]:=true;push(q,p^,adj);{当前顶点入队}end;p:=p^.next;{从边表中取下一个邻接边}end;end;End;第二十一页，共六十五页，2022年，8月28日生成树1、概念生成树是一个连通图G的一个极小的连通子图。包含图G的所有顶点，但只有n-1条边，并且是连通的。在生成树中，不存在回路路径，但若在生成树中任意增加一条边，则必构成回路。一个连通图的生成树不是惟一的，例如，对一个连通图进行深度优先，在搜索过程中经过的边和图的顶点，构成深度优先生成树；若进行广度优先搜索，则构成广度优先生成树。非连通图有若干个连通分量组成，每一个连通分量都存在生成树，这样就构成生成森林。第二十二页，共六十五页，2022年，8月28日2、最小生成树(最小支撑树)若有一个连通的无向图G，它有n个顶点，并且它的边是有权值的。在图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)是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一棵包含边(u,v)的最小生成树。第二十三页，共六十五页，2022年，8月28日(1)普里姆(Prim)算法该算法是利用MST性质，描述如下：

假设G=(V,E)是带权的连通无向图，从u0∈V开始构造G上最小生成树G’=(U,TE)，初始U={u0}，TE=φ。重复以下步骤：在所有的u∈U(生成树中的顶点)，v∈V-U(尚不在生成树中的顶点)，且(u,v)∈E中找一条权值最小的边(u0,v0)并入TE，同时v0并入U，直至U=V时结束。此时，TE中包含n-1条边，并使n个顶点连通，且权值之和最小。如图7.8所示，其为在一个带权的连通无向图G中，构造最小生成树的过程。

为实现这个算法需要引入辅助数组closest[]和lowcost[]记录从U到V-U的权值最小的边。closest[i]=j(i∈V-U,j∈U)，表示顶点i到j的一条边(j,i)，同时(j,i)是U到V-U中的顶点i权值最小的边。(j,i)的权值存放在lowcost[i]中。

第二十四页，共六十五页，2022年，8月28日图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，则closest[1]=2。同样，可求出closest[3]=5，closest[4]=2。它们所对应的lowcost数组分别是：lowcost[1]=(2,1)=5，lowcost[3]=(5,3)=2，lowcost[4]=(2,4)=6。第二十五页，共六十五页，2022年，8月28日图7.9所示为图7.8构造最小生成树过程中，辅助数组closest[]和lowcost[]的变化情况，在这里，对于顶点j∈U，其lowcost[j]=0。顶点编号：0、1、2、3……

若图G=(V,E)采用邻接矩阵表示，邻接矩阵所对应的二维数组是cost[MAX，MAX]。则普里姆算法如下：(1)初始化(U={0}),closest[i]=0;lowcost[i]=cost[0,i];lowcost[0]=0；(i=0,2,…,n-1)。(2)每次扫描数组lowcost[]，找出值最小且不为0的lowcost[k]，得到最小生成树的一条边(closest[k],k)，将其输出；(3)令lowcost[k]=0，将k并入U中；(4)修改数组closest[i]和lowcost[i]（lowcost[i]<>0及i∈V-U）；(5)重复(2)、(3)、(4)，直到U=V（或循环n-1次）结束。第二十六页，共六十五页，2022年，8月28日下标i012345UV-U1closest[i]000000{0}{1,2,3,4,5}Lowcost[i]0615∞∞2closest[i]020022{0,2}{1,3,4,5}lowcost[i]0505643closest[i]020522{0,2,5}{1,3,4,}lowcost[i]0502604closest[i]020522{0,2,3,5}{1,4}lowcost[i]0500605closest[i]020512{0,1,2,3,5}{4}lowcost[i]0000306closest[i]020512{0,1,2,3,4,5}фlowcost[i]000000图7.9图7.8构造最小生成树过程中辅助数组的值

第二十七页，共六十五页，2022年，8月28日Prim算法求最小生成树：procedureprim(v0:integer);

var

lowcost,closest:array[1..maxn]ofinteger;

i,j,k,min:integer;

begin

fori:=1tondobegin{给lowcost[]和closest[]赋初值，此时U={v0}}

lowcost[i]:=cost[v0,i];{lowcost[i]存放的是顶点I到v0的权值}

closest[i]:=v0;{closest[i]存放的是v0}

end;

fori:=1ton-1dobegin{寻找离生成树最近的未加入顶点k}

min:=maxlongint;

forj:=1tondo

if(lowcost[j]<min)and(lowcost[j]<>0)thenbegin

min:=lowcost[j];k:=j;end;

lowcost[k]:=0;{将顶点k加入生成树}forj:=1tondo{修正各点的lowcost和closest值}

ifcost[k,j]<lwocost[j]thenbegin

lowcost[j]:=cost[k,j];

closest[j]:=k;

end;

end;

end;{prim}

第二十八页，共六十五页，2022年，8月28日(2)克鲁斯卡尔(Kruskal)算法该算法是按边权值递增次序,构造最小生成树的算法。算法描述如下：设带权的连通无向图G=(V,E)，有n个顶点。最小生成树的初始状态为有n个顶点但无边的非连通图T=(V,φ)，图中每个顶点自成一个连通分量。(1)将E中的边按权值的递增顺序排序，选择权值最小的边，若与该边相关的顶点落在T中不同连通分量上，则将其加入到T中；否则，将其舍弃。(2)循环至所有顶点在同一连通分量上。如何识别一条边所相关的顶点是否落在一个连通分量上？在此采用集合的方法，即将在一个连通分量上的所有顶点看成一个集合。当从E中取得一条边(xi,xj)后，若xi和xj在同一个集合u中，则将该边舍弃；否则，则将该边加入到T中，并将xj所在的集合v并入集合u。为此引入辅助数组sets[]。第二十九页，共六十五页，2022年，8月28日图7.10克鲁斯卡尔算法构造最小生成树的过程克鲁斯卡尔(Kruskal)算法第三十页，共六十五页，2022年，8月28日①初始化：图G中的n个顶点，构成n个连通分量。顶点xi对应的连通分量用集合i表示，所以sets[i]=i，即表示第i个顶点在集合i中。②依次取出的E中的边(按边权值递增顺序)，设取出的边(xi,xj)。

③判断：若sets[i]=sets[j]，则表示xi和xj在同一个集合中，返回②；否则，xi和xj在不同集合中，则表示xi和xj落在不同连通分量上，转到④。④将边(xi,xj)并入T，同时将xj所在集合v(与xj连通的顶点)并入xi所在集合u(与xi连通的顶点)，即：由v=sets[j]和u=sets[i]，扫描辅助数组sets[]，若sets[k]=v，则将sets[k]=u。返回②。⑤重复②、③、④，取出n-1条边。例如，图7.10所示为依照克鲁斯卡尔算法构造一棵最小生成树的过程。sets[]是辅助数组状态。克鲁斯卡尔(Kruskal)算法第三十一页，共六十五页，2022年，8月28日克鲁斯卡尔(Kruskal)算法1、请用标记数组方法和解决该问题！2、请用有根树的方法解决该问题！3、比较两种处理方法的优劣。第三十二页，共六十五页，2022年，8月28日最短路径采用图结构来表示实际交通图，图中顶点代表城市，边表示城市之间的交通联系，边上的权为城市之间的距离，可能有这样一种问题存在。例如，A城到B城是否有通路；A城到B城的哪条通路代价最低(距离最短)。上述的问题就是最短路径问题。这里讨论的图是带权有向图，并称路径的起始点为源点，路径的最后端点为终点。下面讨论两种最常见的最短路径问题，并给出最短路径问题的算法。第三十三页，共六十五页，2022年，8月28日1、求某源点到其余各顶点的最短路径

定义：给定带权值的有向图G=(V,E)，E中每条弧<u,v>有非负的权。指定V中的一个顶点v作为源点，求从v出发到G中其余各顶点的最短路径，被称为单源最短路径问题。

算法：采用迪杰斯特拉(Dijkstra)算法，解决单源最短路径问题。即按路径长度递增的次序产生最短路径。图G采用邻接矩阵cost[]存储。把G=(V,E)的顶点集合V划分成U和V-U，U为从v出发，已确定最短路径终点集合，初始状态为{v}，V-U为尚未确定最短路径顶点集合.定义一个辅助数组dist[j]：保存从源点v到vj的目前最短路径长度，初值为（v,vj）,若v到vj没有边，则权值为无穷大。以后每加入一个新的中间点vk时，要判断dist[j]与dist[k]+cost[k,j]的大小，若后者更小，则dist[j]:=dist[k]+cost[k,j].再定义一个数组s,s[j]=1表示节点vj已经加入集合U,s[j]=0表示节点vj为待加入集合U的节点。初始时，除了源点s[v]=1,其它节点vi对应的s[i]=0;再定义一个数组path[i],用来表示从源点v到节点vi所经过的最短路径上的顶点序列或者边序列。

第三十四页，共六十五页，2022年，8月28日算法描述如下：

(1)从S集合以外的顶点（待求出最短路径的终点）所对应的dist数组元素中，查找出值最小的元素dist[k],该元素值就是从源点v到vk的最短路径长度。Path[k]就是最短路径上的顶点序列。(2)将s[k]修改为1（即并入已经确定了最短路径的顶点集合）。(3)以vk作为新考虑的中间点，对S[j]=0的所有vj点，比较dist[j]与dist[k]+cost[k,j]的大小，若后者大于前者，则将dist[j]:=dist[k]+dist[k,j],path[j]:=path[m]+j重复以上运算n-2次（第一个节点和最和一个节点除外），即可在dist[i]数组中得到源点v到vi的最短路径，在path数组中得到相应的最短路径。第三十五页，共六十五页，2022年，8月28日v1v2v3v4V5s10001Dist01049207Pathv1V1,v2V1,v3V1,v5,v4V1,v52154317107133428495v1v2v3v4V5s11111Dist01027207Pathv1V1,v2V1,v2,v3V1,v5,v4V1,v5v1v2v3v4V5s10000Dist01049∞7Pathv1V1,v2V1,v3V1,v5v1v2v3v4V5s11001Dist01027207Pathv1V1,v2V1,v2,v3V1,v5,v4V1,v5v1v2v3v4V5s11011Dist01027207Pathv1V1,v2V1,v2,v3V1,v5,v4V1,v5第三十六页，共六十五页，2022年，8月28日Dijkstra算法：Proceduredijkstra(cost,dist,path,i);{求源点vi到其余顶点的最短路径，cost为图的邻接矩阵，dist和path为变量型参数，其中path基类型为集合}Beginforj:=1tonbeginifj<>ithens[j]:=1;dist[j]:=cost[i,j];ifdist[j]<maxintthenpath[j]:=[i]+[j]elsepath[j]:=[];end;fork:=1ton-2dobeginw:=maxint;m:=i;forj:=1tondoif(s[j]=0)and(dist[j]<w)thenm:=j;w:=dist[j];end;ifm<>Ithens[m]:=1elseexit;{剩余重点的dist均为maxint时，无需计算下去}forj:=1tondo{对s[j]=0的元素的dist做必要修改}if(s[j]=0)and(dist[m]+cost[m,j])thenbegindist[j]:=dist[m]+cost[m,j];path[j]:=path[m]+[j];end;end;End;第三十七页，共六十五页，2022年，8月28日2、每对顶点之间的最短路径对带有权值的有向图G=(V,E)中任意一对顶点(u,v)，求u到v的最短路径，被称为每对顶点之间的最短路径问题。对该问题的解决有两种方法：其一，每次以一个顶点为源点，重复执行Dijkstra算法。这样，便可求得每对顶点之间的最短路径。总时间复杂度为o(n3)。其二，采用弗洛伊德(Floyd)算法，这里主要讨论该算法。对有向图G，采用带权邻接矩阵cost[]存储。同时定义一个二维数组A[N，N]，其每一个分量A[i，j]的值是顶点i到顶点j的最短路径。弗洛伊德算法的基本思想是：(1)初始时，对图中任意两个顶点vi和vj，如果从vi到vj存在弧，则从vi到vj存在一条长度为cost[i，j]的路径，但该路径不一定是最短路径，还需要进行n次试探，即考虑从vi出发途经vk(k=1,2,…,n)到达vj是否距离更短。初始化A[i，j]=cost[i，j]（没有考虑途经其它顶点）。第三十八页，共六十五页，2022年，8月28日

(2)对图中任意两个顶点vi和vj之间的路径，考虑途经vk的路径(vi,vk,vj)是否存在。若存在，则比较途经vk是否距离更短，即：比较A[i，k]+A[k，j]和A[i，j](前者为途经vk的距离，而后者为没有考虑途经vk的距离)，较小者送A[i，j]。(3)重复(2)，从vi出发，考虑途经vk(k=1,2,3,…,n-1)到达vj的距离是否更短。n次比较之后，辅助数组中的每一个分量A[i，j]中存放的值，是从vi出发，已考虑了途经图G中所有顶点，到达vj的最短路径。算法时间复杂度O(n^3)第三十九页，共六十五页，2022年，8月28日Floyed(cost,A,p);Beginfori:=1tondoforj:=1tondobegina[I,j]:=cost[I,j];ifa[I,j]<maxintthenp[I,j]:=[i]+[j]elsep[I,j]:=[];end;fork:=1tondo{枚举所有的中间点}fori:=1tondoforj:=1tondobeginif(i=k)or(j=k)or(i=j)thencontinue;ifa[I,k]+a[k,j]<a[I,j]thenbegina[I,j]:=a[I,k]+a[k,j];p[I,j]:=p[I,j]+p[k,j];end;end;End;具体实例请见书上184页例题。第四十页，共六十五页，2022年，8月28日拓扑排序一个无回环的有向图称为有向无环图，简称为DAG图，DAG图在计算机系统，以及工程、管理、经济领域中有着重要的作用。检查一个有向图是否存在回环，可以采用拓扑排序方法进行。7.6.1顶点活动网(AOV网)实际应用中，常用有向图来描述工程的进度、系统实施过程。工程可以分为若干个称为活动(activity)的子工程，而且这些子工程之间通常有一定的先后关系。以顶点为活动，以有向边表示先后关系的有向图，被称为AOV网。在AOV网中，若从顶点vi到顶点vj有一条有向路径，则vi是vj的前驱；vj是vi的后续。若<vi,vj>是网中一条弧，则vi是vj的直接前驱；vj是vi的直接后续。第四十一页，共六十五页，2022年，8月28日在AOV网中，不应该有回环出现，因为存在回环意味着某项活动以自身的完成为先决条件。显然，这是不合理的。所以，对给定的AOV网，必须检测网中是否存在回环。回环检测的方法是：对有向图构造其顶点拓扑有序序列，若网中所有顶点都在它的拓扑序列中，则AOV必定不存在回环。第四十二页，共六十五页，2022年，8月28日课程编号课程名称先决条件C1程序设计无C2离散数学C1C3数据结构C1,C2C4汇编语言C1C5算法分析C3,C4C6计算机体系结构C11C7编译方法C5,C3C8操作系统C3,C6C9高等数学C10线性代数C9C11普通物理C9C12数值分析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-C8第四十三页，共六十五页，2022年，8月28日拓扑排序对一个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的(直接)前驱。得到该序列的过程称为拓扑排序。拓扑排序的方法如下：(1)在AOV网中选择一个没有直接前驱的顶点，并将其输出。(2)从AOV网中删除该顶点和所有以它为尾的弧。(3)重复(1)和(2)，直至所有顶点都被输出，或者当前AOV网中不存在没有前驱（存在有前驱）的顶点为止。前一种情况表示AOV网中无回环存在，而后一种情况则说明AOV网中存在回环。第四十四页，共六十五页，2022年，8月28日图7.13AOV网及其拓扑有序序列产生的过程按上述方法对图7.13(a)中所示的AOV网进行拓扑排序，得到的拓扑序列为：v5-v0-v3-v2-v1-v4为了在计算机中实现上述操作，AOV网采用邻接表作为存储结构。另外，在邻接表的头结点中增加一个存放顶点入度的数据域，入度为0的顶点即为没有前驱的顶点。当删除一条边后，与该边相关联的弧头顶点的入度减1。第四十五页，共六十五页，2022年，8月28日图7.14图7.13(a)的AOV网所对应的邻接表图7.13(a)的AOV网所对应的邻接表如图7.14所示。用一个栈存放AOV网中入度为0的顶点。具体算法描述如下：(1)将邻接表中所有入度为0的顶点编号进栈（可用入度域）。(2)栈为空，转到(3)。栈不为空，首先，栈顶元素vi出栈并输出；然后，在邻接表中查找以顶点vi为尾的弧<vi,vk>，将顶点vk的入度减1，若顶点vk的入度为0，则顶点vk进栈。重复(2)。(3)判断输出的顶点数，若不等于n，则AOV网中有回环存在。第四十六页，共六十五页，2022年，8月28日拓扑排序算法的具体描述为：Proceduretopsort(GL);{Gl为图的邻接表}Begintop:=0;fori:=1tondoifGL[i].indegree=0then[g[i].indegree:=top;top:=i];m:=0;{用m记录输出顶点的个数。}whiletop<>0dobegin(1)j:=top;(2)top:=gl[top].indegree;{退栈}(3)write(gl[j].data);{输出顶点j的值}(4)m:=m+1;(5)p:=gl[j].link;(6)whilep<>nildobegin(a)k:=p^.adjvex;(b)dec(gl[k].indegree);(c)ifgl[k].indegree=0then[gl[k].indegree:=top;top:=k];(d)p:=p^.next;end;ifm<nthen(‘thenetworkhasacycle’)End;时间复杂度分析：n个顶点和e条边的AOV网而言，建立邻接表的时间为O(e)；搜索入度为0顶点时间为O(n)；在拓扑排序中，若无回环存在，则每个顶点进一次栈，出一次栈，入度减1的操作也总共执行e次，所以，总的时间复杂度为O(n+e)。第四十七页，共六十五页，2022年，8月28日例题：士兵排序190页请完成该题第四十八页，共六十五页，2022年，8月28日关键路径对整个工程和系统，人们关心的是两个方面的问题：1）工程能否顺利进行对AOV网进行拓扑排序2）估算整个工程完成所必须的最短时间对AOE网求关键路径第四十九页，共六十五页，2022年，8月28日AOE-网AOE－网(ActivityOnEdgeNetwork)：即边表示活动的网。AOE网是一个带权的有向无环图。其中：顶点表示事件（Event）弧表示活动（Activity）权值表示活动持续的时间通常可用AOE网来估算工程的完成时间。第五十页，共六十五页，2022年，8月28日上图AOE-网中：共有11项活动：a1,a2,a3,…a11；共有9个事件：v1,v2,v3,…v9，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。v9表示整个工程的结束v5表示a4和a5已经完成，a7和a8可以开始与每个活动相联系的数是执行该活动所需的时间v1表示整个工程的开始第五十一页，共六十五页，2022年，8月28日由于整个工程只有一个开始点和一个完成点，在正常的情况（无环）下，网中只有一个入度为零的点（称作源点）和一个出度为零的点（称作汇点）汇点源点第五十二页，共六十五页，2022年，8月28日依据AOE-网可以研究什么问题？（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？第五十三页，共六十五页，2022年，8月28日完成工程的最短时间是从源点到汇点的最长路径的长度。路径长度最长的路径叫做关键路径。从v1到v9的最长路径是（v1,v2,v5,v8,v9），路径长度是18。第五十四页，共六十五页，2022年，8月28日假设开始点是v1，从v1到vi的最长路径长度叫做事件vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。用e(i)表示活动ai的最早开始时间。V9的最早发生时间是18事件vi的最早发生时间第五十五页，共六十五页，2022年，8月28日l(i)－e(i)两者之差意味着完成活动ai的时间余量。我们把l(i)＝e(i)的活动叫做关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。a6的最早开始时间是5，最迟开始时间是8。如a6推迟3天开始或延迟3天完成，都不会影响整个工程的完成。活动的最迟开始时间l(i)，这是在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间。第五十六页，共六十五页，2022年，8月28日由此可知：辨别关键活动就是找e(i)＝l(i)的活动。为求得AOE网中活动的e(i)和l(i)，首先应求得事件的最早发生时间ve(j)和最迟发生时间vl(j)。若活动ai由弧<i,j>表示，持续时间记为dut(<i,j>)，则有如下关系：

活动i的最早开始时间等于事件j的最早发生时间e(i)＝ve(i)活动i的最迟开始时间等于事件k的最迟时间减去活动i的持续时间l(i)＝vl(j)-dut(<i，j>)求ve(j)和vl(j)需分两步进行：aiViVj第五十七页，共六十五页，2022年，8月28日ve[j]和vl[j]可以采用下面的递推公式计算：（1）向汇点递推ve(源点)=0；ve(j)=Max{ve(i)+dut(<i,j>)}公式意义：从指向顶点Vj的弧的活动中取最晚完成的一个活动的完成时间作为Vj的最早发生时间ve[j]pVjVi第五十八页，共六十五页，2022年，8月28日（2）向源点递推由上一步的递推，最后总可求出汇点的最早发生时间ve[n]。因汇点就是结束点，最迟发生时间与最早发生时间相同，即vl[n]