数据结构第七章图

数据结构第七章图7.1图的定义和基本术语

7.2图的存储结构数组表示法

邻接表

十字链表

邻接多重表

7.3图的遍历

7.3.1深度优先搜索

7.3.2广度优先搜索

7.4图的连通性问题

7.4.1无向图的连通分量和生成树

7.4.2最小生成树

7.5有向无环图及其应用

.2

7.6最短路径

7.6.1从某个源点到其余各顶点的最短路径

7.6.2每一对顶点间的最短路径

在日常生活中，常用图来表示一些问题或概念，如IC设计、城市间交通道路规划、作业调度等。图和树一样，也是一种非线性数据结构。图和树的最大差异在于：树描述的是数据元素(结点)之间的层次关系，每一层上的数据元素可能和下一层中多个元素(即孩子结点)相关，但只能和上一层中一个元素相关，而图结构研究两顶点之间是否相连的关系，在图中，结点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。图结构提供了简单的方式来描述一个问题、系统或状况等。7.1图的定义和基本术语

图是由一个顶点集V和一个弧集VR构成的数据结构。

Graph=(V,VR)其中，VR＝{<v,w>|v,w∈V且P(v,w)}<v,w>表示从v到w的一条弧，并称v为弧尾，w为弧头。谓词P(v,w)定义了弧<v,w>的意义或信息。图的结构定义:

由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。

ABECD例如:G1=(V1,VR1)其中V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}若<v,w>VR

必有<w,v>VR,则称(v,w)为顶点v和顶点w之间存在一条边。

BCADFE由顶点集和边集构成的图称作无向图。例如:G2=(V2,VR2)V2={A,B,C,D,E,F}VR2={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}名词和术语网、子图

完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林ABECFAEFBBC设图G=(V,{VR})和图G=(V,{VR}),且VV,VRVR,则称G为G的子图。1597211132

弧或边带权的图分别称作有向网或无向网。假设图中有n

个顶点，e

条边，则

含有e=n(n-1)/2条边的无向图称作完全图；

含有e=n(n-1)条弧的有向图称作有向完全图；

若边或弧的个数e<nlogn，则称作稀疏图，否则称作稠密图。

假若顶点v和顶点w之间存在一条边，则称顶点v

和w

互为邻接点，ACDFE例如:TD(B)=3TD(A)=2

边(v,w)和顶点v和w

相关联。和顶点v关联的边的数目定义为点V的度。B顶点的出度:以顶点v为弧尾的弧的数目；ABECF对有向图来说，顶点的入度:以顶点v为弧头的弧的数目。顶点的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3设图G=(V,{VR})中的一个顶点序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)VR1≤j≤m,则称从顶点u到顶点w之间存在一条路径。路径上边的数目称作路径长度。ABECF如:长度为3的路径{A,B,C,F}简单路径:序列中顶点不重复出现的路径。简单回路:序列中第一个顶点和最后一个顶点相同的路径。若图G中任意两个顶点之间都有路径相通，则称此图为连通图；若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。BACDFEBACDFE

若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。ABECFABECF对有向图，否则，其各个强连通子图称作它的强连通分量。对于下图a中的非强连通图，它的强连通分量见图b。

635421

假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。BACDFE结构的建立和销毁插入或删除顶点对邻接点的操作对顶点的访问操作遍历插入和删除弧基本操作CreatGraph(&G,V,VR)://按定义(V,VR)构造图DestroyGraph(&G)://销毁图结构的建立和销毁对顶点的访问操作LocateVex(G,u);

//若G中存在顶点u，则返回该顶点在

//图中“位置”

；否则返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//对v赋值value。对邻接点的操作FirstAdjVex(G,v);

//返回v的“第一个邻接点”。若该顶点//在G中没有邻接点，则返回“空”。NextAdjVex(G,v,w);

//返回v的（相对于w的）“下一个邻接//点”。若w是v的最后一个邻接点，则//返回“空”。插入或删除顶点InsertVex(&G,v);

//在图G中增添新顶点v。DeleteVex(&G,v);//删除G中顶点v及其相关的弧。插入和删除弧InsertArc(&G,v,w);//在G中增添弧<v,w>，若G是无向的，

//则还增添对称弧<w,v>。DeleteArc(&G,v,w);

//在G中删除弧<v,w>，若G是无向的，

//则还删除对称弧<w,v>。遍历DFSTraverse(G,v,Visit());//从顶点v起深度优先遍历图G，并对每//个顶点调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit());

//从顶点v起广度优先遍历图G，并对每//个顶点调用函数Visit一次且仅一次。

