数据结构-图详述

第七章图前面介绍了两种基本数据结构：线性表和树。线性表是一种线性结构，除了头尾结点外，每个结点只有一个前驱结点和一个后继结点。树是一种非线性结构，数据元素(结点)之间的关系是父子关系，每个结点有且仅有一个双亲结点，有0个或多个孩子结点，在结点之间建立了一种层次关系。图是一种新的数据结构，其数据元素(顶点)之间的关系是任意的，每个顶点都可以和其他任何顶点相关。是种比线性表和树更加复杂的数据结构，而树实际上是一种特殊形式的图。数据结构-图详述全文共104页，当前为第1页。第七章图本章主要内容：1.图的定义及存储结构2.图的两种遍历及图的连通性3.拓扑排序和关键路径以及求最短路径的方法本章重点：1.图的各种存储结构及其构造算法2.图的两种搜索路径的遍历3.应用图的遍历算法求解各种简单路径问题数据结构-图详述全文共104页，当前为第2页。第七章图7.1图的定义和术语

7.2图的存储结构

7.3图的遍历

7.4图的连通性

7.5有向无环图及其应用

7.6最短路径数据结构-图详述全文共104页，当前为第3页。7.1图的定义和术语一、图的定义和术语二、抽象数据类型图的定义数据结构-图详述全文共104页，当前为第4页。

一、图的定义和术语7.1图的定义和术语1．图的定义图由两个集合V和E构成，记为G=(V,E)，其中V是顶点的有限集合，E是连接V中两个不同顶点(顶点对)的边的有限集合。数据结构-图详述全文共104页，当前为第5页。2．图的有关术语顶点：图中的数据元素，v1,v2。有向图：E中的顶点对是有序的，即每条边都是有方向的则称G为有向图。(3)弧：有向图的边,<v,w>表示从v到w的一条弧。(4)弧头：弧的终点w。

弧尾：弧的起始点v。(5)无向图：E中顶点对是无序的，则称G为无向图。无向图中若存在(v,w)E,则必有(w,v)E。

一、图的定义和术语7.1图的定义和术语数据结构-图详述全文共104页，当前为第6页。(6)边：无向图的边。

用n表示图中顶点数目，用e表示边或弧的数目。(7)完全图：对于无向图0≤e≤n(n-1)/2,具有n(n-1)/2条边的无向图称为完全图。(8)有向完全图：对于有向图0≤e≤n(n-1)，具有n(n-1)条弧的有向图称为有向完全图。(9)稀疏图：有很少条边或弧(e<nlogn),反之称为稠密图。(10)

权：与图的边或弧相关的数叫做权。(11)网：带权的图。(12)子图：有两个图G=(V,E)和G’=(V’,E’)，如果V’V且E’E，则称G’为G的子图。

一、图的定义和术语7.1图的定义和术语数据结构-图详述全文共104页，当前为第7页。

(13)邻接点、关联：对于无向图G=（V，E）,如果边(v,v’)E，则称顶点v和v’互为邻接点，即v和v’相邻接。称(v,v’)和顶点v和v’相关联。

(14)度：和顶点v相关联的边或弧的数目TD。

(15)入度：若G是有向图，则以v为终点的弧的个数ID。

(16)出度：若G是有向图，则以v为始点的弧的个数OD。

(17)路径：无向图从顶点vp到vq的路径是一个顶点序列(vp,v1,v2,…vq-1,vq)，且(vp,v1),(v1,v2)…(vq-1,vq)属于E(G)，其中vp是起点，vq是终点。若是有向图，路径是有向。

(18)路径长度：路径上的边或弧的数目。

一、图的定义和术语7.1图的定义和术语数据结构-图详述全文共104页，当前为第8页。(19)回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环。(20)简单路径：序列中顶点不重复出现的路径。

(21)简单回路(简单环)：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，或始点和终点相同的简单路径。(22)

连通(可及)：在图G中，若从顶点v到v’有路径，则称v和v’是连通的(可及的)。(23)连通图：在无向图G中，任意两个顶点都是连通的，称图G是连通图。(24)连通分量：无向图中的极大连通子图。

一、图的定义和术语7.1图的定义和术语数据结构-图详述全文共104页，当前为第9页。

(25)强连通图：在有向图G中，对于任意两个不同顶点vi和vj;vi和vj连通，vj和vi连通，称G为强连通图。

(26)强连通分量：有向图中的极大连通子图称作有向图的强连通分量。

(27)(无向图的)生成树：在一个无向连通图G中，若取它的全部顶点和一部分边构成一个子图G’，即：

V(G’)=V(G)和E(G’)E(G)

若边集E(G’)中的边将图G中所有顶点连通又不形成回路，则称子图G’是原图G的一棵生成树。(无向图的)生成树——无回路的、连通的、无向的图。定理：一棵n个顶点的生成树有且仅有n-1条边。

