课件数据结构教学图

7.1图的基本概念和术语7.2图的存储结构7.3图的遍历和求图的连通分量7.4图的生成树7.5最短路径7.6有向无环图及应用7.7图的第7章图返回主目录7.1图的基本概念和术语第7章图返回主目录第7章图7.1图的基本概念和术语

7.1.1图的基本概念图G由集合V和E组成,记为G=(V,E),图中的结点又称为顶点,其中V是顶点的非空有穷集合,相关的顶点的偶对称为边,E是边的有穷集合。

若图中的边是顶点的有序对,则称此图为有向图。有向边又称为弧,通常用尖括弧表示一条有向边,〈vi,vj〉表示从顶点vi到vj的一段弧,vi称为边的始点(或尾顶点),vj称为边的终点(或头顶点),〈vi,vj〉和〈vj,vi〉代表两条不同的弧。第7章图7.1图的基本概念和术语

若图中的边是顶点的无序对,则称此图为无向图。通常用圆括号表示无向边,(vi,vj)表示顶点vi和vj间相连的边。在无向图中(vi,vj)和(vi,vj)表示同一条边,如果顶点vi

、vj之间有边(vi,vj),则vi

、vj互称为邻接点。图7.1给出两个图G1和G2,其中G1是无向图,G2是有向图。在有向图中用箭头表示弧的方向,箭头从始点指向终点。图G1是一个无向图的例子。在图G1中,V={v1,v2,v3,v4},E={(v1,v2),(v2,v3),(v1,v3),(v1,v4),(v3,v4)}。而(v2,v1)与（v1,v2

）表示同一条边,(v2,v3)与(v3,v2)也表示同一条边,等。若图中的边是顶点的无序对,则称此图为无向课件-数据结构教学第7章图-

图G2是一个有向图的例子,在图G2中V={v1,v2,v3,},E={〈v1,v2

〉,〈v1,v3

〉,〈v2,v3,〉,〈v3,v2

〉}。而〈v3,v2

〉与〈v2,v3,〉表示两条不同的边。对于图G=(V,E),G′=(V′,E′),若有V′∈V,E′∈E,则称图G′是G的一个子图。图7.2给出了G3与其子图G3′。在下面的讨论中不考虑顶点到自身的边,也不允许一条边(或弧)在图中重复出现。因此有n个顶点的无向图最大边数为C2n=n(n-1)/2,这样的图称为无向完全图；有向图中最多可能有A2n=n(n-1)条弧,这样的图称为有向完全图。图G2是一个有向图的例子,在图G2中V课件-数据结构教学第7章图-

7.1.2路径和回路所谓顶点vp

到顶点vq之间的路径,是指顶点序列vp,vi1

,vi2

,…,vim,vq,其中（vp,vi1）,（vi1

,vi2）,…,（vim,vq

）分别为图中的边。路径上边的数目称为路径长度。图7.3所示的无向图中,顶点v1(注：v1在图中用数字1表示，其余类同)到顶点v5的路径有两条,分别为v1,v2,v3,v4与v1,v5,v4,路径长度分别为3和2。如果路径的起点和终点相同(即vp=vq),则称此路径为回路或环。序列中顶点不重复出现的路径称为简单路径,图7.3所示的v1到v5的两条路径都为简单路径。除第一顶点与最后一个顶点之外,其它顶点不重复出现的回路为简单回路或者简单环。7.1.2路径和回路课件-数据结构教学第7章图-

7.1.3连通图若从顶点vi到顶点vj(i≠j)有路径,则vi和vj是连通的。如果无向图中任意两个顶点vi和vj都是连通的,则称无向图是连通的。无向图中极大连通子图称为连通分量。图7.2中的G3有两个连通分量,见图7.4(a)。对于有向图来说,图中任意一对顶点vi和vj(i≠j)均有从vi到vj及从vj到vi的有向路径,则称该有向图是强连通的。有向图中的极大强连通子图称为该有向图的强连通分量。图7.1中G2不是强连通的,但它有一个强连通分量,见图7.4(b)。7.1.3连通图课件-数据结构教学第7章图-

7.1.4顶点的度顶点的度是指依附于某顶点vi的边数,通常记为TD(vi)。在有向图中,要区别顶点的入度和出度的概念。所谓顶点vi的入度是指以vi为终点的弧的数目,记为ID(vi);所谓顶点vi的出度是指以vi为始点的弧的数目,记为OD(vi)。显然

TD(vi)=ID(vi)+OD(vi)例如,在G1中顶点v1的度TD(v1)=3,在G2中顶点v2的入度ID(v2)=2,出度OD(v2)=1,TD(v2)=3。可以证明,对于具有n个顶点、e条边的图,顶点vi的度TD(vi)与顶点的个数及边的数目满足关系:7.1.4顶点的度7.2图的存储结构

7.2.1邻接矩阵图的邻接矩阵表示法是用一个二维数组来表示图中顶点之间的相邻关系。设图G=(V,E)有n(n≥1)个顶点,则G的邻接矩阵是按如下定义的n阶方阵:

