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

1、*问题描述：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。1、邻接矩阵表示法:设G=(V,E)是一个图，其中V=V1,V2,V3,Vn。G的邻接矩阵是一个他有下述性质的n阶方阵： 1，若(Vi,Vj)E 或E； Ai,j=0， 反之图5-2中有向图G1和无向图G2的邻接矩阵分别为 M1和 M2:M1= 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 M2= 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 注意无向图的邻接是一个对称矩阵，例如 M2。

2、用邻接矩阵表示法来表示一个具有n个顶点的图时，除了用邻接矩阵中的n*n个元素存储顶点间相邻关系外，往往还需要另设一个向量存储n个顶点的信息。因此其类型定义如下：VertexType vertexMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧(边)数 GraphKind kind; / 图的种类标志 若图中每个顶点只含一个编号i(1ivnum)，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下： type adjmatrix=array1.vnum,1.vnumof adj;

3、利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容易求得各个顶点的度。对于无向图，顶点Vi的度是邻接矩阵中第i行元素之和，即nnD(Vi)Ai,j （或Ai,j） j=1 i=1对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi的入度ID(Vi)为第i列元素之和。即 nnOD(Vi)Ai,j， OD(Vi)Aj,i） j=1j=1用邻接矩阵也可以表示带权图，只要令Wij, 若或(Vi,Vj)Ai,j , 否则。其中Wij为或(Vi,Vj)上的权值。相应地，网的邻接矩阵表示的类型定义应作如下的修改： adj:weightype ; weightype为权类型图

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

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

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

7、至近，依次访问和v有路径相通且路径长度为1、2的顶点。例如，对图G4进行广度优先搜索遍历的过程如图7.13（3）所示，首先访问v1和v1的邻接点v2和v3，然后依次访问v2的邻接点v4和v5及v3的邻接点v6和v7，最后访问v4的邻接点v8。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由此完成了图的遍历。得到的顶点访问序列为 V1 V2 V3 V4 V5 V6 V7 V8和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2、3、的顶点，需附设队列以存储已被访问的路径长度为1、2的顶点。2、图的输出 图的邻接矩阵是一个二维数组，运用for语句的嵌

8、套依次输出。开始开始输入vexnum，arcnumIncInfo选择图的类型构造图ii+1输入顶点ivexnumY深度遍历广度遍历jj+1N初始化邻接矩阵ivexnum结束YjvexnumNYii+1N主程序流程图karcnumkk+1输入弧的信息设置邻接矩阵YN结束图的构造流程图1、无向图邻接矩阵的建立算法如下：procedure build-graph; 建立无向图的邻接矩阵beginfor i:=1 to n do read(G.vertexi)； 读入n个顶点的信息for i:=1 to n dofor j:=1 to e doG.arcsij =0；将邻接矩阵的每个元素初始化成0 f

9、or k:=1 to e do e为边的数目 read(i,j,w) 读入边和权G.arcsij:=wG.arcsijG.arcsii置对称弧 end；该算法的执行时间是O(n+n2+e),其中消耗在邻接矩阵初始化操作上的时间是O(n2),而en2，所以上述算法的时间复杂度是O(n2)。 2、无向网邻接矩阵的建立算法如下：procedure build-graph; 建立无向网的邻接矩阵beginfor i:=1 to n do read(G.vertexi)； 读入n个顶点的信息for i:=1 to n dofor j:=1 to e doG.arcsij =maxint；将邻接矩阵的每个

10、元素初始化成maxint,计算机内用最大事数maxint表示for k:=1 to e do e为边的数目 read(i,j,w) 读入边和权G.arcsij:=w; G.arcsij:=w end；该算法的执行时间是O(n+n2+e),其中消耗在邻接矩阵初始化操作上的时间是O(n2),而en2，所以上述算法的时间复杂度是O(n2)。3、图的深度优先遍历算法分析beginfor i:=1 to n do(visitedi)初始化标志数组while （in）for：i1 to n do按要求访问邻接点end当用二维数组表示邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需时间为O(n2)，其中n

11、为图中顶点数。4、图的广度优先遍历算法分析beginfor i:=1 to n do(visitedi)初始化标志数组while （in）for：i1 to n doif.if.end二维数组表示邻接矩阵作图的存储结构，其中n为图中顶点数,查找每个顶点的邻接点所需时间为O(n2)。#include #include #include #include #include#define ERROR 0#define OK 1#define MAX_VERTEX_NUM 20 /定义最大值#define INFINITY 32768 /定义极大值#define MAX_INFO 20typedef

12、int VrType; /定义新的类型typedef int InfoType;typedef char VertexType;typedef enum DG,DN,UDG,UDNGraphKind;/有向图,有向网,无向图,无向网typedef struct ArcCell /邻接矩阵表示法的各个数据结构 VrType adj; / 顶点关系类型。对无权图，用或表示相邻否；对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexTy

13、pe vertexMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧(边)数 GraphKind kind; / 图的种类标志 MGraph;typedef struct/设置栈int elem1MAX_VERTEX_NUM;int top;SeqStack;int LocateVertex(MGraph G,VertexType v);void CreateUDG(MGraph &G);void CreateUDN(MGraph &G); void DepthFirstSearch1(MG

14、raph G);void BreadthFirstSearch1(MGraph G);int CreateGraph(MGraph &G);void Display(MGraph G);/* Graph.cpp */int LocateVertex(MGraph G,VertexType v)/用于返回输弧端点所表示的数值int j=0,k;for(k=0;kG.vexnum;+k)if(G.vertexk=v)j=k;break;return(j);void CreateUDG(MGraph &G) / 采用数组(邻接矩阵)表示法,构造无向图 int i,j,k,IncInfo; /i，j，