图是一种结构复杂的数据结构，表现在不仅各个顶点的度可以千差万别，而且顶点之间的逻辑关系也错综复杂，因此图在计算机中的存储方式有多种。一个图的信息包括两部分，图中顶点的信息以及描述顶点之间的关系--边或者弧的信息。因此无论采用什么方法建立图的存储结构，都要完整、准确地反映这两方面的信息。四种最常用的方法：邻接矩阵、邻接表、十字链表、邻接多重表。对于具体的图来说，最好的存储结构不仅依赖于数据的性质，而且还与在这些数据上进行的操作有关。对于实际问题，需要根据具体的图结构本身的特点以及所要实施的操作选择建立合适的存储结构。7.2图的存储结构7.2图的存储结构7.2.1数组表示法7.2.2邻接表7.2.3十字链表7.2.4邻接多重表邻接矩阵是表示顶点之间相邻关系的矩阵。所谓两顶点的相邻关系即它们之间有边相连。邻接矩阵是一个（n×n）阶方阵，n为图的顶点数，它的每一行分别对应图的各个顶点，它的每一列也分别对应图的各个顶点。我们规定矩阵的元素为：7.2.1数组表示法(邻接矩阵)A[i][j]={0(i,j)VR1(i,j)VR1、无向图的邻接矩阵2、有向图的邻接矩阵3、从无向图的邻接矩阵可以得出如下结论（1）矩阵是对称的;（2）第i行或第i列1的个数为顶点i的度;（3）矩阵中1的个数的一半为图中边的数目;（4）很容易判断顶点i和顶点j之间是否有边相连(看矩阵中i行j列值是否为1)。4、从有向图的邻接矩阵可以得出如下结论（1）矩阵不一定是对称的;（2）第i行中1的个数为顶点i的出度;（3）第i列中1的个数为顶点i的入度;（4）矩阵中1的个数为图中弧的数目;（5）很容易判断顶点i和顶点j是否有弧相连。5、网的邻接矩阵表示类似地可以定义网的邻接矩阵为：

wij

若（i,j）∈E(G)或〈i,j〉∈E(G)A[i][j]=∞其它情形网及网的邻接矩阵见图b。typedefstructArcCell{//弧的定义

VRTypeadj;//VRType是顶点关系类型。

//对无权图，用1或0表示相邻否；

//对带权图，则为权值类型。

InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];6、图的邻接矩阵数据类型描述#defineINFINITYINT_MAX//最大值无穷大#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{DG,DN,UDG,UDN}GraphKind;//有向图，有向网，无向图，无向网typedefstruct{//图的定义

VertexType//顶点信息

vexs[MAX_VERTEX_NUM];AdjMatrixarcs;//弧的信息

intvexnum,arcnum;//顶点数，弧数

GraphKindkind;//图的种类标志

}MGraph;StatusCreateGraph（MGraph&G）{//采用数组（邻接矩阵）表示法，构造图Gscanf(&G.kind);switch（G.kind）{caseDG:returnCreateDG(G);//构造有向图GcaseDN:returnCreateDN(G);//构造有向网GcaseUDG:returnCreateUDG(G);//构造无向图GcaseUDN:returnCreateUDN(G);//构造无向网Gdefault：returnERROR;}}//CreateGraph产生图邻接矩阵算法建立一个无向网的邻接矩阵存储的算法如下：StatusCreateUDN（MGraph&G）{//采用数组（邻接矩阵）表示法，构造无向网Gscanf(&G.vexnum，&G.arcnum，&IncInfo);//IncInfo为0则各弧不含其他信息for（i=0；i<G.vexnum；++i）scanf(&G.vexs[i]);for（i=0；i<G.vexnum；++i）//初始化邻接矩阵for（j=0；j<G.vexnum；++j）G.arcs[i][j]={INFINITY，NULL};for（k=0；i<G.arcnum；++k）{//构造邻接矩阵

scanf(&v1，&v2，&w)；//输入一条边依附的顶点及权值

i=LocateVex（G,v1）;j=LocateVex（G,v2）;G．arcs[i][j].adj=w;//弧〈v1，v2〉的权值

if(IncInfo)Input(*G.arcs[i][j].info);G．arcs[j][i]=G．arcs[i][j]}returnOK;}//CreateUDN建立有向图G的邻接矩阵存储