aij=1若(vi,vj)或<vi,vj>∈E(G)

0反之例如,图7.1中的G1、G2的邻接矩阵分别表示为A1和A2,矩阵的行、列号对应于图中结点的号。7.2图的存储结构7.2.1邻接矩阵

从图的邻接矩阵表示法中很容易看出图的一些特性,这种表示方法具有以下特点:

(1)无向图的邻接矩阵一定是对称的,而有向图的邻接矩阵不一定对称。因此,用邻接矩阵来表示一个具有n个顶点的有向图时需要n2个单元来存储邻接矩阵;对有n个顶点的无向图则只需存入上(下)三角形,故只需n(n+1)/2个单元。0111101011011010A2=011001010从图的邻接矩阵表示法中很容易看出图的一些特性,7.2.2邻接链表图的邻接链表存储结构是一种顺序分配和链式分配相结合的存储结构。它包括两个部分,一部分是链表,另一部分是向量。在链表部分中共有n个链表(n为顶点数),即每个顶点对应一个链表。每个链表由一个表头结点和若干个表结点组成。表头结点用来指示第i个顶点vi所对应的链表;表结点由顶点域(vex)和链域(link)所组成。顶点域指示了与vi相邻接的顶点的序号,所以一个表结点实际上代表了一条依附于vi的边,链域指示了依附于vi的下一条边的结点。因此,第i个链表就表示了依附于顶点vi的所有的边。对于有向图来说,第i个链表就表示了从vi发出的所有的弧。7.2.2邻接链表

邻接链表的另一部分是一个向量,用来存储n个结点。向量的下标指示了顶点的序号,这样就可以随机地访问任一个顶点的链表。例如,对于图7.1中的G1和G2,其邻接链表如图7.5所示。defineMaxSize20[WB]

typedefstructArcNode{

intadjvex;/*该弧所指向的顶点的位置*/

structArcNode*nextarc;/*指向下一条弧的指针*/

InfoTypeinfo/*该弧相关信息的指针*/

}ArcNode;邻接链表的另一部分是一个向量,用来存储n个结课件-数据结构教学第7章图-typedefstructVnode{

VertexTypedata;/*顶点信息*/

ArcNode*firstarc;/*指向第一条依附该顶点的弧的指针*/

}Vnode,AdjList［MaxSize］;

typedefstruct{

AdjListvertices;

intvexnum,arcnum;

}ALGraph;[HT5SS]typedefstructVnode{

若无向图有n个顶点,e条边,则邻接链表需n个表头结点和2e个表结点,每个表结点有两个域。显然,对于边很少的图,用邻接链表比用邻接矩阵要节省存储单元。在无向图的邻接链表中,第i个链表中的表结点数就是顶点vi的度数。在有向图的邻接链表中,第i个链表中的表结点数就是顶点vi的出度。若要求vi的入度,必须对邻接链表进行扫描,统计点域的值为i的表结点的数目,显然,这是很费时间的。为了便于确定有向图中顶点的入度,可以另外再建立一个逆邻接链表,使第i个链表表示以vi为头的所有的弧。图7.6即为图G2的逆邻接表。若无向图有n个顶点,e条边,则邻接链表需课件-数据结构教学第7章图-7.3图的遍历和求图的连通分量

7.3.1图的建立由上节知道,可采用邻接矩阵或邻接链表作为图的存储结构。下面给出无向图的邻接矩阵的形式说明及其建立算法7.1。算法7.1

typedefcharvextype;/*顶点的数据类型*/

typedefstruct

{vextypevexs［n+1］;

intarcs［n+1］［n+1］;〖ZK)〗

}graph;7.3图的遍历和求图的连通分量7.3.1voidcreatgraph(graph*ga)/*建立无向图*/

{inti,j,k;

for(i=1;i<n;i++)ga->vexs［i］=getchar();/*读入顶点信息*/

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)ga->arcs［i］［j］=0;/*邻接矩阵初始化*/

for(k=1;k<=e;k++)/*读入e条边*/

{scanf("%d%d",&i,&j);ga->arcs［i］［j］=1;

ga->arcs［j］［i］=1;

}}/*creatgraph*/voidcreatgraph(graph*ga)

7.3.2图的遍历从图中某一顶点出发访遍其余顶点,且使每一顶点仅被访问一次,这一过程称为图的遍历。遍历图的基本方法有两种:深度优先搜索和广度优先搜索。这两种方法都适用于有向图和无向图。因为图的任一顶点都可能和其余顶点相邻接,因此在遍历过程中,可能会多次访问某个顶点。为了避免这种情况,要记下每个已访问过的顶点,一般可增设一个辅助数组visited［n］,每个visited［i］的初值置为零。一旦顶点vi被访问,就将visited［i］置为1。

1.连通图的深度优先搜索遍历7.3.2图的遍历

连通图的深度优先搜索遍历类似于树的先根遍历,其基本思想如下:假定图中某个顶点v1为出发点,首先访问出发点然后选择一个v1的未访问的邻接点v2,以v2为新的出发点继续进行深度优先搜索,直至图中所有顶点都被访问过。显然,图的深度优先搜索是一个递归过程。现以图7.7(a)为例说明深度优先搜索过程。假定v1是出发点,首先访问v1