15、k为计数器,IncInfo为标志符 char ch; /用于吃掉多余的字符 VertexType v1,v2; /用于放置输入的弧的两个顶点 printf(请输入无向图G的顶点数,边数,弧是否含相关信息（是：，否：）: n); scanf(%d,%d,%d,&G.vexnum,&G.arcnum,&IncInfo); ch=getchar(); /用于吃掉回车 printf(请输入%d个顶点的值(1个字符，空格隔开):n,G.vexnum); for(i=0;iG.vexnum;+i) / 构造顶点向量 scanf(%c,&G.vertexi);ch=getchar(); printf(请输入

16、%d条边的顶点顶点(以空格作为间隔): n,G.arcnum); for(i=0;iG.vexnum;+i) / 初始化邻接矩阵 for(j=0;jG.vexnum;+j) G.arcsij.adj=0; G.=NULL; / adj,info for(k=0;kG.arcnum;+k) scanf(%c %c,&v1,&v2); ch=getchar();/ ch吃掉回车符 i=LocateVertex(G,v1); j=LocateVertex(G,v2); if(IncInfo)scanf(%d,&G.); G.arcsij.adj=G.arc

17、sji.adj=1; / 置的对称弧 /CreateUDG void CreateUDN(MGraph &G) / 采用数组(邻接矩阵)表示法,构造无向网 int i,j,k,w,IncInfo; /i，j，k为计数器，w用于放置权值,IncInfo为标志符 char ch; /用于吃掉多余的字符 VertexType v1,v2; /用于放置输入的弧的两个顶点 printf(请输入无向图G的顶点数,边数,弧是否含相关信息（是：，否：）:n ); scanf(%d,%d,%d,&G.vexnum,&G.arcnum,&IncInfo); ch=getchar(); /用于吃掉回车 printf

18、(请输入%d个顶点的值(1个字符，空格隔开):n,G.vexnum); for(i=0;iG.vexnum;+i) / 构造顶点向量 scanf(%c,&G.vertexi);ch=getchar(); printf(请输入%d条边的顶点顶点(以空格作为间隔): n,G.arcnum); for(i=0;iG.vexnum;+i) / 初始化邻接矩阵 for(j=0;jG.vexnum;+j) G.arcsij.adj=0; G.=NULL; /adj,info for(k=0;kG.arcnum;+k) scanf(%c %c,&v1,&v2); ch=getchar(

19、);/ ch吃掉回车符 printf(请输入该边的权值: ); scanf(%d,&w); ch=getchar(); i=LocateVertex(G,v1); j=LocateVertex(G,v2); G.arcsij.adj=w; if(IncInfo)scanf(%d,&G.); G.arcsij=G.arcsji; / 置的对称弧 /CreateUDNvoid DepthFirstSearch1(MGraph G) /无向图、无向网深度优先遍历int i,j,k,visited20,t=1,a=1; /i,j,k为计数器，visited20为标志符用于表示是否

20、已经访问过 SeqStack p; for(i=0;iG.vexnum;+i) /初始化标志符 visitedi=0; visited0=1; /规定以第一个字符开始遍历 printf(深度优先遍历开始：n); k=0;i=0; printf(%c ,G.vertex0); while(iG.vexnum) /不断以行循环在遇到符合条件时打印，每打印出一个就让t加，把合适的值用栈来表示，把指针指向新的项 for(j=0;jG.vexnum;+j) if(G.arcsij.adj!=0&G.arcsij.adj!=INFINITY&visitedj=0) printf(%c ,G.vertexj

21、); visitedj=1; p.elem1k=i; p.top=k; k+;i+;a+;t+; break; if(j=G.vexnum) /当在某一行无法找到合适值时，输出栈内的值，返回上一行重新开始循环 i=p.elem1p.top; p.top-; k-; if(t=G.vexnum)break; /当全部的定点都打印出来了就退出循环 printf(n);void BreadthFirstSearch1(MGraph G) /无向图、无向网广度优先遍历int i,j,k,visited20,t=1; /i,j为计数器，visited20为标志符用于表示是否已经访问过 SeqStack

22、p; for(i=0;iG.vexnum;+i) /初始化标志符 visitedi=0; visited0=1; /规定以第一个字符开始遍历 printf(广度优先遍历开始：n); k=0;i=0; printf(%c ,G.vertex0); while(iG.vexnum) for(j=0;jG.vexnum;+j)/不断以行循环在遇到符合条件时打印，每打印出一个就让t加，把指针指向新的项 if(G.arcsij.adj!=0&G.arcsij.adj!=INFINITY&visitedj=0) printf(%c ,G.vertexj); visitedj=1; p.elem1k=i; p.top=k; k+; t+; i+; /换行，重新开始循环 if(t=G.vexnum)break; printf(n);int CreateGraph(MGraph &G) /构造图printf(请输入要构造的图的类型(有向图:0,有向网:1,