71图的定义和术语72图的存储结构73图的遍历课件

7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径

第七章图7.1图的定义和术语第七章图图(Graph)——由一个顶点集V和一个边集E构成的数据结构。

Graph=(V,E)其中，V={x|x

某个数据对象}是非空有限的顶点集合；

E={(x,y)|x,y

V}或E={<x,y>|x,y

V&&Path(x,y)}是有限的顶点之间关系的集合，(x,y)也叫做边(edge)集合,它是无方向的;Path(x,y)表示从x到y的一条单向通路,它是有方向的,所以<x,y>也叫做弧(arc)的集合,x称为弧尾或始点,y称为弧头或终点.7.1图的定义和术语图(Graph)——由一个顶点集V和一个边集E构成的数据结构有向图——有向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集

E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为<v,w>，v,w是顶点，v为弧尾，w为弧头无向图——无向图G是由两个集合V(G)和E(G)组成的

其中：V(G)是顶点的非空有限集

E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v) 7.1图的定义和术语有向图——有向图G是由两个集合V(G)和E(G)组成的7.1例7.1245136G1图G1中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例7.2157324G26图G2中：V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}7.1图的定义和术语例7.1245136G1图G1中：V(G1)={1,2,3,无向完全图(Completedgraph)—n个顶点的无向图有n(n-1)/2条边（最大边数是n(n-1)/2）有向完全图——n个顶点的有向图，有n(n-1)条边（最大边数是n(n-1)）稀疏图(sparsegraph)：边或弧很少的图,通常边数<nlog2n稠密图(Densegraph)无向图中，边数接近n(n-1)/2；

有向图中，边数接近n(n-1)7.1图的定义和术语无向完全图(Completedgraph)—n个顶点的无有向完全图7.1图的定义和术语无向图(树)有向图完全图无向完全图有向完全图7.1图的定义和术语无向图(树)有向图完全图无权——与图的边或弧相关的数网——带权的有向图叫有向网，带权的无向图叫无向网7.1图的定义和术语权——与图的边或弧相关的数7.1图的定义和术语子图——如果图G(V,E)和图G’(V’,E’),满足：V’V，E’E

则称G‘为G的子图7.1图的定义和术语子图——如果图G(V,E)和图G’(V’,E’),满足：7.邻接点(或相邻点),关联

如果e=(u,v)是E(G)中的一条边，则称u与v互为邻接顶点或相邻顶点;称边e与顶点u,v关联;如果e=<u,v>

是E(G)中的一条弧，则称u邻接到v,v邻接于u,也称e与u,v关联;称弧e与顶点u,v关联;7.1图的定义和术语邻接点(或相邻点),关联7.1图的定义和术语顶点的度（于树的度不同）无向图中，顶点的度为与每个顶点相连的边数,记作TD(v)有向图中，顶点的度分成入度与出度入度：以该顶点为头的弧的数目,记为ID(v)出度：以该顶点为尾的弧的数目,记为OD(v)一个顶点的度数等于该顶点的入度与出度之和,即TD(v)=OD(v)+ID(v)7.1图的定义和术语顶点的度（于树的度不同）7.1图的定义和术语路径——路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)E或<Vij-1,Vij>E,(1<jn)路径长度——沿路径边的数目或沿路径各边权值之和简单路径——序列中顶点不重复出现的路径回路(环)——第一个顶点和最后一个顶点相同的路径简单回路(简单环)——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路7.1图的定义和术语路径——路径是顶点的序列V={Vi0,Vi1,……Vin}，7.1图的定义和术语V0V1V3V2V0V1V3V2V0V1V2V0V1V3V07.1图的定义和术语V0V1V3V2V0V1V3V2V0连通图与连通分量在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。ABCDEHMFGIJLK无向图G的三个连通分量ABCDEFGIJLHMK无向图G7.1图的定义和术语连通图与连通分量ABCDEHMFGIJLK无向图G的三个连通强连通图与强连通分量在有向图中,

若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。强连通图有向图G有向图G的两个强连通分量7.1图的定义和术语强连通图与强连通分量强连通图有向图G生成树：是一个极小连通子图，它含有图中全部n个顶点，但只有n-1条边。如果在生成树上添加1条边，必定构成一个环若图中有n个顶点，却少于n-1条边，必为非连通图。ABCDEHMABCDEHM无向图G

无向图G的生成树