voidCreateDG(MGraph*G){/*建立有向图G的邻接矩阵存储*/inti,j,k,w;charch;printf("请输入顶点数和边数(输入格式为:顶点数,边数):\n");scanf("%d,%d",&G.vexnum，&G.arcnum);/*输入顶点数和边数*/printf("请输入顶点信息(输入格式为:顶点号<CR>):\n");for(i=0;i<G.vexnum;i++)scanf("\n%c",&G.vexs[i]);/*输入顶点信息，建立顶点表*/for(i=0;i<G.vexnum;i++) for(j=0;j<G.vexnum;j++)G.arcs[i][j]=0;/*初始化邻接矩阵*/printf("请输入每条边对应的两个顶点的序号(输入格式为:i,j):\n");for(k=0;k<G.arcnum.;k++) {scanf("\n%d,%d",&i,&j);/*输入e条边，建立邻接矩阵*/ G.arcs[i][j]=1;/*若加入G.arcs[[j][i]=1;，*//*则为无向图的邻接矩阵存储建立*/}}/*CreateDG*/7.2.2邻接表1、图的邻接表表示邻接表(AdjacencyList)是图的一种顺序存储与链式存储相结合的存储结构。将每个结点的边用一个单链表链接起来，若干个结点可以得到若干个单链表，每个单链表都有一个头结点，所有头结点组成一个一维数组，称这样的链表为邻接表。0A141B0452C353D254E015F123BACDFE无向图的邻接表142301201234ABCDE有向图的邻接表ABECF可见，在有向图的邻接表中不易找到指向该顶点的弧。ABECD有向图的逆邻接表ABCDE30342001234在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧。2、从无向图的邻接表可以得到如下结论（1）第i个链表中结点数目为顶点i的度；（2）所有链表中结点数目的一半为图中边数；（3）占用的存储单元数目为n+2e。3、从有向图的邻接表可以得到如下结论（1）第i个链表中结点数目为顶点i的出度；（2）所有链表中结点数目为图中弧数；（3）占用的存储单元数目为n+e。typedefstructArcNode{

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

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

InfoType*info;//该弧相关信息的指针}ArcNode;adjvexnextarcinfo弧的结点结构4、图的邻接表数据类型描述typedefstructVNode{VertexTypedata;//顶点信息

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

}VNode,AdjList[MAX_VERTEX_NUM];datafirstarc顶点的结点结构typedefstruct{AdjListvertices;

intvexnum,arcnum;

intkind;//图的种类标志

}ALGraph;图的结构定义

建立一个有向图的邻接表存储的算法如下：