。因v1有两个邻接点v2

、v3均未被访问过,可以选择v2作为新的出发点,访问v2之后,再找v2的未访问过的邻接点。同v2邻接的有v1

、v4、v5,其中v1已被访问过,而v4

、v5尚未被访问过,可以选择v4作为新的出发点。连通图的深度优先搜索遍历类似于树的先根遍历,课件-数据结构教学第7章图-

重复上述搜索过程,继续依次访问v8、v5

。访问v5之后,由于与v5相邻的顶点均已被访问过,搜索退回到v8

。由于v8

、v4

、v2都是已被访问的邻接点,所以搜索过程连续地从vv8退回到v4,再退回到v2,最后退回到v1

。这时选择v1的未被访问过的邻接点v3,继续往下搜索,依次访问v3

、v6、v7,从而遍历了图中全部顶点。在这个过程中得到的顶点的访问序列为

v1→v2→v4→v8→v5→v3→v6→v7

因为深度优先搜索遍历是递归定义的,故容易写出其递归算法。下面以邻接矩阵作为图的存储结构给出具体算法。重复上述搜索过程,继续依次访问v8、v5算法7.2

intvisited［MaxSize］,n;/*访问标志数组*/voiddfstraverse(GraphG,intv)

{/*对图G作深度优先遍历*/

for(v=0;v<G.vexnum;++v)visited［v］=0;/*访问标志数组初始化*/

for(v=0;v<G.vexnum;++v)

if(![KG-*2]visited［v］)dfs(G,v);/*对尚未访问的顶点调用dfs*/

}/*dfstraverse*/算法7.2voiddfs(GraphG,intv)

{/*从第v个顶点出发递归地深度优先遍历图G*/

visited［v］=1;printf("%d",v);/*访问第v个顶点*/

for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))

f(!visited［w］)dfs(G,w);/*对v的尚未访问的邻接顶点w递归调用dfs*/

}/*dfs*/voiddfs(GraphG,intv)

由上述可知,遍历图的过程实质上是对每个顶点搜索其邻接点的过程。故用邻接矩阵表示图时,搜索一个顶点的所有邻接点需花费O(n)时间,则从n个顶点出发搜索的时间应为O(n2),即dfs算法的时间复杂度是(n2);如果使用邻接链表来表示图时,其dfs算法的时间复杂度为O(n+e),此处e为无向图中边的数目或有向图中弧的数目。

2.连通图的广度优先搜索遍历连通图广度优先搜索遍历类似于树的按层次遍历,其基本思想是:从图中某个顶点vi出发,在访问了vi之后依次访问vi所有邻接点;然后分别从这些邻接点出发按广度优先搜索遍历图的其它顶点,直至所有顶点都被访问过。由上述可知,遍历图的过程实质上是对每个顶点

下面以图7.7(a)中G图为例说明广度优先搜索的过程。首先从起点v1出发访问v1。v1有两个未曾访问的邻接点v2和v3,先访问v2,再访问v3;然后再先访问v2的未曾访问过的邻接点v4

、v5及v3的未曾访问过的邻接点v6和v7,最后访问v4的未曾访问过的邻接点v8

。至此图中所有顶点均已被访问过。得到的顶点访问序列为:

v1→v2→v3→v4→v5→v6→v7→v8

在广度优先搜索中,若对x的访问先于y,则对x邻接点的访问也先于对y邻接点的访问。因此,可采用队列来暂存那些刚被访问过,但可能还有未访问的邻接点的顶点。现在,我们以邻接矩阵作为图的存储结构,给出广度优先搜索遍历算法。下面以图7.7(a)中G图为例说明广度优先搜算法7.4Voidbfs(intk)/*从vk出发广度优先遍历图Ｇ,Ｇ用邻接矩阵表示*/