7.1图的定义和术语生成树：是一个极小连通子图，它含有图中全部n个顶点，但只有n生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。有向图G的生成森林有向图G7.1图的定义和术语生成森林：有向图G的生成森林有向图G7.1图的定义和术语本章只讨论简单图,有两类图形不在本章讨论之列：7.1图的定义和术语本章只讨论简单图,有两类图形不在本章讨论之列：7.1图的图的抽象数据类型定义ADTGraph{数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}；VR={<v,w>|v,w∈V且P(v,w),

<v,w>表示从v到w的弧，

谓词P(v,w)定义了弧<v,w>的意义或信息}基本操作P：}图的抽象数据类型定义ADTGraph{CreatGraph(&G,V,VR)

//按定义(V,VR)构造图DestroyGraph(&G)://销毁图基本操作LocateVex(G,u);

//若G中存在顶点u，则返回该顶点在图中“位置”

；否则返回其它信息。GetVex(G,v);

//返回v的值。PutVex(&G,v,value);

//对v赋值value。CreatGraph(&G,V,VR)DestroyGrFirstAdjVex(G,v);//返回v的“第一个邻接点”。若该顶点//在G中没有邻接点，则返回“空”。NextAdjVex(G,v,w);//返回v的（相对于w的）“下一个邻接

点”。若w是v的最后一个邻接点，则返回“空”。基本操作FirstAdjVex(G,v);NextAdjVex(InsertArc(&G,v,w);

//在G中增添弧<v,w>，若G是无向的，//则还增添对称弧<w,v>。DeleteArc(&G,v,w);

//在G中删除弧<v,w>，若G是无向的，//则还删除对称弧<w,v>。DeleteVex(&G,v);//删除G中顶点v及其相关的弧。InsertVex(&G,v);//在图G中增添新顶点v。基本操作InsertArc(&G,v,w);DeleteArcDFSTraverse(G,v,Visit())//从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit())//从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。DFSTraverse(G,v,Visit())BFST图的四种常用的存储形式：邻接矩阵和加权邻接矩阵（labeledadjacencymatrix）邻接表十字链表邻接多重表7.2图的存储结构图的四种常用的存储形式：7.2图的存储结构一、(加权)邻接矩阵（labeledadjacencymatrix）设图G=<V,E>是一个有n个顶点的图，则图的邻接矩阵是一个二维数组G.arcs[n][n]，定义：一、(加权)邻接矩阵（labeledadjacencym无向图G1有向图G2无向图G1有向图G2

一、(加权)邻接矩阵（continue）(1)对称矩阵(可采用压缩存储);(2)每一行(或列)1的个数是该顶点的度;(3)主对角线全为0(简单图);从邻接矩阵中可以反映图的许多特征:无向图一、(加权)邻接矩阵（continue）(1)对称矩阵(

一、(加权)邻接矩阵（continue）有向图(1)每一行1的个数是该顶点的出度;(2)每一列1的个数是该顶点的入度;(3)主对角线全为0(简单图);有向图的邻接矩阵不一定对称。一、(加权)邻接矩阵（continue）有向图(1)每一定义为：G.arcs[i][j]=Wij

<vi,vj>或（vi,vj）∈VR∞无边（弧）以有向网为例：邻接矩阵：N.Edge=(

v1v2

v3v4v5v6

)顶点表：5v1v2v3v4v5v6489755613N∞

5

∞

7

∞

∞∞

∞

4

∞

∞

∞

8

∞

∞

∞∞

9∞

∞

5∞

∞

6∞

∞

∞

5

∞

∞

3

∞

∞∞

1

∞网络的邻接矩阵

一、(加权)邻接矩阵（continue）定义为：G.arcs[i][j]=Wij<v容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。

n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。邻接矩阵法优点：邻接矩阵法缺点：

一、(加权)邻接矩阵（continue）容易实现图的操作，如：求某顶#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20typedefenum{DG,DN,UDG,UDN}GraghKind;typedefstructArcCell{//弧的定义

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

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

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

InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];用邻接矩阵表示的图的存储表示(P161)用邻接矩阵表示的图的存储表示(P161)typedefstruct{//图的定义

VertexTypevexs[MAX_VERTEX_NUM];//顶点信息

AdjMatrixarcs;//弧的信息

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

GraphKindkind;//图的种类标志

}MGraph;

用邻接矩阵表示的图的存储表示(continue)typedefstruct{//图的定义用邻接矩阵表StatusCreateUDN(Mgraph&G){//用邻接矩阵表示returnOK;}例：用邻接矩阵生成无向网的算法（参见教材P162）scanf(&G.vexnum,&G.arcnum,&IncInfo);//输入总顶点数，总弧数和信息for(i=0;i<G.vexnum,;++i)scanf(&G.vexs[i]);//输入顶点值，存入一维向量中for(i=0;i<G.vexnum;++i)//对邻接矩阵n*n个单元初始化，adj=∞,info=NULLfor(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};for(k=0;k<G.arcnum;++k){//给弧赋初值(循环次数＝弧数)

scanf(&v1,&v2,&w);i=LocateVex(G,v1);j=LocateVex(G,v2);//找到两顶点在矩阵中的位置(n次)

G.arcs[i][j].adj=w;//输入对应权值

If(IncInfo)Input(*G.arcs[i][j].info);G.arcs[j][i]=G.arcs[i][j]；//无向网是对称矩阵}对于n个顶点e条弧的网，建网时间效率=O(n2+n+e*n)StatusCreateUDN(Mgraph&G){//intfirstAdjVex(MgraphG,intv){

//返回顶点v的第一个邻接点，G为无向图for(k=0;k<G.vexnum;k++) if(G.adj[v][k]>0)break; if(k>=G.vexnum)k=-1;//无邻接点

returnk;}//endfirstAdjVex()图的部分操作在邻接矩阵上的实现intfirstAdjVex(MgraphG,int二、邻接表(AdjacencyList)无向图的邻接表为每个顶点建立一个单链表,第i个单链表中的结点表示与顶点vi相邻的顶点01234^1334^142^0注：邻接表不唯一，因各个边结点的链入顺序是任意的。v1v2v3v4v523^142^0v1v2v3v5v4v4二、邻接表(AdjacencyList)无向图的邻接表data:结点的数据域，保存结点的数据值。firstarc:结点的指针域，给出自该结点出发的的第一条边

的边结点的地址。头结点:datafirstarcadjvexnextarc表结点:adjvex:该边或弧所指向的顶点的位置.nextarc:指向下一条边或弧的指针.二、邻接表(AdjacencyList)adjvexnextarcdatafirstarcdata:结点的数据域，保存结点的数据值。头结点:在无向图的邻接表中,如何求每个顶点的度？若顶点数为n,边数为e时,则在无向图中共需多少个结点？二、邻接表(AdjacencyList)01234^1334^142^0v1v2v3v4v523^142^0v1v2v3v5v4v4n个头结点,2e个表结点第i

个链表中的结点个数是顶点i的度在无向图的邻接表中,如何求每个顶点的度？若顶点数为n,边数为有向图的邻接表和逆邻接表在有向图的邻接表中，第i

个单链表链接的边都是顶点i

发出的边。也叫做出边表。在有向图的逆邻接表中，第i

个单链表链接的边都是进入顶点

i

的边。也叫做入边表。v1v2v3v4V4V3^V2V12^3^0^1V4V3V2V1^3^0^2^0邻接表(出边)逆邻接表(入边)01230123用邻接表表示有向图时，若不考虑逆邻接表，只需n个顶点结点，e个边结点。有向图的邻接表和逆邻接表v1v2v3v4V4V3^V2V12网络(带权图)的邻接表带权图的边结点中保存该边上的权值cost网络(带权图)的邻接表带权图的边结点中保存该边上的权值邻接表表示的图的存储结构（P163）//边结点定义typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置

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

InfoType*info;//该弧相关信息的指针}ArcNode;adjvexinfonextarc邻接表表示的图的存储结构（P163）//边结点定义adjve//头结点定义typedefstructVNode{VertexTypedata;//顶点信息

ArcNode*firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[MAX_VERTEX_NUM];datafirstArc邻接表表示的图的存储结构（P163）//头结点定义datafirstArc邻接表表示//图的定义typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;//图的种类标志}ALGraph;

邻接表表示的图的存储结构（P163）//图的定义邻接表表示的图的存储结构（P163）图的操作在邻接连表的上的实现intfirstAdjVex(ALGraphghead,intv){ returnghead[v]->firstArc.adjvex; }//endfirstAdjVex()intnextAdjVex(ALGraphghead,intv,intw){ p=ghead[v]->firstArc; while(p&&p->adjvex!=w)p=p->next; if(!p)return0; elsereturnp->next->adjvex; }//endnextAdjVex()找某顶点的所有邻接点的时间复杂度是O(e)图的操作在邻接连表的上的实现找某顶点的所有邻接点的时间复杂度如何建立邻接表（以有向图为例）算法思想：首先将邻接表表头数组初始化，vertex域初始化为i，firstarc初始化为NULL；然后对读入的每一条弧<i,j>，产生一个表结点，adjver域置为j，并将结点链接到邻接表的第i个链表中。如何建立邻接表（以有向图为例）算法思想：算法如下：VoidGreatAdjList(ALGraph&G){ArcNode*p;sacnf(“%d%d”,&n,&e);G.vexnum=n;G.arcnum=e;for(i=0;i<n;i++){G.vertices[i].vertex=i;G.vertices[i].firstarc=NULL;}for(k=0;k<e;k++){scanf(i,j);p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;}}//GreatAdjList算法如下：VoidGreatAdjList(ALGraph讨论：邻接表与邻接矩阵的比较1.联系：都可以用来存储有向图和无向图；邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：①邻接矩阵是顺序结构，邻接表是链式结构②对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（e<<n2)讨论：邻接表与邻接矩阵的比较1.联系：都可以用来存储有向图三、邻接多重表(无向图的一种存储结构)在无向图的邻接表中,一条边出现两个单链表中.浪费空间，也给某种操作带来了困难。在邻接多重表中，每一条边只有一个结点(称边结点)为有关边的处理提供了方便。三、邻接多重表(无向图的一种存储结构)在无向图的邻接表中

markivexjvexilinkjlink其中:mark

是记录是否处理过的标记；ivex和jvex是依附于该边的两顶点位置。ilink域指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边。需要时还可设置一个存放与该边相关的权值的域

cost。边结点的结构Ebox:三、邻接多重表(无向图的一种存储结构)markivexjvexilinkj顶点结点的结构:

其中:data

存放与该顶点相关的信息;Firstarc是指示第一条依附于该顶点的边的指针。存储顶点信息的结点表以顺序表方式组织.在邻接多重表中,所有依附于同一个顶点的边都链接在同一个单链表中。从顶点i

出发,可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。

dataFirstarcVexBox:三、邻接多重表(无向图的一种存储结构)顶点结点的结构:dataFirsta例aecbd0123acdb4e010323212441^^^^^三、邻接多重表(无向图的一种存储结构)例aecbd0123acdb4e0四、十字链表(有向图的一种存储结构)可以把十字链表看成是将有向图的邻接表和逆邻接表这两个表结合起来而得到的一种链表。在十字链表中,有向图中每一条弧对应一个结点(称弧结点)每一个顶点也对应一个结点(称顶点结点)。四、十字链表(有向图的一种存储结构)可以把十字链表看成是将有其中:

tailvex表示该弧的弧尾顶点在图中的位置；

headvex表示该弧的弧头顶点在图中的位置；

hlink指向弧头相同的下一条弧的指针；

tlink指向弧尾相同的下一条边的指针。需要时还可有权值域cost

边结点的结构tailvexheadvexhlinktlinkArcBox:四、十字链表(有向图的一种存储结构)其中:边结点的结构tailvexheadv顶点结点的结构

dataFirstinFirstoutVexNode:其中:数据域data存放与该顶点相关的信息，指针域Firstin指向以该顶点为弧头的第一条弧；指针域Firstout指向以该顶点为弧尾的第一条弧。四、十字链表(有向图的一种存储结构)顶点结点的结构dataFirstin例bdacabcd012302012320323130^^^^^^^^四、十字链表(有向图的一种存储结构)例bdacabcd01230#defineMAX_VERTEX_NUM20TypedefstructArcBox{//弧结点结构

inttailvex,headvex;structArcBox*hlink,tlink;InfoType*info;}ArcBox；TypedefstructVexNode{//顶点结构

VertexTypedata;ArcBox*firstin,*firstout;}VexNode;Typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//表头向量

intvexnum,arcnum;}OLGraph;//图结构#defineMAX_VERTEX_NUM207.3图的遍历从已给的连通图中某一顶点出发，沿着一些边访问图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历(GraphTraversal)。深度优先遍历广度优先遍历图的两种遍历方法7.3图的遍历从已给的连通图中某一顶点出发，沿着一些边访图中可能存在回路，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组visited[]，它的初始状态为0，在图的遍历过程中，一旦某一个顶点i