voidCreateALGraph(ALGraphG){//建立有向图的邻接表存储

arcNode*s;scanf(“%d,%d”,&G.vexnum,&G.arcnum);//读入顶点数和边数

for(i=0;i<G.vexnum;i++)//建立有n个顶点的顶点表

{scanf(“\n%c”,&G.vertices[i].data);//读入顶点信息

G.vertices[i].firstarc=NULL;//顶点的边表头指针设为空}for(k=0;k<G.arcnum;k++)//建立边表

{scanf("\n%d,%d",&i,&j);//读入边<Vi,Vj>的顶点对应序号

s=(arcNode*)malloc(sizeof(arcNode));s.adjvex=j;//邻接点序号为j s.nextarc=G.vertices[i].firstarc;/*将新边表结点s插入到顶点Vi的边表头部*/ G.vertices[i].firstarc=s;}}/*CreateALGraph*/十字链表(OrthogonalList)是有向图的另一种链式存储结构。实际上它是将有向图的邻接表和逆邻接表结合在一起，得到的一种链表。在十字链表中，对应于有向图中的每一条弧有一个结点，对应于每个顶点也有一个结点。这些结点的结构如下图所示。7.2.3十字链表头域(headvex)：存放该弧的弧头顶点在图中的位置；尾域(tailvex)：存放该弧的弧尾顶点在图中的位置；链域hlink：指向与该弧具有相同弧头的下一条弧的边结点；链域tlink：指向与该弧具有相同弧尾的下一条弧的边结点；info域指向该弧的相关信息(如权值)。图中弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。头结点即为顶点结点，它由三个域组成：data域：存放与顶点有关的信息(如顶点的名称等)；firstin域：存放以该顶点为弧头的单链表的头指针；firstout域：存放以该结点为弧尾的单链表的头指针。弧的结点结构弧尾顶点位置弧头顶点位置弧的相关信息指向下一个有相同弧头的结点指向下一个有相同弧尾的结点typedefstructArcBox{//弧的结构表示

inttailvex,headvex;InfoType*info;structArcBox*hlink,*tlink;

}ArcBox;顶点的结点结构顶点信息数据指向该顶点的第一条入弧指向该顶点的第一条出弧typedefstructVexNode{//顶点的结构表示

VertexTypedata;ArcBox*firstin,*firstout;}VexNode;typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//顶点结点(表头向量)

intvexnum,arcnum;//有向图的当前顶点数和弧数}OLGraph;有向图的结构表示(十字链表)只要输入n个顶点的信息和e条弧的信息，便可建立该有向图的十字链表，其算法内容如下。

statusCreateDG(OLGraph&G)/*采用十字链表表示，构造有向图G(G.kind=DG)*/{scanf(&G.vexnum,&G.arcnum,&IncInfo);//IncInfo为0则各弧不含其实信息

for(i=0;i<G.vexnum;++i)//构造表头向量

{scanf(&G.xlist[i].data);//输入顶点值

G.xlist[i].firstin=NulL;G.xlist[i].firstout=NULL;}

for(k=0;k<G.arcnum;++k)//输入各弧并构造十字链表*/{scanf(&v1,&v2);/*输入一条弧的始点和终点*/i=LocateVex(G,v1);j=LocateVex(G,v2);p=(ArcBox*)malloc(sizeof(ArcBox));*p={i,j,G.xlist[j].fistin,G.xlist[i].firstout,NULL}//对弧结点赋值{tailvex,headvex,hlink,tlink,info}

G.xlist[j].fisrtin=G.xlist[i].firstout=p;//完成在入弧和出弧链头的插入

if(IncInfo)Input(*);//若弧含有相关信息，则输入

}}/*CreateDG*/

邻接多重表是存储无向图的另一种链式存储方法。虽然邻接表是无向图的一种很有效的存储结构，在邻接表中容易求得顶点和边的各种信息，但是，在邻接表中每一条边(Vi，Vj)有两个结点，分别在第i个和第j个链表中，这就给某些图的操作带来不便。例如在某些图的应用问题中需要对边进行某种操作，如删除一条边等，这时需要两次扫描邻接表，找到表示同一条边的两个边结点并进行删除，显然给操作带来不便。邻接多重表是对邻接表的一种改进，邻接多重表的结构与十字链表类似。在邻接多重表中，每一条边用一个结点表示，它由下图(a)所示的6个域组成，顶点结点(b)所示。7.2.4邻接多重表mark为标志域，用以保存标志该条边是否被搜索过；ivex和jvex保存该边依附的两个顶点在图中的位置；ilink保存指向下一条依附于顶点ivex的边；jlink保存指向下一条依附于顶点jvex的边；info保存指向和边相关的各种信息的指针域。每一个顶点可用一个结点表示，它由两个域组成。其中，data域存储和该顶点相关的信息，firstedge域保存指示第一条依附于该顶点的边。

在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边结点同时链接在两个链表中。可见对于无向图而言，其邻接多重表和邻接表的差别在于同一条边，在邻接表中用两个结点表示，而在邻接多重表中只用一个结点来表示。因此，除了在边结点中增加一个标志域外，邻接多重表的建立及其各种基本操作的实现和邻接表相似。typedefstructEbox{VisitIfmark;//访问标记

intivex,jvex;//该边依附的两个顶点的位置

structEBox*ilink,*jlink;InfoType*info;//该边信息指针}EBox;边的结构表示typedefstruct{//邻接多重表

VexBoxadjmulist[MAX_VERTEX_NUM];

intvexnum,edgenum;

}AMLGraph;顶点的结构表示typedefstructVexBox{VertexTypedata;EBox*firstedge;//指向第一条依附该顶点的边}VexBox;无向图的结构表示邻接矩阵：有向图和无向图

邻接表（逆邻接表）：有向图和无向图

十字链表：有向图

邻接多重表：无向图各种存储结构的适用类型7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第七章图7.3图的遍历

从图中某一个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次。这一过程就叫图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

但是，在图中有回路，从图中某一顶点出发访问图中其它顶点时，可能又会回到出发点，而图中可能还剩余有顶点没有访问到，因此，图的遍历较树的遍历更复杂。我们可以设置一个全局型标志数组visited[0..n-1]来标志某个顶点是否被访过，未访问的值为false，访问过的值为true7.3图的遍历深度优先搜索广度优先搜索根据搜索路径的方向不同，图的遍历有两种方法：V1V2V4V5V3V7V6V8例深度遍历：V1方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。7.3.1深度优先搜索

为了在遍历过程中便于区分顶点是否已被访问，需附设访问标志数组visited[0..n-1],，其初值为FALSE，一旦某个顶点被访问，则其相应的分量置为TRUE。

V2

V4

V8

V5

V3

V6

V7

V2

V4

V8

V2

V4

V5

V8

V2

V4

V3

V5

V8

V2

V4

V6

V3

V5

V8

V2

V4

V7

V6

V3

V5

V8

V2

V4例如，对下图所示无向图G7，从顶点1出发的深度优先搜索遍历序列可有多种，下面仅给出三种，其它可作类似分析。在无向图G7中，从顶点1出发的深度优先搜索遍历序列举三种为：1,2,4,8,5,6,3,71,2,5,8,4,7,3,61,3,6,8,7,4,2,5

首先将图中每个顶点的访问标志设为FALSE,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。非连通图的深度优先搜索遍历//---下列算法使用的全局变量---Booleanvisited[MAX];//访问标志数组Status(*VisitFunc)(intv);//函数变量voidDFSTraverse(GraphG,

Status(*Visit)(intv)){

//对图G作深度优先遍历。

VisitFunc=Visit;

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//访问标志数组初始化

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

if(!visited[v])DFS(G,v);//对尚未访问的顶点调用DFS}voidDFS(GraphG,intv){//从顶点v出发，深度优先搜索遍历连通图Gvisited[v]=TRUE;VisitFunc(v);

for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);//对v的尚未访问的邻接顶点w//递归调用DFS}//DFSabchdekfgFFFFFFFFFTTTTTTTTTachdkfebgachkfedbg访问标志:访问次序:例如:012345678分析上述算法，在遍历时，对图中每个顶点至多调用一次DFS函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当以邻接表作图的存储结构时，找邻接点所需时间为O(e)，其中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。

从刚才讲述的遍历结果可以看出，从某一个顶点出发的遍历结果是不唯一的。但是,若我们给定图的存储结构,则从某一顶点出发的遍历结果应是唯一的。(1)

用邻接矩阵实现图的深度优先搜索

以无向图G7为例，来说明算法的实现，G7的邻接矩阵见下图无向图G7，可以描述从顶点1出发的深度优先搜索遍历过程，示意图见下图，其中实线表示下一层递归调用，虚线表示递归调用的返回。从图G7中，可以得到从顶点1的遍历结果为1,2,4,8,5,6,3,7。同样可以分析出从其它顶点出发的遍历结果。(2)用邻接表实现图的深度优先搜索仍以无向图G7为例，来说明算法的实现，G7的邻接表见右图，可以描述从顶点7出发的深度优先搜索遍历示意图，见下页图,其中实线表示下一层递归，虚线表示递归返回，箭头旁边数字表示调用的步骤。于是，从顶点7出发的深度优先搜索遍历序列，从图G7中可得出为7，3，1，2，4，8，5，6。从其它顶点出发的深度优先搜索序列，请读者自已写出。图示见下一页V1V2V4V5V3V7V6V8例广度遍历：V1方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止7.3.2广度优先搜索

和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2、3、…的顶点，需附设队列以存储已被访问的路径长度为1、2、…

的顶点。

V7

V6

V3

V5

V8

V2

V4例如，对无向图G7，从顶点1出发的广度优先搜索遍历序列可有多种，下面仅给出三种，其它可作类似分析。

在无向图G7中，从顶点1出发的广度优先搜索遍历序列举三种为：

1,2,3,4,5,6,7,81,3,2,7,6,5,4,81,2,3,5,4,7,6,8动画演示

voidBFSTraverse(GraphG,

Status(*Visit)(intv)){

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//初始化访问标志

InitQueue(Q);//置空的辅助队列Q

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

if(!visited[v]){

//v尚未访问

}

}//BFSTraverse……

分析上述算法，每个顶点至多进一次队列。遍历图的过程实质是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。

visited[v]=TRUE;Visit(v);//访问uEnQueue(Q,v);//v入队列while(!QueueEmpty(Q)){DeQueue(Q,u);//队头元素出队并置为ufor(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))

if(!visited[w]){visited[w]=TRUE;Visit(w);EnQueue(Q,w);//访问的顶点w入队列

}//if}//while(1)用邻接矩阵实现图的广度优先搜索遍历仍以无向图G7及其的邻接矩阵来说明对无向图G7的遍历过程根据该算法用及图G7中的邻接矩阵，可以得到图G7的无向图G7的广度优先搜索序列，若从顶点1出发，广度优先搜索序列为：1，2，3，4，5，6，7，8。若从顶点3出发，广度优先搜索序列为：3，1，6，7，2，8，4，5,从其它点出发的广度优先搜索序列可根据同样类似方法分析。（2）用邻接表实现图的广序优先搜索遍历仍以无向图G7及其邻接表来说明邻接表上实现广度优先搜索遍历的过程根据该算法，可以得到图G7的广度优先搜索序列，若从顶点1出发，广度优先搜索序列为：1，2，3，4，5，6，7，8，若从顶点7出发，广度优先搜索序列为：7，3，8，1，6，4，5，2，从其它顶点出发的广度优先搜索序列可根据同样类似方法分析。7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第七章图7.4.1生成树1．生成树在图论中，常常将树定义为一个无回路连通图。例如，下图中的两个图就是无回路的连通图。乍一看它似乎不是不是树，但只要选定某个顶点做根并以树根为起点对每条边定向，就可以将它们变为通常的树。7.4生成树和最小生成树在一个连通图中，有n个顶点，若存在这样一个子图，含有n个顶点，n-1条不构成回路的边，则这个子图称为生成树，或者定义为：一个连通图G的子图如果是一棵包含G的所有顶点的树，则该子图称为图G的生成树。

由于n个顶点的连通图至少有n-1条边，而所有包含n-1条边及n个顶点的连通图都是无回路的树，所以生成树是连通图中的极小连通子图，所谓极小是指边数最少，若在生成树中去掉任何一条边，都会使之变为非连通图，若在生成树上任意增加一条边，就会构成回路。那么，对给定的连通图，如何求得它的生成树呢？回到我们前面提到的图的遍历，访问过图中一个顶点后，要访问下一个顶点，一般要求两个顶点有边相连，即必须经过图中的一条边，要遍历图中n个顶点且每个顶点都只遍历一次，则必须经过图中的n-1条边，这n-1条边构成连通图的一个极小连通子图，所以它是连通图的生成树，由于遍历结果可能不唯一，所以得到的生成树也是不唯一的。要求得生成树，可考虑用刚才讲过的深度优先搜索遍历算法及广度优先搜索遍历算法。对于深度优先搜索算法DFS，由DFS（i）递归到DFS（j），中间必经过一条边（i,j），因此，只需在DFS(j)调用前输出这条边或保存这条边，即可求得生成树的一条边，整个递归完成后，则可求得生成树的所有边。对于广度优先搜索算法BFS，若i出队，j入队，则(i,j)为一条树边。因此，可以在算法的if语句中输出这条边，算法完成后，将会输出n-1条边，也可求得生成树。由深度优先搜索遍历得到的生成树，称为深度优先生成树，由广度优先搜索遍历得到的生成树，称为广度优先生成树。无向图G7的两种生成树见下面的图。若一个图是强连通的有向图，同样可以得到它的生成树。生成树可以利用连通图的深度优先搜索遍历或连通图的广度优先搜索遍历算法得到。V1V2V4V5V3V7V6V8例深度遍历：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V82．生成森林

若一个图是非连通图或非强连通图，但有若干个连通分量或若干个强连通分量，则通过深度优先搜索遍历或广度优先搜索遍历，不可以得到生成树，但可以得到生成森林，且若非连通图有n个顶点，m个连通分量或强连通分量，则可以遍历得到m棵生成树，合起来为生成森林，森林中包含n-m条树边。生成森林可以利用非连通图的深度优先搜索遍历或非连通图的广度优先搜索遍历算法得到。例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林

对于网，因为它的边是带权的，而我们知道生成树是不唯一的，于是就产生了这样一个问题，如何找到一个各边的权数总和最小的生成树呢？探讨这个问题，对于实际生活有很大的意义。例如，假若要在几个城市之间建立一个通信联络网，则连通n个城市只需要n-1条线路，这时，自然会考虑这样一个问题，如何在最节省经费的情况下，建立这个通信网。在每两个城市之间都可以设置一条线路，相应地都要付出一些代价。

n个城市，如果任意两个城市之间均有线路，则最多可设置n(n-1)/2条线路，那么如何在这n(n-1)/2条线路中选择n-1条，使得总的耗费最低呢？7.4.3最小生成树

可以用连通网来表示n个城市以及n个城市之间的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网，可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在我们来选择这样一棵生成树，使总的费用最小。一棵生成树的代价就是树上各边的代价之和。于是，这个问题就是构造连通网的最小代价生成树(MinimumCostSpanningTree)，简称为最小生成树的问题。

构造最小生成树可以有多种算法，其中多数算法利用了最小生成树的一种简称MST的性质：假设N=(V，E)是一个连通网，U是顶点集V的一个非空子集。若(u，v)是一条具有最小权值(代价)的边，其中u∈U，v∈V-U，则必存在一棵包含边(u，v)的最小生成树。可以用反证法证明之。假设网N中的任何一棵最小生成树都不包含(u，v)。设T是连通网上的一棵最小生成树，当将边(u，v)加入到T中时，由生成树的定义，T中必存在一条包含(u，v)的回路。另一方面，由于T是生成树，则在T上存在另一条边(u'，v')，其中u'∈U，v'∈V-U，且u和u'之间、v和v'之间均有路径相通。删去边(u'，v')，便可以消除上述回路，同时得到另一棵生成树T'。因为(u，v)的权小于等于(u'，v')的权，故T'的权也不高于T的权，因此T'也是包含(u，v)的一棵最小生成树。这和假设矛盾。如何利用MST性质来构造最小生成树呢？下面介绍它的普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。

取图中任意一个顶点u作为生成树的根，之后往生成树上添加新的顶点v。在添加的顶点v和已经在生成树上的顶点u之间必定存在一条边，并且该边的权值在所有连通顶点u和v之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上一共含有n个顶点为止。普里姆算法的基本思想:

普里姆(prim)算法

在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。

一般情况下所添加的顶点应满足下列条件:UV-Uabcdegf195141827168213127例如:aedcbgf148531621所得生成树权值和=14+8+3+5+16+21=67假设开始顶点就选为顶点1，故首先有U={1}，W=V-U={2，3，4，5，6}

为实现Prim算法，需设置一个辅助数组closedge，以记录从U到V-U具有最小代价的边。对每个顶点Vi∈V－U,在辅助数组中存在一个相应的分量closedge[i-1]，它包括两个域，其中lowcost存储该边的权值；显然，closedge[i-1].Lowcost=Min{cost(u,vi)|u∈U}adjvex域存储该边依附的在U中的顶点。

Typedefstruct{VertexTypeadjvex;//U集中的顶点序号

VRTypelowcost;//边的权值}closedge[MAX_VERTEX_NUM];voidMiniSpanTree_P(MGraphG,VertexTypeu){//用普里姆算法从顶点u出发构造网G的最小生成树

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;//初始，U＝{u}

for(i=0;i<G.vexnum;++i){k=minimum(closedge);//求出加入生成树的下一个顶点(k)

printf(closedge[k].adjvex,G.vexs[k]);//输出生成树上一条边

closedge[k].lowcost=0;//第k顶点并入U集

for(j=0;j<G.vexnum;++j)//修改其它顶点的最小边

if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj};

}}