一、图的定义和术语7.1图的定义和术语数据结构-图详述全文共104页，当前为第10页。(28)有向树：一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，此有向图是一棵有向树。(29)(有向树的)生成森林:由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。3．图有关术语的示例(1)设图G=(V,E)，V={a,b,c,d,e}，E={<a,b>,<a,c>,<b,d>,<c,e>,<d,c>,<e,d>。回答下列问题：a.

求与顶点b相关联的弧；b.

是否存在从顶点c到b的路径？c.求ID(d)、OD(d)、TD(d);d.

该有向图中是否是强连通图？

一、图的定义和术语7.1图的定义和术语数据结构-图详述全文共104页，当前为第11页。解：a.与顶点b相关联的弧有两条：<a,b>和<b,d>；

b.不存在从顶点c到b的路径；c.ID(d)=2;OD(d)=1,TD(d)=3;d.不是强连通图；

一、图的定义和术语7.1图的定义和术语数据结构-图详述全文共104页，当前为第12页。7．2图的存储结构一、邻接矩阵（数组表示法）二、邻接表三、十字链表四、多重邻接表数据结构-图详述全文共104页，当前为第13页。

一、邻接矩阵7.2图的存储结构

邻接矩阵(AdjacencyMatrix)是一种用来表示图中顶点间相邻关系的矩阵，是一种用边的集合表示图的方法。1．一维数组存储图的顶点v0,v1,…vn-1，用n阶矩阵A=(aij)表示图的边或弧，A的定义如下：(1)

若图为有权图，aij对应边<vi,vj>或(vi,vj)的权值，

(2)

若图为非权图，则

aii=0;aij=1，当i≠j且<vi,vj>或(vi,vj)存在时；

aij=0，当i≠j且<vi,vj>或(vi,vj)不存在时。称矩阵A为图的邻接矩阵。∞当i=jWij有<vi,vj>或(vi,vj)∞无aij=数据结构-图详述全文共104页，当前为第14页。

例1：如图所示的是有权图(网)的邻接矩阵：

012340∞27∞11∞∞∞∞∞2∞∞∞5∞3∞∞∞∞∞43∞∞4∞7.2图的存储结构

一、邻接矩阵数据结构-图详述全文共104页，当前为第15页。例2：无权图的邻接矩阵：

1234101112100131001411107.2图的存储结构

一、邻接矩阵数据结构-图详述全文共104页，当前为第16页。2.邻接矩阵存储表示#defineINFINITYINT_MAX//最大值∞(定义infinity为最大值)#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{DG,DN,UDG,UDN}GraphKind；//{有向图，有向网，无向图，无向网}typedefstructArcCell{VRTypeadj；//VRType是边(或弧)的类型。对无权图，用1

或0表示相邻否；对带权图，则为权值类型。InfoType*Info；

//该弧相关信息的指针}ArcCell，AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedrfstruct{VertexTypevexs[MAX_VERTEX_NUM]；//顶点向量

AdjMatrixarcs；//邻接矩阵

Intvexnum,arcnum；//图的当前顶点数和弧数

GraphKindkind；//图的种类标志}Mgraph；7.2图的存储结构

一、邻接矩阵数据结构-图详述全文共104页，当前为第17页。3．邻接矩阵的性质(1)在图中各顶点的序号确定后，图的邻接矩阵是唯一确定的；(2)无向图和无向网的邻接矩阵是一个对称矩阵；(3)对于无向图，顶点的度是邻接矩阵中第i行(或第i列)的非零元素个数之和；(4)对于有向图，第i行的非零元素个数之和为顶点vi的出度，第j列的非零元素个数之和为顶点vj的入度。(5)无向图的边数等于邻接矩阵中非零元素个数之和的一半，有向图的弧数等于邻接矩阵中非零元素个数之和。

一、邻接矩阵7.2图的存储结构数据结构-图详述全文共104页，当前为第18页。4．邻接矩阵的特点(1)邻接矩阵可采用压缩存储(2)操作特点适于进行边或弧的删除和插入操作。但不易于进行顶点的插入删除操作。

一、邻接矩阵7.2图的存储结构数据结构-图详述全文共104页，当前为第19页。5．构造无向网的算法statuscreateUDN(Mgraph&G)//用邻接矩阵表示，构造无向网G{scanf(&G.vexnum,&G.arcnum,&Incinfo)；//输入顶点数、边数和信息

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

IncInfo为0则各弧不含其它信息

scanf(&G.vexs[i])；

//构造顶点向量

for(i=0;i<G.vexnum;++i)//初始化邻接矩阵

for(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};//{adj,info}for(k=0;k<G.vexnum;++k)//构造邻接矩阵

{scanf(&v1,&v2，&w)；//输入一条边依附的顶点(弧尾、弧头)及权值

i=LocateVex(G,v1)；//确定v1和v2在G中位置

j=LocateVex(G,v2)；

G.arcs[i][j].adj=w；

if(Incinfo)Input(*G.arcs[i][j].info);若含有相关信息，输入

G.arcs[j][i]=G.arcs[i][j];//置<v1,v2>的对称弧<v2,v1>}returnOK;}

一、邻接矩阵7.2图的存储结构数据结构-图详述全文共104页，当前为第20页。1．边链表依附于顶点V的所有边（或为弧尾的弧）以某种次序组成一个链表，被称为顶点V的边链表。在边链表中，其结点结构：其中：adjvex域存放v的某个邻接顶点在顶点表中的序号；

nextarc域存放指针，指向下一个边或弧的结点；

info域存放边<v,adjvex>的权值。边链表表示依附某顶点vi的边信息(有向图是以顶点vi为弧尾的弧)，其结点结构称为边结点。adjvexinfonextarc有两部分：边链表：依附某顶点的边信息构成的单链表顶点表：用一维数组存储顶点本身及边链表的头指针

二、邻接表7.2图的存储结构数据结构-图详述全文共104页，当前为第21页。2．顶点表用顺序存储方式存储图的顶点表v0,v1,v2,…vn-1，每个顶点的结构：

datafirstarc其中：data域放该顶点的名称；

firstarc域是指针域，存放指向顶点相关边链表的第一个边结点的指针。3．邻接表

由顺序存储的顶点表和链接存储的边链表构成的图的存储结构被称为邻接表。

二、邻接表7.2图的存储结构数据结构-图详述全文共104页，当前为第22页。例3：例1的邻接表：01234

二、邻接表7.2图的存储结构数据结构-图详述全文共104页，当前为第23页。例1的逆邻接表01234

二、邻接表7.2图的存储结构数据结构-图详述全文共104页，当前为第24页。例2邻接表：1234

二、邻接表7.2图的存储结构数据结构-图详述全文共104页，当前为第25页。4．邻接表的存储表示#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;//该弧指向的顶点的位置

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

Infotype*info;//与该弧相关的信息(权)}ArcNode;typedefstructVnode{vertexTypedata;//顶点信息

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

弧的指针

}Vnode，AdjList[MAX_VERTEX_NUM]；

二、邻接表7.2图的存储结构数据结构-图详述全文共104页，当前为第26页。typedefstruct{AdjListvertices；

intvexnum,arcnum；//图的当前顶点数和弧数

intkind；//图的种类标志

}ALGraph;

二、邻接表7.2图的存储结构数据结构-图详述全文共104页，当前为第27页。5．邻接表的性质(1)图的邻接表表示不唯一的，它与边结点的次序有关；(2)无向图的邻接表中第i个顶点的度为第i个链表中结点的个数；(3)有向图的邻接表中第i个链表的结点的个数是第i个顶点的出度；而第i个顶点的入度需遍历整个链表，采用逆邻接表,建立一个以vi顶点为头的弧的表。(4)无向图的边数等于邻接表中边结点数的一半，有向图的弧数等于邻接表中边结点数。

二、邻接表7.2图的存储结构数据结构-图详述全文共104页，当前为第28页。6．邻接表的特点(1)对于顶点多边少的图采用邻接表存储节省空间；(2)容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点之间是否有边或弧相连，则需搜索第i个或第j个链表。

二、邻接表7.2图的存储结构数据结构-图详述全文共104页，当前为第29页。练习题：已知无向图G的邻接表如下，画出无向图G。12345数据结构-图详述全文共104页，当前为第30页。答案：

数据结构-图详述全文共104页，当前为第31页。

十字链表是有向图另一种链式存储结构。是将有向图的邻接表和逆邻接表结合起来得到的一种链表。包含弧结点和顶点结点。1．弧结点有五个域：三、十字链表tailvexheadvexhlinktlinkinfo其中：tailvex是尾域，指示弧尾顶点在图中的位置；

headvex是头域，指示弧头顶点在图中的位置；

hlink链域，指向弧头相同的下一条弧；

tlink链域，指向弧尾相同的下一条弧；

info域指向该弧的相关信息。弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。

7.2图的存储结构数据结构-图详述全文共104页，当前为第32页。2．顶点结点顶点结点为弧结点构成的链表的头结点，由三个域组成。datafirstinfirstout其中：data域存储和顶点相关的信息，如顶点的名称等；

firstin链域指向以该顶点为弧头的第一个弧结点；

firstout链域指向以该顶点为弧尾的第一个弧结点。

三、十字链表7.2图的存储结构数据结构-图详述全文共104页，当前为第33页。例4:图的十字链表.三、十字链表7.2图的存储结构tailvexheadvexhlinktlinkinfodatafirstinfirstout数据结构-图详述全文共104页，当前为第34页。3．十字链表的存储表示#defineMAX_VEX_NUM20typedefstructArcBox{inttailvex,headvex;//该弧的尾和头顶点的位置

structArcBox*hlink,*tlink;//分别为弧头相同和弧尾相同的弧的链域

Infotype*info//该弧相关信息的指针

}ArcBox;typedefstructVexNode{Vertextypedata;ArcBox*firstin,*firstout;//分别指向该顶点第一条入弧(以该点为弧头)和出弧(以该点为弧尾)}VexNode;三、十字链表7.2图的存储结构数据结构-图详述全文共104页，当前为第35页。typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//顶点结点数组

intvexnum,arcnum;//有向图的当前顶点数和弧数

}OLGraph;

