邻接矩阵表示图-深度-广度优先遍历

1、*冋题描述：建立图的存储结构(图的类型可以是有向图、无向图、有向网、无向网,学生可以任选两种类型)，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。1、邻接矩阵表示法：设G=(V,E)是一个图，其中V=V1,V2,V3,Vi】。G的邻接矩阵是一个他有下述性质的n阶方阵：1,若(Vi,Vj)eE或eE：Aij=0,反之图5-2中有向图G1和无向图G2的邻接矩阵分别为Ml和M2:Ml=厂01011|1010|1001|L0000JM2=厂0111|1010|IHOI|L1010J注意无向图的邻接是一个对称矩阵，例如M2。用邻接矩阵表示法来表示一个具有n个顶点的图时，除了用

2、邻接矩阵中的n+n个元素存储顶点间相邻关系外，往往还需要另设一个向量存储1】个顶点的信息。因此其类型定义如下：VertexTypevertexMAX_VERTEX_NUM;/顶点向量AdjMatrixarcs;/邻接矩阵intvexnum,arcnum;/图的当前顶点数和弧(边)数GraphKindkind;/图的种类标志若图中每个顶点只含一个编号i(lWiWvnum)，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下：typeadjmatrix=arrayl.vnumJ.vnumjofadj;利用邻接矩阵很容易判定任意两个顶点之间是否有边(或弧)相联，并容易求得各个顶点的度。对

3、于无向图，顶点Vi的度是邻接矩阵中第i行元素之和，即D(Vi)=ZAij(或EAij)j=li=l对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi的入度ED(Vi)为第i列元素之和。即OD(Vi)=EAij,OD(Vi)=ZA|j,i)j=lj=l用邻接矩阵也可以表示带权图，只要令Wij,若Vi,Vj或(Vi,Vj)Aij=00,否则。其中Wij为Vi,Vj或(Vi,Vj)上的权值。相应地，网的邻接矩阵表示的类型定义应作如下的修改：aclj:weiglitype;weiglitype为权类型图5-6列出一个网和它的邻接矩阵。厂OO31OOOOn1OOOO51OO11OO

4、OOOOOOOO11OOOO6OOOO1LOO322OOJ网(b)邻接矩阵图56网及其邻接矩阵对无向图或无向网络，由于其邻接矩阵是对称的，故可釆用压缩存贮的方法, 仅存贮下三角或上三角中的元素(但不含对角线上的元素)即可。显然，邻接矩阵表示法的空间复杂度O(n2)o无向网邻接矩阵的建立方法是：首先将矩阵A的每个元素都初始化成8。然后，读入边及权值(ij,wij),将A的相应元素置成Wijo2、图的遍历：*深度优先搜索深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问，则深度优先遍历可从图的某个顶点V出发,访问此顶点，然后依次从V的未被访问的邻接点出

5、发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点，重复上述过程，直至图中所有顶点都被访问到为止。以图7.13(a)中无向图G.为例，深度优先遍历图的过程如图7.13(b)所示。假设从顶点出发进行搜索，在访问了顶点必后，选择邻接点V2。因为V2未曾访问，则从必出发进行搜索。依次类推，接着从VoV8,V5出发进行搜索。在访问了V5之后，由于V5的邻接点已都被访问，则搜索回到Vs。由于同样的理由，搜索继续回到V.,V?直至仏，此时由于的另一个邻接点为被访问，则搜索乂从必到V$,再继续进行下去。由此得到顶点的访问序列为：fV2fV

6、s-v5-v5-v7显然，这是一个递归的过程。为了在遍历过程中便于区别顶点是否己被访问，需附设访问标志数组vistedo.n-l,其初值为0,但某个顶点被访问，则其相应的分量置为lo*广度优先搜索假设从图中某顶点V出发，在访问了V之后一次访问V的各个未曾访问的扩大邻接点，然后分别从这些邻接点出发依次访问他们的邻接点，并使“先被访问的邻接点”先于“后被访问的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中的顶点都被访问为止。换句话说，广度优先遍历图的过程就是以V为起始点，有远至近，依次访问和V有路