普里姆算法的时间复杂度为O(n2)。abcdegf195141827168213127aedcbaaa19141814例如:e12ee8168d3dd7213c55具体做法:先构造一个只含n个顶点的子图T，然后从权值最小的边开始，若它的添加不使T中产生回路，则在T上加上这条边，如此重复，直至加上n-1条边为止。考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：克鲁斯卡尔(Kruskal)算法先将图中所有边按权值递增顺序排列，依次选定取权值较小的边，但要求后面选取的边不能与前面选取的边构成回路，若构成回路，则放弃该条边，再去选后面权值较大的边，n个顶点的图中，选够n-1条边即可。abcdegf195141827168213127aedcbgf148531621例如:7121819算法描述:构造非连通图T=(V,{});k=i=0;//k计选中的边数

while(k<n-1){++i;

检查边集E中第i条权值最小的边(u,v);

若(u,v)加入T后不使T中产生回路，则输出边(u,v);

且k++;}

克鲁斯卡尔算法需对e条边按权值进行排序，其时间复杂度为O(eloge)

普里姆算法克鲁斯卡尔算法时间复杂度O(n2)O(eloge)稠密图稀疏图算法名适应范围比较两种算法7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第七章图有向无环图的概念7.5有向无环图及其应用一个无环的有向图称做有向无环图（directedacyclinegraph）。简称DAG图。DAG图是一类较有向树更一般的特殊有向图，下图给出了有向树、DAG图和有向图的例子。