在十字链表中既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得顶点的出度和入度。三、十字链表7.2图的存储结构数据结构-图详述全文共104页，当前为第36页。

邻接多重表是无向图的另一种链式存储结构。在邻接表中一条边(vi,vj)有两个结点，分别在第i个和第j个链表中，若对边操作需在两个链表上操作。采用多重链表较适宜这种操作。1．边结点四、邻接多重表markivexilinkjvexjlinkinfo其中：mark为标志域，标记该条边是否被搜索过；

ivex和jvex为该边依附的两个顶点在图中的位置；

ilink指向下一条依附于顶点ivex的边；

jlink指向下一条依附于顶点jvex的边；

info为指向和边相关的各种信息的指针域。7.2图的存储结构数据结构-图详述全文共104页，当前为第37页。2.顶点结点datafirstedge其中：data域存储和该顶点相关的信息；

firstedge域指示第一条依附于该顶点的边。在多重链表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边结点同时链接在两个链表中。对无向图而言，其邻接多重表和邻接表的差别，仅仅在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。

四、邻接多重表7.2图的存储结构数据结构-图详述全文共104页，当前为第38页。例4：例2的邻接多重链表表示四、邻接多重表7.2图的存储结构markivexilinkjvexjlinkinfodatafirstedge数据结构-图详述全文共104页，当前为第39页。7.3图的遍历一、深度优先搜索二、广度优先搜索