7、径相通且路径长度为1、2的顶点。例如，对图G4进行广度优先搜索遍历的过程如图7.13（3）所示，首先访问vl和vl的邻接点v2和v3,然后依次访问v2的邻接点v4和v5及v3的邻接点v6和说，最后访问v4的邻接点v8。由于这些顶点的邻接点均己被访问，并且图中所有顶点都被访问，由此完成了图的遍历。得到的顶点访问序列为V5-V6-V8和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2、3、的顶点，需附设队列以存储己被访问的路径长度为1、2的顶点。2、图的输出图的邻接矩阵是一个二维数组，运用foi语句的嵌套依次输出。 图的构造流程图1、无向图邻接矩阵的建立算法如

8、下：procedurebuild-giaph;建立无向图的邻接矩阵beginfori:=ltondoread(G.vertexi)；读入11个顶点的信息fori:=ltondoforj:=ltoedoG.arcsij=0：将邻接矩阵的每个元素初始化成0fork:=ltoedoe为边的数目read(ij,w)读入边i和权G.arcsij:=wG.arcsij=G.arcsii置对称弧end；该算法的执行时间是Og+f+e),其中消耗在邻接矩阵初始化操作上的时间是O(iF),而en2,所以上述算法的时间复杂度是O()。2、无向网邻接矩阵的建立算法如下：procedurebuild-giaph;建立

9、无向网的邻接矩阵beginfori:=ltondoread(G.vertexi)；读入11个顶点的信息fori:=ltondoforj:=ltoedoG.arcsij=maxint；将邻接矩阵的每个元素初始化成maxint,计算机内g用最大事数maxint表示fork:=ltoedoe为边的数目read(ij,w)读入边和权G.arcsij:=w;G.arcsij:=wend：该算法的执行时间是Og+if+e),其中消耗在邻接矩阵初始化操作上的时间是O(iF),而en2,所以上述算法的时间复杂度是O()。3、图的深度优先遍历算法分析beginfori:=ltondo(visitedi)初始化标

10、志数组wliile(in)for：i=ltondo按要求访问邻接点end当用二维数组表示邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需时间为O(iF),其中n为图中顶点数。4、图的广度优先遍历算法分析beginfori:=ltondo(visitedi)初始化标志数组wliile(in)for：i=1tondoififend二维数组表示邻接矩阵作图的存储结构，其中n为图中顶点数，查找每个顶点的邻接点所需时间为O(iF)。#include#inc1ude#include#include#includetidefineERROR0tidefineOK1tidefineMAX_VERTEX_NU

11、M20定义最大值tidefineINFINITY32768定义极大值tidefineMAX_INF020typedefintVrType;/定义新的类型typedefintInfoType;typedefcharVertexType;typedefenumDG,DN,UDG,UDNjGraphKind;/有向图，有向网，无向图,无向网typedefstruetArcCell/邻接矩阵表示法的各个数据结构VrTypeadj;/顶点关系类型。对无权图，用或表示相邻否；对带权图，则为权值类型。InfoType*info;/该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NU

12、MMAX_VERTEX_NUM;typedefstruetVertexTypevertexMAX_VERTEX_NUM:/顶点向量AdjMatrixarcs;/邻接矩阵intvexnum,arcnum;/图的当前顶点数和弧(边)数GraphKindkind;/图的种类标志MGraph;typedefstruet/设置栈intelemiMAXVERTEXNUM;inttop;SeqStack;intLocateVertex(MGraphG,VertexTypev):voidCreateUDG(MGraph&G);voidCreateUDN(MGraph&G);voidDepthFirstSear

13、chi(MGraphG):voidBreadthFirstSearchi(MGraphG):intCreateGraph(MGraph&G):voidDisplay(MGraphG):/*Graphcpp*/intLocateVertex(MGraphG,VertexTypev)/用于返回输弧端点所表示的数值intj=0,k;for(k=0:kGvexnum;+k)if(Gvertexk=v)j=k:break:return(j);voidCreateUDG(MGraph&G)/采用数组(邻接矩阵)表示法，构造无向图irrti,j,k,Incinfo:i,j,k为计数器,Incinfo为标志符