有向树、DAG图和有向图示意

有向无环图是描述含有公共子式的表达式的有效工具。例如下述表达式：

((a+b)*(b*(c+d)+(c+d)*e)*((c+d)*e)

可以用第六章讨论的二叉树来表示，如下页左图所示。仔细观察该表达式，可发现有一些相同的子表达式，如(c+d)和(c+d)*e等，在二叉树中，它们也重复出现。若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间。例如下页右图所示为表示同一表达式的有向无环图。

检查一个有向图是否存在环要比无向图复杂。对于无向图来说，若深度优先遍历过程中遇到回边（即指向已访问过的顶点的边），则必定存在环；而对于有向图来说，这条回边有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。但是，如果从有向图上某个顶点v出发的遍历，在DFS(v)结束之前出现一条从顶点u到顶点v的回边，由于u在生成树上是v的子孙，则有向图必定存在包含顶点v和u的环。

有向无环图是描述一项工程或系统的进行过程的有效工具。除最简单的情况之外，几乎所有的工程（project）都可分为若干个称作活动（activity）的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行：二是估算整个工程完成所必须的最短时间。以下两小节将详细介绍这样两个问题是如何通过对有向图进行拓扑排序和关键路径操作来解决的。

7.5.1拓扑排序在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：①先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；②子项目之间无次序要求，即两个子项目可以同时进行，互不影响。在工厂中，一件设备的生产包括许多工序，各工序之间也存在这两种关系。学校里某个专业的课程学习，有些课程是基础课，它们可以独立于其它课程，即无前导课程；有些课程必须在一些课程学完后才能开始学。这些类似的问题都可以用有向图来表示，我们把这些子项目、工序、课程看成一个个顶点，称之为活动(Activity)。如果从顶点Vi到Vj之间存在有向边<Vi，Vj>,则表示活动i必须先于活动j进行。这种图称做顶点表示活动的网络(ActivityOnVertexnetwork,简称AOV网络)。例如下页的表格表示了某校计算机专业的课程及其相互之间的关系，它对应的AOV网络如后面的图所示。某专业课程设置AOV网络在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系具有传递性。AOV网络中一定不能有有向环。例如在一个图中，V2是V3的前趋顶点，V1是V2的前趋顶点，V3又是V1的前趋顶点，这样就存在一个V1V2

V3

V1的环路，环路表示顶点之间的先后关系进入了死循环。因此，对给定的AOV网络首先要判定网络中是否存在环路，只有有向无环图的网络在应用中才有实际意义。有向环路拓扑排序

问题:

在AOV-网中，不应该出现有向环，因为存在环意味着某项活动应以自己为先决条件，这是荒谬的。若设计出这样的流程图，工程便无法进行。而对程序的数据流图来说，则表明存在一个死循环。因此，对给定的AOV-网应首先判定网中是否存在环。

检测AOV-网中是否存在回路的方法之一，是对有向图构造其顶点的拓扑有序序列，若某个AOV-网中所有顶点都在它的拓扑序列中，则说明该AOV网不会存在回路

何谓“拓扑排序”？简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。对有向图进行如下操作:

按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列例如：对于下列有向图BDAC可求得拓扑有序序列：

ABCD或ACBDBDAC反之，对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路{B,C,D}如何进行拓扑排序？一、从有向图中选取一个没有前驱的顶点，并输出之;

重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。二、从有向图中删去此顶点以及所

有以它为尾的弧;abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念

没有前驱的顶点入度为零的顶点删除顶点及以它为尾的弧弧头顶点的入度减1

为避免每次都要搜索入度为零的顶点，在算法中设置一个“栈”，以保存“入度为零”的顶点。StatusTopologicalSort(ALGraphG){//有向图G采用邻接表存储结构。若G无回路，则输出G的//顶点的一个拓扑序列并返回OK，否则ERROR。

FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1]InitStack(S);for(i=0;i<G.vexnum;++i)//入度为零的顶点入栈

if(!indegree[i])Push(S,i);

count=0;//对输出顶点计数

while(!EmptyStack(S)){Pop(S,i);++count;printf(i,G.vertices[i].data);//输出i号顶点并记数

for(p=G.vertices[i].Firstarc;p;p=pnextarc){k=padjvex;//对i号顶点的每个邻接点的入度减一

if(!（--indegree[k])Push(S,k);//新产生的入度为零的顶点入栈

}}if(count<G.vexnum)printf(“图中有回路”)ElsereturnOK;}//TopologicalSort算法分析：对有n个顶点和e条弧的有向图而言，建立各顶点的入度的时间复杂度为O（e）；建零入度顶点栈的时间复杂度为O（n）；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈，出一次栈，入度减一的操作在WHILE语句中总共执行e次，所以，总的时间复杂度为O（n+e）。32104算法描述例1234560122infirstarc5543^^^adjvexnextarc3^25^240123456^top16toptop0122infirstarc5543^^^adjvexnextarc3^25^240123456^输出序列：63210416toptop0122infirstarc5543^^^adjvexnext3^25^240123456^输出序列：6321041topp0122infirstarc5543^^^adjvexnext2^25^240123456^输出序列：6321041topp0122infirstarc5543^^^adjvexnext2^25^240123456^输出序列：6321041topp0112infirstarc5543^^^adjvexnext2^25^240123456^输出序列：6321041topp0112infirstarc5543^^^adjvexnext2^25^240123456^输出序列：6321041topp=NULL0112infirstarc5543^^^adjvexnext2^25^240123456^输出序列：61321041toptop0112infirstarc5543^^^adjvexnext2^25^240123456^输出序列：6132104topp0102infirstarc5543^^^adjvexnext2^25^240123456^输出序列：6132104topp40102infirstarc5543^^^adjvexnext2^25^240123456^输出序列：6132104p4top0102infirstarc5543^^^adjvexnext2^25^240123456^输出序列：6132104p4top0002infirstarc5543^^^adjvexnext2^25^240123456^输出序列：6132104p4top30002infirstarc5543^^^adjvexnext2^25^240123456^输出序列：6132104p4top30002infirstarc5543^^^adjvexnext2^25^240123456^输出序列：6132104p4top30001infirstarc5543^^^adjvexnext2^25^240123456^输出序列：6132104p4top30001infirstarc5543^^^adjvexnext2^25^240123456^输出序列：6132104p=NULL4top30001infirstarc5543^^^adjvexnext2^25^240123456^输出序列：613321044top30001infirstarc5543^^^adjvexnext2^25^240123456^输出序列：613321044topp0001infirstarc5543^^^adjvexnext1^25^2