图的遍历——从图的某一顶点出发访问图中的所有顶点，且每个顶点仅访问一次。图的遍历算法是求解图连通性问题、拓扑排序和求关键路径等算法的基础。数据结构-图详述全文共104页，当前为第40页。一、深度优先搜索7.3图的遍历

深度优先搜索(DepthFirstSearch)遍历类似于树的先根遍历，是树的先根遍历的推广。是一个递归过程。1.算法的基本思想(1)首先访问图中某一个顶点Vi，以该顶点为出发点；(2)任选一个与顶点Vi邻接的未被访问的顶点Vj；(3)以Vj为新的出发点继续进行深度优先搜索，直至图中所有和Vi有路径的顶点均被访问到。若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到。

数据结构-图详述全文共104页，当前为第41页。2．深度优先搜索的例子一、深度优先搜索7.3图的遍历数据结构-图详述全文共104页，当前为第42页。(1)首先访问出发点v1，v1有两个邻接点v2,v6，均未被访问，任选其一作为新的出发点，选v2；

(2)访问v2，v2有三个邻接点v1,v3,v7，其中v3,v7未被访问,选v3作为新的出发点；

(3)访问v3，v3邻接点v2,v4,v8，其中v4,v8未被访问,选v4作为新的出发点；

(4)访问v4，v4邻接点v3,v5,v8，其中v5,v8未被访问,选v5作为新的出发点；

(5)访问v5，v5邻接点v4,v6，其中v6未被访问,选v6作为新的出发点；一、深度优先搜索7.3图的遍历数据结构-图详述全文共104页，当前为第43页。(6)访问v6，v6邻接点v1,v5，并且均已被访问，因此，退回到出发点v5，但v5的两个邻接点v4,v6也均被访问过，因此再退回到v4，v4的三个邻接点中只有v8未被访问，选v8为新的出发点；

(7)访问v8，v8有四个邻接点，其中v7,v9未被访问，选v7为新的出发点；

(8)访问v7，v7有三个邻接点，其中只有v9未被访问，选v9为新的出发点；

(9)访问v9，至此图中所有顶点均被访问。得到了深度优先搜索遍历的顶点序列（DFS序列）：

v1→v2→v3→v4→v5→v6→v8→v7→v9一、深度优先搜索7.3图的遍历数据结构-图详述全文共104页，当前为第44页。3．深度优先搜索的算法Booleanvisited[MAX]；//访问标志数组Status(*VisitFunc)(intv)；VoidDFSTraverse(GraphG,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;v<G.vexnum;++v)visited[v]=FASLE;for(v=0;v<G.vexnum;++v)if(!visited[v])

DFS(G,v);//深度优先遍历}一、深度优先搜索7.3图的遍历数据结构-图详述全文共104页，当前为第45页。voidDFS(GraphG,intv)//从第v个顶点出发递归地深度优先遍历图G{visited[v]=TRUE；

VisitFunc(v)；//访问第v个顶点

For(w=FirstAdjvex(G,v)；w；w=NextAdjVex(G，v，w))If(!visited[w])//对v的尚未访问的邻接点w递归调用DFSDFS(G，w)；

}

一、深度优先搜索7.3图的遍历数据结构-图详述全文共104页，当前为第46页。一、深度优先搜索7.3图的遍历深度优先遍历后，产生的子图是一个以出发点为根的深度优先生成树。

见图数据结构-图详述全文共104页，当前为第47页。

广度优先搜索(BreadthFirstSearch)遍历类似于树的按层次遍历。算法基本思想(1)首先访问图中某一个指定的出发点vi；(2)然后依次访问vi的所有邻接点vi1,vi2…vit；(3)再依次以vi1,vi2…vit为顶点，访问各顶点未被访问的邻接点，依此类推，直到图中所有顶点均被访问为止。

二、广度优先搜索7.3图的遍历数据结构-图详述全文共104页，当前为第48页。2．广度优先搜索的例子QFFFFFFFFFVisit[v]012345678出发点TV1V1TV2TV6V2TV3V7TV6TTV5V3TTV4V8V7TTTV9V4V5V8V97.3图的遍历