被访问，就立即让visited[i]

为1，防止它被多次访问。7.3图的遍历图中可能存在回路，在访问完某个顶点之后可能会沿着某些边又回到DFS算法思想：深度优先搜索DFS(DepthFirstSearch)从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至V0的所有邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。DFS算法思想：深度优先搜索DFS(DepthFirs深度优先搜索DFS(DepthFirstSearch)深度优先搜索的示例深度优先遍历生成树深度优先搜索DFS(DepthFirstSearch图的深度优先遍历算法voiddfsTraverse(){ for(v=1;v<=n;v++)visited[v]=false; for(v=1;v<=n;v++) if(!visited[v])dfs(v);}voiddfs(intv){visited[v]=1;for(w=firstAdjVex(v);w;w=nextAdjVex(v,w)) if(!visited[w])dfs(w); }//使用ADT在递归函数中增加一计数器sum，初值为n，每访问一次就减1,减到0则return，可避免递归时间过长。图的深度优先遍历算法在递归函数中增加一计数器sum，初值为n在邻接矩阵A上实现

voiddfs(intv){visited[v]=true;for(w=1;w<=n;w++) if(A[v][w]>0) if(!visited[w])dfs(w); }//

图的深度优先遍历算法在邻接矩阵A上实现图的深度优先遍历算法在邻接链表上实现

voiddfs(intv){visited[v]=true;

p=ghead[v]->firstArc;

while(p){w=p->adjvex; if(!visited[w])dfs(w);

p=p->next;

}同学们自己考虑非递归实现算法图的深度优先遍历算法在邻接链表上实现同学们自己考虑非递归实现算法图的深度优先遍Dfs1(Graphg,intv){//利用栈实现非递归算法

//第一个顶点入栈并访问Visit(v);visit[v]=1;push(s,v);//当栈不空时做

Whlie(!EmptyStack(s)){p=ghead[v]->firstArc;//找到栈顶的一个未被访问的邻接点，入栈并访问

while(p){w=p->adjvex; if(!visited[w]){push(s,w);visit(w);p=ghead[w]->firstArc;}elsep=p->next;}//while//如果所有邻接点都被访问，出栈

pop(s,v);}//while}Dfs1(Graphg,intv){//利用栈实现非递V1V2V4V5V3V7V6V8例深度遍历：V112341342vexdatafirstarc2783^^^adjvexnext55641^51282^678678736354^^^V3V7V6V2V5V8V4V1V2V4V5V3V7V6V8例深度遍历：V112341V1V2V4V5V3V7V6V8例12341342vexdatafirstarc2783^^^adjvexnext556^482^6786787^^^深度遍历：V1V3V7V6V2V4V8V5V1V2V4V5V3V7V6V8例12341342vexdaDFS算法效率分析:

设图中有n个顶点，e条边，遍历时对图中每个顶点至多调用一次DSF函数，遍历图的过程就是对每个顶点查找其邻接点的过程，消耗的时间取决于所采用的存储结构如果用邻接矩阵来表示图，查找每个顶点的邻接点所需的时间为O(n2)。如果用邻接表来表示图，查找每个顶点的邻接点所需的时间为O(e),加上访问n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。DFS算法效率分析:设图中有n个顶点，e条边，遍历二、广度优先搜索BFS(BreadthFirstSearch

)BFS算法思想：从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。二、广度优先搜索BFS(BreadthFirstSeABCDEFGHIJKL树的按层次进行访问的次序：

A、B、C、D、E、F、G、H、I、J、K、L适用的数据结构：队列二、广度优先搜索BFSABCDEFGHIJKL树的按层次进行访问的次序：二、广度优除了辅助数组visited[]之外，为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。广度优先搜索BFS除了辅助数组visited[]之外，为了实现逐层访VoidBFSTraverse(GraghG,intv){

for(v=0;v<G.vexnum;v++)visited[v]=0;//清访问标记

InitQueue(Q);//清队列Q;

for(v=0;v<G.vexnum;v++)//对每一个顶点vif(!visited[v]){visited[v]=1;visit(v);//访问v;标记v;EnQueue(Q,v);//v未被访问

while(!QueueEmpty(Q))

{

//Q不空

DeQueue(Q,u);//出队头元素到ufor(w=firstAdjVex(u);w;w=nextAdjVex(u,w))

if(!visited[w]){visited[w]=1;visit(w);EnQueue(w);//将u的每个未被访问的邻接点w入队

}//if

}//while

}//if}VoidBFSTraverse(GraghG,int例adbce1234acdbvexdatafirstarc5543^^^adjvexnext5e1^51143^22012345afr遍历序列：a012345dfr遍历序列：ad012345dcfr遍历序列：adc例adbce1234acdbvexdatafirstarc1234acdbvexdatafirstarc5543^^^adjvexnext5e1^51143^22012345dcbfr遍历序列：adcb012345

cbfr遍历序列：adcb012345

cbefr遍历序列：adcbe例adbce1234acdbvexdatafirstarc55401234525fr遍历序列：adcbe0123455fr遍历序列：adcbe012345

fr遍历序列：adcbe1234acdbvexdatafirstarc5543^^^adjvexnext5e1^51143^22例adbce012345算法分析:如果使用邻接表表示图，则循环的总时间代价为d0+d1+…+dn-1=O(e)，其中的di是顶点i的度如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的n个元素，总的时间代价为O(n2)。广度优先搜索BFSDFS与BFS之比较：空间复杂度相同，都是O(n)(借用了堆栈或队列）；时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。算法分析:如果使用邻接表表示图，则循环的总时间代价为d0+1.求一条从顶点i到顶点s的简单路径2.

求两个顶点之间的一条路径长度最短的路径三、遍历应用举例1.求一条从顶点i到顶点s的简单路径2.求两个顶应用1.求一条从顶点i到顶点s的简单路径abchdekfg求从顶点b到顶点k的一条简单路径。从顶点b出发进行深度优先搜索遍历例如:假设找到的第一个邻接点是a,且得到的结点访问序列为:

b

adhce

kfg假设找到的第一个邻接点是c,则得到的结点访问序列为:

b

chdae

kfg应用1.求一条从顶点i到顶点s的简单路径abchvoidDFSearch(intv,ints,char*PATH){//从第v个顶点出发递归地深度优先遍历图G，//求得一条从v到s的简单路径，并记录在PATH中

visited[v]=TRUE;//访问第v个顶点

for(w=FirstAdjVex(v);w!=0;

w=NextAdjVex(v))if(!visited[w])DFSearch(w,s,PATH);

}

Append(PATH,getVertex(v));

//第v个顶点加入路径&&!foundif(w==s){found=TRUE;Append(PATH,w);}else

if(!found)Delete(PATH,v);

//从路径上删除顶点vvoidDFSearch(intv,ints,c应用2.求两个顶点之间的一条路径长度最短的路径

若两个顶点之间存在多条路径，则其中必有一条路径长度最短的路径。如何求得这条路径?应用2.求两个顶点之间的一条路径长度最短的路径若两abchdekfg求路径长度最短的路径可以基于广度优先搜索遍历进行，但需要修改队列的结点结构及其入队列和出队列的算法。深度优先搜索访问顶点的次序取决于图的存储结构，而广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。abchdekfg求路径长度最短的路径可以基于广度优先搜索遍例如:求下图中顶点3至顶点5的一条最短路径。队列用双向链表的表示:

312475

Q.front

Q.rear321475689例如:求下图中顶点3至顶点5的一条最短路径。队列用双7.4图的连通性问题对无向连通图进行遍历得到的将是一个极小连通子图，即图的生成树！由深度优先搜索得到的生成树，称为深度优先搜索生成树。由广度优先搜索得到的生成树，称为广度优先搜索生成树。对非连通图进行遍历，得到的将是各连通分量的生成树，即图的生成森林！7.4.1无向图的连通分量和生成树7.4图的连通性问题对无向连通图进行遍历得到的将是一个极例1：画出下图的生成树DFS生成树v0v1v2v4v4v3邻接表01234^1334^142^0v4v3v2v1v023^142^0v0v2v1v4v3BFS生成树v0v1v3v2v4无向连通图例1：画出下图的生成树DFS生成树v0v1v2v4v4v3DEABCFJLMGHIK例2：画出下图的生成森林（或极小连通子图）求解步骤：Step1:先求出邻接矩阵或邻接表；Step2:写出DFS或BFS结果序列；Step3:画出对应子图或生成森林。我们选用邻接表方式来求深度优先搜索生成森林DEABCFJLMGHIK例2：画出下图的生成森林（或极小连1155M12L11K10J9I8H7G6F5E4D3C2B1A012^^0^120^0^4^378^106^6^1011^126^709^1219^111^1229^47^10811DEGHIK子图1：再写出DFS结果（3次）ABMJLCFDEGHKIABCFJLM先写出邻接表（或邻接矩阵）：子图2：子图3：极小连通！1155M12L11K10J9I8H7G6F5E4D3C2BDEGHIK子图(或连通分量)ABCFJLMABCFJLMDEGHIK生成森林DEGHIK子图ABCFJLMABCFJLMDEGHIK生成求连通分量的算法（生成森林用对应的二叉树存储）VoidDFSForest(BiTree&T)

{T=NULL;for(v=0;v<n;v++)visited[v]=0;for(v=0;v<n;v++)if(!visited[v]){p=(CSTree)malloc(sizeof(CSNode));//生成树的根*p={GetVex(G,v),NULL,NULL}if(!T)T=p;//森林空，p是第一棵树

elseq->nextsibling=p;q=p;//q当前森林中最后一棵树的根

DFSTree(G,v,p);//深度优先遍历，并建立树；

}//if}//求连通分量的算法（生成森林用对应的二叉树存储）VoidDFSTree(GraphG,intv,CSTree&T){visited[v]=1;first=true;for(w=firstAdjVex(v);w;w=nextAdjVex(v,w))

if(!visited[w]){ p=(CSTree)malloc(sizeof(CSNode));//生成树的根*p={GetVex(G,v),NULL,NULL}; if(first){T->lchild=p;first=false;} elseq->nextsibling=p;}q=p; DFSTree(G,w,q);

}//if

}//DFSTree()VoidDFSTree(GraphG,intv,7.4.2有向图的强连通分量

算法思想：使用dfs算法思想。设一编号数组finished[]1.

对图G的邻接链表进行dfs遍历，并按退出递归的次序给顶点编号。（1，2，3，….）2.对图G的逆邻接链表进行dfs遍历，每次调用dfs的出发点是编号最大的未被访问的顶点(上次最后完成搜索的顶点）图G1234513245例Finished1234535421得到的顶点集：1,3，24，57.4.2有向图的强连通分量图G1234513245例7.4.3最小生成树MST(MinimumcostSpanningTree)

使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。MST:在网络的多个生成树中，寻找一个各边权值之和最小的生成树。构造最小生成树的准则必须只使用该网络中的边来构造最小生成树；必须使用且仅使用n-1条边来联结网络中的n个顶点；不能使用产生回路的边。7.4.3最小生成树MST(Minimumcost假设在n个城市之间要建立通信网络线，要求使得这个城市之间连通且费用最少。MST典型用途：数学模型：顶点———表示城市，有n个；边————表示线路，有n–1条；边的权值—表示线路的经济代价；连通网——表示n个城市间通信网。问题抽象：

n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST假设在n个城市之间要建立通信网络线，要求使得这个城市之间连通求一个带权连通图中的最小生成树的方法:

Prim算法

Kruskal算法都是利用MST的性质构造最小生成树的算法7.4.3最小生成树MST求一个带权连通图中的最小生成树的方法:都是利用MST的性质构最小生成树的MST性质：若U集是V的一个非空子集，若(u0,v0)是一条最小权值的边，其中u0U，v0V-U；则：(u0,v0)必在某一最小生成树上。UV-U最小生成树的MST性质：若U集是V的一个非空子集，若(u证明（反证法）设G的任何MST都不包含（u,v）。设T是G的一个MST，将（u,v）加入T，形成回路。去掉（u’,v’）得到T’,因wuv<wu’v’，所以T’的边权之和小于T的边权之和，与T是MST矛盾。Uuu’V-Uvv’最小生成树的MST性质：证明（反证法）UV-U最小生成树的MST性质：1、普里姆(Prim)算法普里姆算法的基本思想（是一种贪婪算法）设连通网络图G=<V,E,W>,TE是G上最小生成树中边的集合.1.TE=，U={u0

};2.在U和V-U之间选最小边（u,v），将v加入U，将(u,v)加入TE中;3.重复2直到U=V(或n-1次)1、普里姆(Prim)算法普里姆算法的基本思想（是一种贪婪算普里姆(Prim)算法过程示例1237456281612222510251418普里姆(Prim)算法过程示例1237456281612221237456281612222510251418普里姆(Prim)算法过程示例1237456281612222510251418普里姆(P1237456281612222510251418普里姆(Prim)算法过程示例1237456281612222510251418普里姆(P1237456281612222510251418普里姆(Prim)算法过程示例1237456281612222510251418普里姆(P1237456281612222510251418普里姆(Prim)算法过程示例1237456281612222510251418普里姆(P1237456281612222510251418普里姆(Prim)算法过程示例1237456281612222510251418普里姆(P1237456281612222510251418普里姆(Prim)算法过程示例1237456281612222510251418普里姆(P设置一个辅助数组closedge[]，对每个顶点viV－U,存在分量closedge[i-1],有两个域，Lowcost=Min{cost(u,vi)|uU}adjvex:

存储与该边关联的U中顶点Prime算法的实现辅助数组closedge说明如下:Struct{VertexTypeadjvex;VRTypelowcost;}closedge[MAX_VERTEX_NUM];设置一个辅助数组closedge[]，对每个顶点viV细化的普里姆(Prim)算法:TE={};closedge[v].adjvex=v1;closedge[v].lowcost=adj.matrix[1][v];2.U[1]=1;U[2…n]=0;3.选U[k]=0的closedge[k].lowcost最小的k；4.U[k]=1,u=closedge[k].adjvex,(u,k)加入TE中5.修改所有不属于U的k的邻接点w的lowcost值，规则是：如果closedge[w].lowcost>adj.matrix[k][w]则：closedge[w].lowcost=adj.matrix[k][w]细化的普里姆(Prim)算法:12374562816122225102514181237456281612222510251418Adjvexv3v4v5v6v1v2{1,6,5,4,{}Lowcost1612222410423,2,7}Closedge

I

2

3

4

5

6

7UV-UkAdjvexv1v1v1v1v1v1{1}{2,3,4,6

Lowcost28105,6,7}Adjvexv1v1v1v6v1v1{1,6}{2,3,4,5,5Lowcost2824

10

7}Adjvexv1v1v5v6v1v5{1,6,5}{2,3,4,7}4Lowcost2822

241025Adjvexv1v4v5v6v1v4{1,6,5,4}{2,3,7}3

Lowcost2812

22241018Adjvexv3

v4v5v6v1v4{1,6,5,4,{2,7}2

Lowcost16

12222410

18

3}Adjvexv3v4v5v6v1

v2{1,6,5,4,{7}7Lowcost1612222410

14

3,2}Adjvexv3v4vvoidMiniSpanTree_PRIM(MgtaphG,VertexTypeintu){k=LocateVer(G,u);//k为顶点u的序号for(v=0;v<G.vexnum;v++)if(v!=k)closedge[v]={u,G.arcs[k][j].adj};closedge[k].lowcost=0;//第k个顶点加入在U集合中

for(i=1;i<G.vexnum;i++){k=minimum(closedge);//lowcost最小的顶点序号为ku=closedge[k].adjvex;prinf(u,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}

}//for

}//MinISpan_Tree_PRIMvoidMiniSpanTree_PRIM(Mgtaph设连通网络有n个顶点，则该算法的时间复杂度为O(n2)。它适用于边稠密的网络。Prime算法分析设连通网络有n个顶点，则该算法的时间复杂度为O(n2)2、Kruscal算法算法思想:先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。2、Kruscal算法算法思想:先构造一个只含n个顶构造非连通图ST=(V,{});k=i=0;//k计选中的边数,i计检查的边数

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

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

若(u,v)加入ST后不使ST中产生回路，

则输出边(u,v);

且k++;}算法描述:构造非连通图ST=(V,{});算法描述:√√√√×√×√√√√√×√×√7.4.4关节点和重连通分量

(BiconnectedComponent)若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点(割点)。没有关节点的连通图为重（双）连通图。如何判别给定的连通图是否是双连通图？7.4.4关节点和重连通分量(BiconnectedC在一个无向连通图G中,重连通分量可以利用深度优先生成树找到。关节点的两个特性：1.深度优先生成树的根是关节点的充要条件是它至少有两个子女。2.其它顶点u是关节点的充要条件是它至少有一个子女w,以w为根的子树与u的任一祖先之间无回边。7.4.4关节点和重连通分量

(BiconnectedComponent)在一个无向连通图G中,重连通分量可以利用深度优先生成树找到ahgcbfde例如:下列连通图中，顶点

a

和顶点c

是关节点深度优先生成树abcdefghahgcbfde例如:下列连通图中，顶点a和顶点c是1abcdefgh2345678331111111abcdefgh2345678331111111)设V0为深度优先遍历的出发点

p=G.vertices[0].firstarc;v=p->adjvex;

DFSArticul(G,v);

//从第v顶点出发深度优先搜索

if

(count<G.vexnum)

{

//生成树的根有至少两棵子树

printf(0,G.vertices[0].data);

//根是关节点1)设V0为深度优先遍历的出发点2)定义函数:

low(v)=Min{visited[v],low[w],visited[k]}

其中:顶点w

是生成树上顶点v

的孩子;顶点k

是生成树上和顶点v有回边相联接的祖先;

visited记录深度优先遍历时的访问次序

若对顶点v，在生成树上存在一个子树根w,

且

low[w]≥visited[v]

则顶点v为关节点。2)定义函数:对深度优先遍历算法作如下修改：visited[v]的值改为遍历过程中顶点的访问次序count值;

2.遍历过程中求得

low[v]=Min{visited[v],low[w],visited[k]}3.从子树遍历返回时，判别low[w]≥visited[v]?对深度优先遍历算法作如下修改：visited[v]的值改为遍for(p=G.vertices[v0].firstarc;p;p=p->nextarc){

}voidDFSArticul(ALGraphG,intv0){//从第v0个顶点出发深度优先遍历图G,

//查找并输出关节点}//DFSArticulmin=visited[v0]=++count;//v0是第count个访问的顶点,并设low[v0]的初值为min

//检查v0的每个邻接点low[v0]