{r=0;f=0;/*置空队列qu,f和r分别是头指针和尾指针*/printf("%c\n",g.vexs［k］);/*访问出发点vk+1*/visited［k］=1;/*标记vk已访问过*/

r++;qu［r］=k;/*已访问过的顶点（序号）入队列*/

while(r![KG-*2]=f)/*队非空时执行*/

{f++;i=qu［f］;/*队头元素序号出队列*/

for(j=1;j<=n;j++)算法7.4if((g.arcs［i］［j］==1)&&((!visited［j］))

{printf("%c\n",g.vexs［j］;/*访问vi的未曾访问的邻接点vj*/

visited［j］=1;

r++;qu［r］=j;/*访问过的顶点入队列*/

}/*if*/

}/*while*/

}/*bfs*/if((g.arcs［i］［j］==1)&&((

7.3.3求图的连通分量如果要遍历一个非连通图,则需多次调用dfs或bfs。每一次都得到一个连通分量;调用dfs或bfs的次数就是连通分量的个数。因此很容易写出非连通图的遍历算法和计算一个图的连通分量的算法。下面给出以邻接矩阵为存储结构,通过调用深度优先搜索算法实现的计算连通分量的算法。算法7.5

voidcomponent()

{count=0;

for(i=1;i<=n;i++)

visited［i］=0;/*初始化标志数组*/7.3.3求图的连通分量for(i=1;i<=n;i++)

{if(

{count=count+1;

dfs(i);/*从顶点vi+1出发遍历一个连通分量*/

printf(″compend\n″);

}/*if*/

}/*for*/

printf(″Toyalcomponents:%d″,count);

}/*component*/for(i=1;i<=n;i++)

在此算法中,若将dfs换成bfs亦可,改换后的算法即是通过调用广度优先搜索算法实现的计算连通分量的算法。对图7.2所示的非连通图G3,执行算法component时,分别调用dfs(1)和dfs(6),可求出两个连通分量:

v1,v2,v3,v4,v5compend

v6,v7compend

TotalComponents:2因为一旦调用了dfs(i)之后,顶点vI即被做上了访问标记,而对每个顶点v1,dfs(i)最多只能被调用一次,因此,算法component中调用及内部递归调用自己,其次数仍是n,故算法的时间复杂度是O(n2)。在此算法中,若将dfs换成bfs亦可,改7.4图的生成树

7.4.1生成树的概念设图G=(V,E)是个连通图,当从图任一顶点出发遍历图G时,将边集E(G)分成两个集合A(G)和B(G)。其中A(G)是遍历图时所经过的边的集合,B(G)是遍历图时未经过的边的集合。显然,G1=(V,A)是图G的子图。我们称子图G1是连通图G的生成树。图的生成树不是唯一的。如对图7.7中的图G,当按深度和广度优先搜索法进行遍历就可以得到图7.8所示的两种不同的生成树,并分别称为深度优先生成树和广度优先生成树。对于有n个顶点的连通图,至少有n-1条边,而生成树中恰好有n-1条边,所以连通图的生成树是该图的极小连通子图。若在图G的生成树中任意加一条属于边集B(G)中的边,则必然形成回路。7.4图的生成树7.4.1课件-数据结构教学第7章图-

7.4.2最小生成树

1.网络的概念若将图的每条边都赋上一个权,则称这种带权的图为网络。通常权是具有某种意义的数,比如,我们可以表示两个顶点之间的距离,耗费等。图7.9就是两个网络的例子。若G=(V,E)是网,则邻接矩阵可定义为

aij=Wij若(vi,vj)或〈V〉∈E

0若i=j

∞若(vi,vj)或〈vi,vj

〉E其中Wij

表示边上的权值;∞表示一个计算机允许的、大于所有边上权值的数。7.4.2最小生成树课件-数据结构教学第7章图-A1=0615∞∞605∞3∞1505645∞50∞2∞36∞06∞∞4260A2=01∞234∞∞01∞∞∞∞∞∞0∞∞4∞∞∞20∞∞∞∞∞∞∞0∞3∞∞∞∞∞0∞∞∞3∞∞50

2.最小生成树的定义及MST性质以下讨论无向网络(简称网络或网)的最小生成树问题。A1=0615∞∞A2=0

如果连通图是一个网络,称该网络中所有生成树中权值总和最小的生成树为最小生成树(也称最小代价生成树)。图7.10给出图7.9(a)的几棵生成树。其中(a)的权为26,(b)的权为16,(c)的权为15,可以证明(c)为一棵最小生成树。求网络的最小生成树是一个具有重大实际意义的问题。例如,要求沟通n个城市之间的通讯线路,需要建造n-1条通讯线路。可以把n个城市看作图的n个顶点,各个城市之间的通讯线路看作边,相应的建设花费作为边的权,这样就构成了一个网络。由于在n个城市之间,可行线路有(n*(n-1))/2条,那么,如何选择其中的n-1条线路(边)在n个城市间建成全都能相互通讯的网,并且总的建设花费为最小?这就是求该网络的最小生成树问题。如果连通图是一个网络,称该网络中所有生成树课件-数据结构教学第7章图-

构造最小生成树的方法很多,其中大多数算法都利用了称之为MST的性质。MST性质:设G=(V,E)是一个连通图,T=(U,TE)是正在构造的最小生成树。若边(u,v)是G中所有一端在U中(即u∈U)而另一端在V-U中(即v∈V-U)具有最小权值的一条边,则存在一棵包含边(u,v)的最小生成树。证明(反证法):设网络G的任何一棵最小生成树T都不包含(u,v),当把(u,v)加到T中,则根据生成树的定义和性质,生成树T中必然存在一条包含(u,v)的回路(见图7.11),并且T中必然已有另一条边(u′,v′),其中u′∈U,v′∈V-U,且u和u′,v和v′之间均有路径相通。构造最小生成树的方法很多,其中大多数算法课件-数据结构教学第7章图-

7.4.3普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法如何利用MST性质来构造最小生成树呢？一般有构造它的Prim算法和Kruskal算法,我们先介绍Prim算法。

Prim算法的基本思想如下:假设G=(V,E)是连通网,T=(U,TE)为欲构造的最小生成树。初始化U={u0},TE=φ。重复下述操作:在所有u∈U,v∈V-U的边(u,v)∈E中,选择一条权最小的边(u,v)并入TE,同时将v并入U,直到U=V为止。这时产生的TE中具有n-1条边。容易看出,上述过程求得的T=(U,TE)是G的一棵最小生成树。连通网用邻接矩阵net表示,若两个顶点之间不存在边,其权值用一大于任何边上权值的较大数max来表示不存在边的长度。数据类型定义和普里姆算法描述如下:7.4.3普里姆(Prim)算法和克鲁斯卡尔(Kru算法7.6typedefstruct

{intbegin,end;/*边的起点和终点*/

floatlength;/*边的权值*/

}edgefloatnet［n］［n］;/*连通网的带权邻接矩阵*/edgetree［n-1］;/*生成树*/voidPrim(void)

{/*构造网net的最小生成树,u0=1为构造出发点*/

intj,k,m,v,min,max=10000;算法7.6floatd;

edgee;

for(j=1;j<n;j++)/*初始化tree［n-1］*/

{tree［j-1］.begin=1;/*顶点1并入U*/

tree［j-1］.end=j+1;

tree［j-1］.length=net［0］［j］;

}

for(k=0;k<n-1;k++)/*求第k+1条边*/

{min=max;floatd;for(j=k;j<n-1;j++)if(tree［j］.length<min)

{min=tree［j］.length;m=j;}

e=tree［m］;tree［m］=tree［k］;tree［k］=e;

v=tree［k］.end;/*V∈U*/for(j=k+1;j<n-1;j++)/*在新的顶点v并入U之后更新tree［n-1］*/{d=net［v-1］［tree［j］.end-1］;

if(d<tree［j］.length)

{tree［j］.length=d;for(j=k;j<n-1;j++)if(tretree［j］.begin=v;

}/*if*/

}/*for*/

}/*for*/

for(j=1;j<n;j++)

printf(″%d%d%f\n″,tree［j］.begin,tree［j］.end,tree［j］.length);

}/*Prim*/求图7.9中网的最小生成树的Prim算法的执行过程如图7.12所示。t课件-数据结构教学第7章图-

在图7.12中,(a)为一个网,此时U={1},V-U={2,3,4,5,6},在和1相关联的所有的边中,(1,3)的权值最小,因此取(1,3)为最小生成树的第一条边,如(b)所示;此时U={1,3},V-U={2,4,5,6},在和1、3相关联的所有边中,(3,6)为权值最小的边,取(3,6)为最小生成树的第二条边,如(c)所示;现在U={1,3,6},V-U={2,4,5},在和1、3、6相关联的所有边中,(6,4)的权值最小,取(6,4)为最小生成树的第三条边,如(d)所示;这样,U={1,3,6,4},V-U={2,5},在所有和1、3、6、4相关联的边中,(3,2)为权值最小的边,取(3,2)为最小生成树的第四条边,如(e)所示;U={1,3,6,4,2},V-U={5},U中顶点和5相关联的权值最小的边为(2,5),取(2,5)为最小生成树的第五条边,如(f)所示。(f)为最终得到的最小生成树。在图7.12中,(a)为一个网,此时U={Prim算法的初始化时,其时间复杂度为O(n),但k循环内有两个循环语句,故这个循环的总时间为O(n2),所以整个算法的时间复杂度是O(n2)。Prim算法的运算量与网的边数有关,因此适合于求边稠密的网的最小生成树。构造最小生成树的另一算法是一种按权值递增的次序来构造最小生成树的方法,这是由Kruskal提出的。

Kruskal算法的基本思想如下:设G=(V,E)是连通网,最小生成树T=(V,TE),初始时TE=Ф,即T仅包含网G的全部顶点,T中每个顶点自成一个连通分量,在图G的边集E中按权值自小至大依次选择边(u,v),若该边端点u、v分别是当前T的两个连通分量T1、T2中的顶点,则将该边加入到T中,T1、T2也由此连接成一个连通分量;若u、v是当前同一个连通分量中的顶点,则舍去此边,依次类推,直到T中所有顶点都在同一连通分量上为止,T便成为G的一棵最小生成树。Prim算法的初始化时,其时间复杂度为O(

此算法可以简单描述如下:

T=(V,Φ);

While(T中所有边数<n-1)

{从E中选取当前最短边(u,v);从E中删去边(u,v);

If((u,v)并入T之后不产生回路)将(u,v)并入T中;

}按此算法思想对图7.12(a)的网进行处理,逐步形成最小生成树的过程如图7.13所示。可以证明Kruskal算法的时间复杂度是O(e),其中e是图G的边数。此算法可以简单描述如下:课件-数据结构教学第7章图-7.5最短路径

7.5.1单源顶点最短路径问题求解设从顶点v1出发,找从它到图中所有其它各顶点的最短路径。迪杰斯特拉(Dijkstra)提出了一个按路径长度递增的顺序产生最短路径的方法。此方法的基本思想是:把图中所有的顶点分成两组,第一组包括已确定最短路径的顶点,第二组包括尚未确定最短路径的顶点,按最短路径长度递增的顺序逐个把第二组的顶点加到第一组中去,直至从v1出发可以到达的所有顶点都包括在第一组中。在这个过程中,总保持从v1到第一组各顶点的最短路程长度,都不大于从v1到第二组的任何顶点的最短路径长度。另外,每一个顶点对应一个距离值,第一组的顶点对应的距离值就是从v1到此顶点的只包括第一组的顶点为中间顶点的最短路径长度。7.5最短路径7.5.1单源顶点最短路

具体的做法是:一开始第一组只包括顶点v1,第二组包括其它所有顶点,v1对应的距离值为0,第二组的顶点对应的距离值是这样确定的:若图中有边〈v1,vj

〉,则vj的距离为此边所带的权值,否则vj的距离值为一个很大的数(大于所有顶点间的路径长度),然后每次从第二组的顶点中选一个距离值为最小的vm加入到第一组中。每往第一组加入一个顶点vm,就要对第二组的各个顶点的距离值进行一次修正。若加进vm做中间顶点,使从v1到vj的最短路径比不加vm的路径为短,则要修改vj的距离值。修改后再选距离最小的顶点加入到第一组中。具体的做法是:一开始第一组只包括顶点v1,

如此进行下去,直到图中所有顶点都包括在第一组中,或再也没有可加入到第一组中的顶点存在为止。假设有向图G的n个顶点为1到n,并用邻接矩阵cost表示,若〈vi,vj

〉是图G中的边,则cost［i］［j］的值等于边所带的权;若〈vi,vj〉不是图G中的边,则cost［i］［j］等于一个很大的数;若i=j,则cost［i］［j］=0。另外,设置3个数组S［n］、dist［n］、pre［n］。S用以标记那些已经找到最短路径的顶点,若S［i-1］=1,则表示已经找到源点到顶点i的最短路径；若S［i-1］=0,则表示从源点到顶点i的最短路径尚未求得。dist［i-1］用来记录源点到顶点i的最短路径。

pre［i-1］表示从源点到顶点i的最短路径上该点的前趋顶点,若从源点到该顶点无路径,则用0作为其前一个顶点序号。算法描述如下。如此进行下去,直到图中所有顶点都包括在第一算法7.7

voidDijkstra(floatcost［］［n］,intv)

{/*求源点v到其余顶点的最短路径及其长度,cost为有向网的带权邻接矩阵*//*设max值为32767,代表一个很大的数*/

v1=v-1;

for(i=0;i<n;i++)

{dist［i］=cost［v1］［i］;/*初始化dist*/

if(dist［i］<max)pre［i］=v;elsepre［i］=0;

}算法7.7pre［v1］=0;

for(i=0;i<n;i++)S［i］=0;/*第一组开始为空集*/

S［v1

］=1;/*源点v并入第一组*/

for(i=0;i<n;i++)/*扩充第一组*/

{min=max;

for(j=0;j<n;j++)

if(!S［j］&&(dist［j］<min)){min=dist［j］;k=j;}S［k］=1;/*将k+1加入第一组*/

for(j=0;j<n;j++)

if(!S［j］&&(dist［j］>dist［k］+cost［k］［j］))/*修正第二组各顶点的距离值*/pre［v1］=0;{dist［j］=dist［k］+cost［k］［j］;pre［j］=k+1;}/*k+1是j+1的前趋*/

}/*所有顶点均已扩充到S中*/

for(j=0;j<n;j++)/*打印结果*/

{printf(″%f\n%d″,dist［i］,i+1);

p=pre［i］;

while(p![KG-*2]=0)/*继续找前趋顶点*/

{printf(″<″%d″,p};

p=pre［p-1］;

}

}

}/*Dijkstra*/{dist［j］=dist［k］+cost

例如,对图7.14所示的有向网络实施算法7.7,若源点为1,邻接矩阵cost如左,则运算执行中S,dist及pre的变化状况如表7.1所示。

∞050∞∞∞∞0∞10∞∞20060∞∞∞∞0

由表7.1容易看出,Dijkstra算法的时间复杂度为O(n2)。例如,对图7.14所示的有向网络实施算法7课件-数据结构教学第7章图-课件-数据结构教学第7章图-

7.5.2求有向网中每对顶点间的路径给出一个含有n个顶点的带权有向网,要求其每一对顶点之间的最短路径。解决这个问题的一种方法是反复执行n次Dijkstra算法,每次执行以一个顶点为起始顶点,求得从该顶点到其它各顶点的最短路径;执行n次之后,就能求得从每一个顶点出发到其它各顶点的最短路径。弗洛伊德(Floyd)提出了另一种算法,这种算法仍用邻接矩阵cost表示带权有向图。如果从vi到vj有弧,则从vi到vj存在一条长度为cost［i］［j］的路径,该路径不一定是最短路径,需要进行n次试探。首先考虑路径(vi,v1,vj)是否存在(即判别弧〈vi,v1

〉和〈v1,vj

〉是否存在),如果存在,则比较〈vi,v1v〉和〈vi,vj

〉的路径长度,取较短者为从v到vj的中间顶点序号不大于1的最短路径。7.5.2求有向网中每对顶点间的路径

在路径上再增加一个顶点v2,若(vi,…,v2)和(v2,…,vj)分别是当前找到的中间顶点序号不大于1的最短路径,则(vi,…,v2,…,vj)就有可能是从v到vj的中间顶点的序号不大于2的最短路径。将它和已经得到从vi到vj中间顶点序号不大于1的最短路径相比较,从中选出长度较短者作为从vi到vj中间顶点序号不大于2的最短路径之后,再增加一个顶点v3,继续进行试探,依次类推。在一般情况下,若(vi,…,vk)和(vk,…,v)分别是从vi到vk和从vk到vj的中间顶点序号不大于k-1的最短路径,则将(vi,…,vk,…,vj)和已经得到的vi到vj且中间顶点序号不大于k-1的最短路径相比较,取其长度较短者作为从vi到vj的中间顶点序号不大于k的最短路径。在路径上再增加一个顶点v2,若(vi,…

如此重复,经过n次比较后,最后求得的必是从vi到vj的最短路径。用此方法,可同时求得每对顶点间的最短路径。综上所述,弗洛伊德(Floyd)算法的基本思想是递推地产生一个矩阵序列:A0,A1,…Ak,…An,其中:

A0［i］［j］=cost［i］［j］

Ak

［i］［j］=Min{A(k-1)［i］［j］,A(k-1)

［i］［k］+(k-1)［k］［j］}(1≤k≤n)由上述公式可以看出,A1［i］［j］是从vi到vj中间顶点序号不大于1的最短路径长度;Ak

［i］［j］是从vi到vj中间顶点序号不大于k的最短路径长度;An［i］［j］是从vi到vj的最短路径长度。如此重复,经过n次比较后,最后求得的必是

还设置一个矩阵path,path［i］［j］是从vi到vj中间顶点序号不大于k的最短路径上vi的一个邻接顶点的序号,约定若vi到vj无路径时path［i］［j］=0。由path［i］［j］的值,可以得到从vi到vj的最短路径。算法描述如下：算法7.8

intpath［n］［n］/*路径矩阵*/

voidFloyd(floatA［］［n］,cost［］［n］);

{/*A是路径长度矩阵,cost是有向网G,max=32767代表一个很大的数*/

for(i=0;i<n;i++)/*设置A和path的初值*/还设置一个矩阵path,path［i］［jfor(j=0;j<n;j++)

{if(cost［i］［j］<max)path［i］［j］=j;/*j是i的后继*/else{path［i］［j］=0;A［i］［j］=cost［i］［j］;

}

for(k=0;k<n;k++)

/*做n次迭代,每次均试图将顶点k扩充到当前求得的从i到j的最短路径上*/

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(A［i］［j］>(A［i］［k］+A［k］［j］))/*修改长度和路径*/for(j=0;j<n;j++){A［i］［j］=A［i］［k］+A［k］［j］;path［i］［j］=path［i］［k］;}

for(i=0;i<n;i++)/*输出所有顶点对i,j之间的最短路径的长度及路径*/

for(j=0;j<n;j++)

{printf(″%f″,A［i］［j］);/*输出最短路径的长度*/next=path［i］［j］;/*next为起点i的后继顶点*/if(next==0)/*i无后继表示最短路径不存在*/{A［i］［j］=A［i］［k］+A［kprintf(″%dto%dnopath.\n″,i+1,j+1)

else/*最短路径存在*/

{printf(″%d″,i+1);

while(next![KG-*2]=j+1)/*打印后继顶点,然后寻找下一个后继顶点*/

{printf(″″-->%d″,next);next=path［next-1］［j］;}printf(″″-->%d\n″,j+1);

}/*else*//*打印终点*/*/

}/*for*/

}/*Floyd*/printf(″%dto%dnopath.\n″,

以图7.14中的有向网络为例实施上述算法,迭代过程中A和path的变化及其最终输出的结果见图7.15。图中A0=cost,∝在机内表示为max。对此例而言,迭代时有:A1=A0,path1=path0,A5=A4,path5=path4,因此表中省略了A1,path1,A5和path5。算法输出的结果是由最终求得的路径长度矩阵A5和路径矩阵path5求得的。以图7.14中的有向网络为例实施上述算法,课件-数据结构教学第7章图-7.6有向无环图及应用

7.6.1拓朴排序所有的工程或者某种流程都可以分为若干个小的工程或者阶段,称这些小的工程或阶段为“活动”。若以图中的顶点来表示活动,有向边表示活动之间的优先关系,则这样的有向图称为AOV(ActivityOnVertexnetwork)网。在AOV网中,若从顶点vi到顶点vj之间存在一条有向路径,称顶点vi是顶点vj的前趋,或者称顶点vj是顶点vi的后继。若〈vi,vj

〉是图中的弧,则称顶点vi是顶点vj的直接前趋,顶点vj是顶点vi的直接后继。

AOV网中的弧表示了活动之间存在的制约关系。7.6有向无环图及应用7.6.1拓朴排

例如,计算机专业的学生必须完成一系列规定的专业基础课和专业课才能毕业,这个过程就可以被看成是一个大的工程,而活动就是学习每一门课程。我们不妨把这些课程的名称与相应的代号列于表7.2。其中C1,C13是独立于其它课程的基础课,而有的课却需要有先行课（如学完解析几何才能学微积分）,前提条件规定了课程之间的优先关系。这种优先关系可以用图7.16所示的有向图来表示。其中,顶点表示课程,有向边表示前提条件。若课程vi为课程vj的前行课,则必然存在有向边〈vi,vj

〉。例如,计算机专业的学生必须完成一系列规定课件-数据结构教学第7章图-课件-数据结构教学第7章图-

显然,任何一个可执行程序也可以划分为若干个程序段(或若干语句),由这些程序段组成的流程图也是一个AOV网。

对于一个AOV网,常常要以有向图的次序关系为前提,为每个单项活动进行的先后安排一个线性序列的次序关系,如对图7.16来说,(C1,C13,C4,C8,C14,C15,C5,C2,C3,C10,C7,C11,C12,C6,C9)是一个可行的线性序列,因为有向图Ci是Cj的前趋,则在上述线性序列中Ci排在Cj的前面。在AOV网中不允许出现环,因为环意味着某项子工程的开工将以本身工作完成为先决条件,这显然是不合理的。检测有环的一个方法是,把AOV网中全部顶点排成一个线性序列,使得在此序列中顶点之间不仅保持有向图中原有的次序关系,而且在有向图中所有无关系的各对顶点之间人为建立一个次序关系。显然,任何一个可执行程序也可以划分为若干个

若有向图无环,则可构造一个包含图中所有顶点的线性序列。称具有上述特性的线性序列为拓朴有序序列。对AOV网构造拓朴有序序列的运算称为拓朴排序。若AOV有环,则找不到该网的拓朴有序序列。反之,任何无环有向图,其所有顶点都可以排在一个拓朴有序序列里。一个AOV网的拓朴有序序列不是唯一的。例如,对图7.16的有向图顶点进行拓朴排序,还可以得到(C1,C13,C4,C8,C14,C15,C2,C3,C10,,C11,C12,C9,C9,C7,C5)。对AOV网进行拓朴排序的方法和步骤如下:若有向图无环,则可构造一个包含图中所有顶点(1)从AOV网中选择一个没有前趋的顶点（该顶点的入度为0）并且输出它;

(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边;

(3)重复上述两步,直到剩余网中不再存在没有前趋的顶点为止。操作的结果有两种:一种是网中全部顶点都被输出,这说明网中不存在有向回路,拓朴排序成功;另一种是网中顶点未被全部输出,剩余的顶点均有前趋顶点,这说明网中存在有向回路,不存在拓朴有序序列。图7.17给出了一个AOV网实施上述步骤的例子。这样得到一个拓朴序列(v1,v6,v4,v3,v2,v5)。(1)从AOV网中选择一个没有前趋的顶点课件-数据结构教学第7章图-

为了实现上述思想,我们采用邻接链表作为给定的AOV网的存储结构,在表头结点增设一个入度域,以存放各个顶点当前的入度值,每个顶点的入度域的值都随邻接链表动态生成过程中累计得到,由图7.17的AOV网生成的邻接链表如图7.18(a)所示。为了避免在每一步选入度为零的顶点时重复扫描表头数组,利用表头数组中入度为零的顶点域作为链栈域,存放下一个入度为零的顶点序号,零表示栈底,栈顶指针为top,寄生在表头数组的入度域中的入度为零的顶点链表如图7.18(b)所示。栈顶指针top=6指出v6的入度为零,v6的入度域为1,指出下一个入度为零的顶点是v1,v1的入度为零表示v1是栈底。根据上面的叙述,我们得到邻接链表作存储结构的拓朴排序算法梗概如下:为了实现上述思想,我们采用邻接链表作为给定课件-数据结构教学第7章图-(1)扫描顶点表,将入度为零的顶点入栈;

(2)While(栈非空)

{将栈顶点vj弹出并输出之;在邻接链表中查vj的直接后继vk,把vk的入度减1,若vk的入度为零则进栈;}

(3)若输出的顶点数小于n,则输出“有回路”;否则拓朴排序正常结束。下面给出求精的拓朴排序算法。算法7.9

typedefstructnode

{intvex;(1)扫描顶点表,将入度为零的顶点入栈;typedefstructvnode{intid;

structnodelink;}vexnode;voidtoposort(vexnodedig［］)

{/*AOV网的邻接链表*/

edgenode*p;

top=0;m=0;

for(i=1;i<n+1;i++)/*入度为零的顶点进栈*/if(dig［i］.id==0){dig［i］.id=top;top=i;}typedefstructvnodeWhile(top>0)

{j=top;top=dig［top］.id;

printf(″%d\n″,j);