二、广度优先搜索数据结构-图详述全文共104页，当前为第49页。(1)首先访问出发点v1;(2)然后访问v1的两个邻接点v2,v6;(3)以v2为顶点，访问v2未被访问的两个邻接点v3，v7；(4)以v6为顶点，访问v6未被访问的邻接点v5；(5)以v3为顶点，访问v3未被访问的两个邻接点v4,v8；(6)以v7为顶点，访问v7未被访问的邻接点v9，至此图中所有顶点均被访问。得到了广度优先搜索遍历的顶点序列（BFS序列）：

v1→v2→v6→v3→v7→v5→v4→v8→v97.3图的遍历

二、广度优先搜索数据结构-图详述全文共104页，当前为第50页。3．广度优先搜索算法voidBFSTraverse(GraphG，Status(*Visit)(intv))//按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。{for(v=0;v<G.vexnum；++v)visited[v]=FALSE；

InitQueue(Q)；//置空的辅助队列Qfor(v=0；v<G.vexnum；++v)if(!visited[v])//v尚未访问

{visitd[v]=TRUE;visit(v);EnQueue(Q,v)；//访问v并入队

while(!QueueEmpty(Q))//当堆栈非空

{DeQueue(Q,u)；//队头元素出队，并用u返回

for(w=FirstAdjVex(G,u)；w；w=NextAdjVex(G,u,w))if(!visited[w])//访问u尚未访问的邻接点并入队

{visited[w]=TRUE；Visit(w);//访问wEnQueue(Q,w)；}//w入队列Q}}}见图

二、广度优先搜索7.3图的遍历数据结构-图详述全文共104页，当前为第51页。7.4图的连通性问题本节是关于图的连通性问题。主要介绍:无向图生成树,以及最小生成树问题。利用遍历图的算法是求解图的连通性问题的关键。

一、无向图的连通分量和生成树二、最小生成树

数据结构-图详述全文共104页，当前为第52页。

一、无向图的连通分量和生成树7.4图的连通性问题1.连通图的生成树

一个连通图从任一顶点遍历后，其所有边集E(G)可以分为两个集合T(G)和B(G)，T(G)是遍历图过程中历经的边的集合；B(G)是剩余的边的集合。T(G)和G中所有顶点一起构成连通图G的极小连通子图即生成树。

可以从动态方面理解生成树：由遍历连通图G时所经过的边和顶点构成的子图是G的生成树。数据结构-图详述全文共104页，当前为第53页。

一、无向图的连通分量和生成树右图是由深度优先搜索得到的深度优先搜索生成树：B(G)T(G)返回7.4图的连通性问题数据结构-图详述全文共104页，当前为第54页。右图是由广度优先搜索得到的是广度优先搜索生成树：B(G)T(G)

一、无向图的连通分量和生成树7.4图的连通性问题数据结构-图详述全文共104页，当前为第55页。2．连通图生成树的算法：(生成的树采用左孩子右兄弟存储结构)voidDFSTree(GraphG，intv，CSTree&T)//从第v个顶点出发深度优先遍历图G，建立以T为根的生成树。

{visited[v]=TRUE；first=TRUE；

for(w=FirstAdjVex(G，v)；w>=0；w=NextAdjVex(G，v，w))if(!Visited[w]){p=(CSTree)malloc(sizeof(CSNode))；//分配孩子结点*p={GetVex(G，w)，NULL，NULL}；

if(first){T->lchild=p；first=FALSE；}//是根的左孩子结点

elseq->nextsibling=p；

//是上一邻接顶点的右兄弟结点

q=p；

DFSTree(G,w,q)；//从第w个顶点出发深度优先遍历图G}//建立子生成树q}

一、无向图的连通分量和生成树7.4图的连通性问题数据结构-图详述全文共104页，当前为第56页。1.最小生成树的定义(1)连通图代价若要在n个顶点之间建立连通图，至少要有n-1条边来连接这n个顶点，将这n-1条边上的权值之和定义为连通图的代价。

二、最小生成树7.4图的连通性问题数据结构-图详述全文共104页，当前为第57页。

二、最小生成树(2)最小生成树(MinimumCostSpanningTree--MST)

对于一个无向网N=(V,E)，其顶点个数为|V|=n，图中边的个数为|E|，可以从它的|E|条边中选出n-1条边，使之满足：

a.n-1条边和图的n个顶点构成一个连通图(生成树)。

b.该连通图的代价是所有满足条件a.的连通图的代价的最小值。这样的连通图被称为网络N的最小生成树。即所谓的代价和最小的生成树。

7.4图的连通性问题数据结构-图详述全文共104页，当前为第58页。2．最小生成树的性质（MST性质）假设图N=(V,E)是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边,其中u∈U，v∈V-U，则必存在一棵包含边(u,v)的最小生成树。两个利用MST性质求得最小生成树的算法：

普里姆(Prim)算法克鲁斯卡尔(Kruskal)算法

二、最小生成树7.4图的连通性问题数据结构-图详述全文共104页，当前为第59页。2．普里姆(Prim)算法(1)算法的思想设N=(V,E)是连通网，TE是N上最小生成树中边的集合。a.算法开始时，U={u0|u0∈V}(选一个初始顶点)，TE={}；b.找到满足weight(u0,v0)=min{weight(u,v)|u∈U，v∈V-U}的边(u0,v0)，把它并入集合TE中，同时v0并入U。c.反复执行b，直到U=V时终止算法。普里姆算法的时间复杂度为O(n2)，用于边稠密的图。

二、最小生成树7.4图的连通性问题数据结构-图详述全文共104页，当前为第60页。

二、最小生成树7.4图的连通性问题数据结构-图详述全文共104页，当前为第61页。

假设用邻接矩阵存储图。另设一个结构数组closedge，

closedge[i].adjvex存放已在U中且与vi相邻的顶点vk;closedge[i].Lowcost存放(vi,vk)边上的权值。若closedge[i].Lowcost=0表示vi在U中，

closedge[i].Lowcost=∞表示vi与vk间无边。算法中每次从lowcost中选取权值大于0且最小的边，把该边中属于V-U的顶点vk加入到U中，然后考察vk与其余属于V-U的顶点vj有边的权值是否比原closedge[j].Lowcost小，若小则修改closedge[j].Lowcost

。

二、最小生成树7.4图的连通性问题数据结构-图详述全文共104页，当前为第62页。

二、最小生成树23456UV-Ukadjvexlowcostv16v11v15

∞∞{v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6adjvexlowcostv350v62v360{v1,v3,v6}{v2,v4,V5}4adjvexlowcostv3500v360{v1,v3,,v4,v6}{v2,V5}2adjvexlowcost000v360{v1,v2,v3,v4,v6}{V5}5adjvexlowcost00000{v1,v2,v3,v4,v5,v6}closedge7.4图的连通性问题i数据结构-图详述全文共104页，当前为第63页。

二、最小生成树7.4图的连通性问题普里姆算法：VoidMinispanTree_prim(MgraphG,VertexTypeu){//用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边//辅助数组定义：

struct{vertexTypeadjvex;VRTypelowcost;}closedge[MAX_VERTEX_NUM];

数据结构-图详述全文共104页，当前为第64页。

二、最小生成树7.4图的连通性问题k=LocateVex(G,u);//设图的存储结构采用邻接矩阵表示

for(j=0;j<G.vexnum;++j)//辅助数组初始化

if(j!=k)closedge[j]={u,G.arcs[k][j].adj};closedge[k].lowcost=0;For(i=1;i<G.vexnum;++i){k=minmum(closedge);//求下一个kPrintf(closedge[k].adjvex,G.vexs[k]);Closedge[k].lowcost=0;//k顶点并入U集

For(j=0;j<G.vexnum;++j)//新顶点并入U后重选最小边

if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j]}}数据结构-图详述全文共104页，当前为第65页。练习题：用Prim算法求下图的最小代价生成树。数据结构-图详述全文共104页，当前为第66页。答案数据结构-图详述全文共104页，当前为第67页。2．克鲁斯卡尔(Kruskal)算法求最小生成树的另一种方法。算法的基本思想设连通网N={V，E}，T为N的最小生成树。初始时，T={V，{}}，即T中没有边，只有n个顶点，理所当然，这n个顶点就是n个连通分量。

(1)在E中选择权值最小的边，并将此边从E中删除。

(2)如果此边的两个顶点在T的不同连通分量中，则将此边加入到T的边集中，从而导致T中减少一个连通分量，重复执行(1)、(2)；如果此边的两个顶点在T的同一个连通分量中，则也重复执行(1)、(2)，直至T中仅剩一个连通分量时，终止操作。克鲁斯卡尔算法的时间复杂度为O(eloge),适合边稀疏的图。

二、最小生成树7.4图的连通性问题数据结构-图详述全文共104页，当前为第68页。

二、最小生成树7.4图的连通性问题数据结构-图详述全文共104页，当前为第69页。7.5

有向无环图及其应用一、有向无环图二、拓扑排序三、关键路径数据结构-图详述全文共104页，当前为第70页。一、有向无环图7.5

有向无环图及其应用

有向无环图(directedacyclinegraph)，简称DAG图，是一个无环的有向图。(1)在编译原理中，进行语义分析时，有向无环图是描述含有公共子式表达式的有效工具。(2)有向无环图也是描述一项工程或系统的进行过程的有效工具。在描述一项工程时，图的顶点被描述为子工程，称为“活动”。

数据结构-图详述全文共104页，当前为第71页。二、拓扑排序1.拓扑排序问题的提出通常，一个任务(工程)总可以分成若干个子任务，欲完成整个任务，只需完成所有子任务。而一些子任务常必须先于另外一些子任务被完成。也就是若想完成一个子任务必须看其先决务件是否被满足，这些先决条件即某些(其他的)子任务已经被完成。因此，先决条件定义了各任务之间的先后关系，这种关系可以用一个表示偏序的有向图来表示。如一个施工流程图，一个产品生产流程图或是一个数据流图，学生学习的进程图等。7.5

有向无环图及其应用数据结构-图详述全文共104页，当前为第72页。2.AOV网(ActivityOnVertexNetwork)

用顶点表示活动，用弧表示活动间的优先关系的有向图称AOV网(点表示活动的网）。7.5

有向无环图及其应用二、拓扑排序数据结构-图详述全文共104页，当前为第73页。3.拓扑排序的定义

(1)定义所谓拓扑序列，就是把AOV网中的所有顶点排成一个线性序列，该序列满足如下条件：若AOV网中存在弧<vi,vj>，则在该序列中，vi必位于vj之前。构造AOV网的拓扑序列的操作被称为拓扑排序。

(2)特点a.一个有向图的拓扑序列不唯一。b.有向无环图一定存在拓扑序列。反之通过构造拓扑序列，来判定AOV是否存在环。7.5

有向无环图及其应用二、拓扑排序数据结构-图详述全文共104页，当前为第74页。4.拓扑排序的算法(1)基本思想a.在有向图中选一个入度为0的顶点且输出之。b.从图中删除该顶点及所有以它为尾的弧。c.重复执行a和b，直到全部顶点均已输出，或图中剩余顶点的入度均不为0(说明图中存在回路，无法继续拓扑排序)。7.5

有向无环图及其应用二、拓扑排序数据结构-图详述全文共104页，当前为第75页。(2)示例拓扑序列：v0-v3-v2-v4-v17.5

有向无环图及其应用二、拓扑排序数据结构-图详述全文共104页，当前为第76页。(3)算法a.采用邻接表作有向图的存储结构，且在头结点增加一个存放顶点入度的数组(indegree)。b.删除顶点及以它为尾的弧的操作，则可换以弧头顶点的入度减1来实现。c.设一栈暂存所有入度为0的顶点。7.5

有向无环图及其应用二、拓扑排序数据结构-图详述全文共104页，当前为第77页。7.5

有向无环图及其应用二、拓扑排序Statustopologicalsort(algraphG){findindegree(G,indegree);//求各顶点的入度indegree[0…vernum-1]initstack(s);

for(i=0;i<G.vexnum;++i)//入度为0的顶点入栈

if(!indegree[i])push(s,i);count=0;while(!stackempty(s)){pop(s,i);printf(i.vextices[i].data);++count;//对输出顶点计数

for(p=G.vextices[i].firstarc;p;p=p->nextarc)//对邻接点的入度减1{k=p->adjvex;//为0入栈，相当于删

if(!(--indegree[k]))push(s,k);}//除顶点的弧

}if(count<G.vexnum)returnERROR;elsereturnOK;}数据结构-图详述全文共104页，当前为第78页。1．AOE网(边表示活动的网)

在AOV网中，有向图的顶点表示一项任务，有向边表示任务之间的先后关系。在实际应用中，任务之间除了先后关系外，还有时间上的约束,用AOE(ActivityOnEdgenetwork)网来表示这种约束关系。

AOE网是一个带权的有向无环图,

7.5

有向无环图及其应用三、关键路径对AOE网研究的问题是：完成整项工程至少需要多少时间？(2)那些活动是影响工程进度的关键？数据结构-图详述全文共104页，当前为第79页。其中:顶点表示事件(Event)，表明它的入边的活动已经完成，它的出边活动可以开始的一种状态，弧表示活动，权表示活动持续的时间。通常将入度为零的点称作源点；出度为零的点叫汇点。利用AOE网来估算工程的完成时间。整个工程只有一个开始点和一个完成点，7.5

有向无环图及其应用三、关键路径数据结构-图详述全文共104页，当前为第80页。7.5

有向无环图及其应用三、关键路径

图1一个AOE网数据结构-图详述全文共104页，当前为第81页。V1V2V3V4V5V6V7V8v9^v51^v34v45^v24v51^v62^v87^v79v84^v92^v94^图1的邻接表存储结构7.5

有向无环图及其应用三、关键路径数据结构-图详述全文共104页，当前为第82页。(1)关键路径因为在AOE网中，有些活动可以同时进行，所以完成一个工程所需的最短时间是从一个源点到一个汇点的最大路径长度。具有最大长度的路径被称为关键路径。

这里路径长度是指路径上的各边权值之和。

关键路径上的活动都是关键活动。

7.5

有向无环图及其应用三、关键路径2.关键路径数据结构-图详述全文共104页，当前为第83页。三、关键路径(2)事件的最早发生时间和最晚发生时间设事件的最早发生时间ve[k],假设开始点v1，设ve[1]=0，按拓扑序列求其余各顶点事件vk的最早发生时间ve[k]:

ve[k]=max{ve[j]+wight(j,k)}

，其中jT，T是以vk为终顶点的所有弧的始顶点集合。设事件的最晚发生时间vl[k]，设汇点的vl[n]=ve[n],按逆拓扑序列求其余各点事件的最晚发生时间vl[j]:

vl(j)=min{vl(k)-weight(<j,k>)}，其中kS,S是以vj为始顶点的所有弧的终顶点的集合。7.5

有向无环图及其应用见图1数据结构-图详述全文共104页，当前为第84页。(3)活动的最早开始时间和最迟开始时间若设e[i]为ai的最早开始时间，设ve[j]为vj的最早发生时间，事件vj是活动ai的弧尾。则有：

e[i]=ve[j]

若设l[i]为活动ai的最迟开始时间，l[i]等于终顶点vk事件的最晚发生时间减去该活动持续的时间，即：

l[i]=vl[k]-weight(<j,k>)

7.5

有向无环图及其应用三、关键路径见图1数据结构-图详述全文共104页，当前为第85页。(4)关键活动若l(i)-e(i)>0，则两者之差为完成活动ai的时间余量。若l(i)=e(i)，则称ai为关键活动。之所以称其为关键活动，是因为完成该活动的时间的增加或缩短将影响整个工程的时间进度。

ve(1)=0ve(j)=max{ve(i)+weight(<i,j>)}

vl[n]=ve[n]

vl(j)=min{vl(k)-weight(<j,k>)}e[i]=ve[j]

l[i]=vl[k]-weight(<j,k>)7.5

有向无环图及其应用三、关键路径数据结构-图详述全文共104页，当前为第86页。(5)求ve(j)和vl(j)的方法

a.从源点v1开始，自左向右对每个事件进行计算，其顺序是顶点的某个拓扑序列。

ve(1)=0ve(j)=max{ve(i)+weight(<i,j>)|<i,j>E,j=1,2…n}i

由此递归公式可以依次得到所有事件的最早发生时间，最后计算出的是整个工程的最早发生时间ve(n)。

7.5

有向无环图及其应用三、关键路径数据结构-图详述全文共104页，当前为第87页。b.vl(j)的计算从汇点vn开始，自右向左逐个事件逆推计算，直到计算至源点v1为止。其计算顺序是拓扑序列的逆序。对于vn，其vl(n)=ve(n)

计算vl(j)的递归公式：

vl(n)=ve(n)vl(j)=min{vl(k)-weight(<j,k>)|<j,k>E,j=n-1,…1}k7.5

有向无环图及其应用三、关键路径数据结构-图详述全文共104页，当前为第88页。v1v2v3v4v5v6v7v8v97.5

有向无环图及其应用三、关键路径ve0

6457716

14

18vl0

66871016

14

18a1a2a3a4a5a6a7a8a9a10a11e0006457

7716

14l0236687

71016

14数据结构-图详述全文共104页，当前为第89页。(6)求关键路径的算法思想：a.输入若干条弧<j,k>，建立AOE网的存储结构(采用邻接表)；b.从源点v1(v0)出发，令ve[1]=0,按拓扑有序求其余各顶点的最早发生时间ve[i](2≤i≤n)。若网中有回路，则终止算法；c.从汇点vn出发，令vl[n]=ve[n]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i](n-1≥i≥1)；d.根据ve和vl的值，求出各活动ai的最早开始时间e(i)和最迟开始时间l(i),若e(i)=l(i)，则ai是关键活动。7.5

有向无环图及其应用三、关键路径数据结构-图详述全文共104页，当前为第90页。算法：

StatusTopologicalOrder(ALGraphG,Stack&T){FindInDegree(G,indegree)

建零入度顶点栈S；

InitaStack(T);count=0;ve[0..G.vexnum-1]=0;//初始化

vhile(!StackEmpty(S)){Pop(S,j);Push(T,j);++count;//j号顶点入T栈并计数

for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;//对j号顶点的每个邻接点入度减1if(--indegree[k]==0)Push(S,k);//入度减为0，则入栈

if(ve[j]+*(p->info)>ve[k])ve[k]=ve[j]+*(p->info);}}if(count<G.vexnum)returnERROR;//该有向网有回路

elsereturnOK;}

7.5

有向无环图及其应用三、关键路径数据结构-图详述全文共104页，当前为第91页。

7.5

有向无环图及其应用三、关键路径//G为有向网，输出G的关键活动StatusCriticalPath(ALGraphG){if(!TopologicalOrder(G,T))returnERROR;vl[0..G.vexnum-1]=ve[G.vexnum-1];//初始化顶点的最迟发生时间

while(!StackEmpty(T))//拓朴逆序求各顶点的vl值

for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=*(p->info);if(vl[k]-dut<vl[j])vl[j]=vl[k]-dut;}

见82v1v4v6v3v2v5v8v7v9数据结构-图详述全文共104页，当前为第92页。//求诸活动的最早开始时间ee和最迟开始时间el和关键活动

for(j=0;j<G.vexnum;++j)for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=*(p->info);ee=ve[j];el=vl[k]-dut;tag=(ee==el)?’*’:’

’;printf(j,k,dut,ee,el,tag);//输出关键活动

}}7.5

有向无环图及其应用三、关键路径数据结构-图详述全文共104页，当前为第93页。7.6最短路径一、问题的提出二、从某个源点到其余各顶点的最短路径三、每一对顶点之间的最短路径数据结构-图详述全文共104页，当前为第94页。一、问题的提出7.6

最短路径

在实际生活中，如某人要从A城到B城，他需要选择线路，这是一类最简单的最短路径问题：通常我们需要考虑一些代价问题，比如：花费的时间、费用，这时路径长度的度量不是边数多少的问题，我们需要的是“代价”最小路径。这就是我们所有讨论最短路径问题。

“代价”是指从某个始点到其余顶点路径权值之和。最短路径是指权值之和最小的路径。数据结构-图详述全文共104页，当前为第95页。二、从某个源点到其余各顶点的最短路径又称单源最短路径。1．源点：路径上的第一个顶点，起始点。2．终点：最后一个顶点。3．单源最短路径：给定有向图G和