14、charch;/用于吃掉多余的字符VertexTypevl,v2;用于放置输入的弧的两个顶点printf(“请输入无向图G的顶点数，边数，弧是否含相关信息(是：，否：)：n);scanf(d,%d,&G.vexnum,&Garcnum,&Inclnfo);ch二getcharO;用于吃掉回年printf(”请输入%d个顶点的値(1个字符，空格隔开)：n,G.vexnum);for(i=0;iG.vexnum;+i)/构造顶点向量scanf(c,&GvertexEi);ch二getchar();printf(请输入%1条边的顶点顶点(以空格作为间隔):n,G.arcnum);for(i二0;iG

15、.vexnum;+i)/初始化邻接矩阵for(j=0;jGvexnum;+j)Garcsijadj二0;G.二NULL;/adj,infofor(k=0;kGarcnum;+k)scanf(“c%c，&vl,&v2);sch=getchar():/ch吃掉回车符i=LocateVertex(G,vl);j=LocateVertex(G,v2);if(IncInfo)scanf(%d,&G.);G.arcsij.adj=G.arcsji.adj=l:/置的对称弧/CreateUDGvoidCreateUDN(MGraph&G)/采用数组(邻接矩阵)表示

16、法，构造无向网inti,j,k,w,IncInfo;/i,j,k为计数器，w用于放置权值,Incinfo为标志符charch;/用于吃掉多余的字符VertexTypevl,v2;用于放置输入的弧的两个顶点printf(”请输入无向图G的顶点数，边数，弧是否含相关信息(是：，否：)：”)；scanf(%d,%d,%d,&G.vexnum,&G.arcnum,felnclnfo);ch二getcharO;用于吃掉IhL车printf(”请输入%d个顶点的値(1个字符，空格隔开)：n,G.vexnum);for(i=0;iG.vexnum;+i)/构造顶点向量scanf(%c,&G.vertexi)

17、;ch=getchar();printf(请输入%4条边的顶点顶点(以空格作为间隔):n,G.arcnum);for(i=0;iG.vexnum.:+i)/初始化邻接矩阵for(j=0;jG.vexnum;+j)G.arcsij.adj=0;G.二NULL;/adj,infofor(k=0;kG.arcnum;+k)scanf(%c%c,&vl,&v2);ch=getchar():/ch吃掉回车符printf请输入该边的权值:”)；scanf(%d,&w);ch二getchar();i=LocateVertex(G,vl);j=LocateVertex(G,v2);G.a

18、rcsij.adj二w;if(IncInfo)scanf(%d,&G.);G.arcstij=G.arcstji;/置的对称弧 /CreateUDNvoidDepthFirstSearchi(MGraphG)/无向图、无向网深度优先遍历inti,j,k,visited20,t=l,a=l:/i,j,k为计数器，visited20为标志符用于表示是否己经访问过SeqStackp;for(i=0;iG.vexnum;卄i)/初始化标志符visitedEi=0;visited0=l;/规定以第一个字符开始遍历printf(”深度优先遍历开始：n)；k=0;i=0;printf(

19、%cG.vertex0);while(iG.vexnum)/不断以行循环在遇到符合条件时打印，每打印出一个就让t加，把合适的值用栈來表示，把指针指向新的项for(j=0;jG.vexnum;+j)if(G.arcstij.adj!=0&G.arcstij.adj!=INFINITY&visitedj=0)printf(%cG.vertexj);visitedj=1;p.elemik=i;p.top=k:k+;i+:a+;t+;break;if(j=G.vexnum)/当在某一行无法找到合适值时，输出栈内的值，返回上一行重新开始循环i=p.elemip.top;p.top；k-；if(t=G.v

20、exnum)break;/当全部的定点都打印出來了就退出循环printf(n);voidBreadthFirstSearchl(MGraphG)/无向图、无向网广度优先遍历inti,j,k,visited20,t=l;/i,j为计数器，visited20为标志符用于表示是否己经访问过SeqStackp;for(i=0;iG.vexnum:卄i)/初始化标志符visitedi=0;visited0=l;/规定以第一个字符开始遍历printfCr度优先遍历开始：n)；k=0;i=0;printf(%cG.vertex0);while(iG.vexnum)for(j=0:jG.vexnum;+j)/

21、不断以彳亍循环在遇到符合条件时打印,每打印出一个就让t加，把指针指向新的项if(G.arcstij.adj!=0&G.arcstij.adj!=INFINITY&visitedj=0)printf(%cG.vertexj);visitedj=1;p.elemik=i;p.top=k;k+:t+;i+；/换行，重新开始循环if(t二二G.vexnum)break;printf(n);intCreateGraph(MGraph&G)/构造图printf(/z请输入要构造的图的类型(有向图:0,有向网：1,无向图:2,无向网：3):n)；scanf(%d,&G.kind);switch(G.kind)case2:CreateUDG(G);break;case3:CreateUDN(G);break;defauIt:returnERROR:/CreateGraphvoidDisplay(MGra