《邻接矩阵表示图深度广度优先遍历》由会员分享，可在线阅读，更多相关《邻接矩阵表示图深度广度优先遍历（11页珍藏版）》请在金锄头文库上搜索。
1、*问题描述：建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。1、邻接矩阵表示法:设 G=(V,E)是一个图，其中 V=V1,V2,V3,Vn。G 的邻接矩阵是一个他有下述性质的 n 阶方阵：1，若(Vi,Vj)E 或 E；Ai,j=0，反之图 5-2 中有向图 G1 的邻接矩阵为 M1M1= 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 用邻接矩阵表示法来表示一个具有 n 个顶点的图时，除了用邻接矩阵中的n*n 个元素存储顶点间相邻关系外，往往还需要另设一个向量存储 n 个顶点的信息。因此其类型定义如下：VertexType ver
2、texMAX_VERTEX_NUM; / 顶点向量AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧(边)数GraphKind kind; / 图的种类标志若图中每个顶点只含一个编号 i(1ivnum)，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下：type adjmatrix=array1.vnum,1.vnumof adj;利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容1易求得各个顶点的度。对于有向图，顶点 Vi 的出度 OD(Vi)为邻接矩阵第 i 行元素之和，顶点 Vi的入度 ID(Vi)为第
3、 i 列元素之和。即nnOD(Vi) Ai,j， OD(Vi)Aj,i）j=1 j=1 用邻接矩阵也可以表示带权图，只要令Wij, 若或(Vi,Vj)Ai,j , 否则。其中 Wij 为 或 (Vi,Vj)上的权值。相应地，网的邻接矩阵表示的类型定义应作如下的修改： adj:weightype ; weightype 为权类型2、图的遍历：*深度优先搜索深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问，则深度优先遍历可从图的某个顶点 V 出发，访问此顶点，然后依次从 V 的未被访问的邻接点出发深度优先遍历图，直至图中所有和 V 有路径相通的顶点都
4、被访问到；若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点，重复上述过程，直至图中所有顶点都被访问到为止。以图中无向图 G4为例，深度优先遍历图的过程如图所示。假设从顶点 V1出发进行搜索，在访问了顶点 V1后，选择邻接点 V2。因为 V2未曾访问，则从 V2出发进行搜索。依次类推，接着从 V4,V8,V5出发进行搜索。在访问了 V5之后，由于 V5的邻接点已都被访问，则搜索回到 V8。由于同样的理由，搜索继续回到V4，V 2直至 V1，此时由于 V1的另一个邻接点为被访问，则搜索又从 V1到 V3，再2继续进行下去。由此得到顶点的访问序列为：V1 V2 V4 V8 V5 V3 V6
5、 V7显然，这是一个递归的过程。为了在遍历过程中便于区别顶点是否已被访问，需附设访问标志数组 visted0.n-1,其初值为 0，一但某个顶点被访问，则其相应的分量置为 1。2、图的输出图的邻接矩阵是一个二维数组，运用 for 语句的嵌套依次输出。YNYN YN 主程序流程图Y开始输入vexnum，arcnumIncInfoi和权G.arcsij:=wG.arcsijG.arcsii置对称弧end；该算法的执行时间是 O(n+n2+e),其中消耗在邻接矩阵初始化操作上的时间是 O(n2),而 e #include #include #include #include#define ERROR
6、 0#define OK 1#define MAX_VERTEX_NUM 20 /定义最大值#define INFINITY 32768 /定义极大值#define MAX_INFO 20typedef int VrType; /定义新的类型typedef int InfoType;typedef char VertexType;typedef enum DG,DN,UDG,UDNGraphKind;/有向图,有向网,无向图,无向网typedef struct ArcCell /邻接矩阵表示法的各个数据结构VrType adj; / 顶点关系类型。对无权图，用或表示相邻否；对带权图，则为权值类
7、型。InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vertexMAX_VERTEX_NUM; / 顶点向量AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧(边)数GraphKind kind; / 图的种类标志 MGraph;typedef struct/设置栈5int elem1MAX_VERTEX_NUM;int top;SeqStack;int LocateVertex(MG
8、raph G,VertexType v);void CreateUDG(MGraph &G);void CreateUDN(MGraph &G); void DepthFirstSearch1(MGraph G);void BreadthFirstSearch1(MGraph G);int CreateGraph(MGraph &G);void Display(MGraph G);/* Graph.cpp */#includeGraph.hint LocateVertex(MGraph G,VertexType v)/用于返回输弧端点所表示的数值int j=0,k;for(k=0;k的对称弧/
9、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(请输入%d个顶点的值(1个字符，空格隔开):n,G.v
10、exnum);for(i=0;i的对称弧 /CreateUDNvoid DepthFirstSearch1(MGraph G) /无向图、无向网深度优先遍历int i,j,k,visited20,t=1,a=1; /i,j,k为计数器，visited20为标志符用于表示是否已经访问过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)/不断以行循环在遇到符合条件时打印
11、，每打印出一个就让t加，把合适的值用栈来表示，把指针指向新的项for(j=0;jG.vexnum;+j)if(G.arcsij.adj!=0&G.arcsij.adj!=INFINITY&visitedj=0) printf(%c ,G.vertexj);visitedj=1;p.elem1k=i;p.top=k;k+;i+;a+;t+;break;if(j=G.vexnum)/当在某一行无法找到合适值时，输出栈内的值，返回上一行重新开始循环i=p.elem1p.top;p.top-;k-;8if(t=G.vexnum)break; /当全部的定点都打印出来了就退出循环printf(n);vo
12、id BreadthFirstSearch1(MGraph G) /无向图、无向网广度优先遍历int i,j,k,visited20,t=1; /i,j为计数器，visited20为标志符用于表示是否已经访问过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)for(j=0;jG.vexnum;+j)/不断以行循环在遇到符合条件时打印，每打印出一个就让t加，把指针指
13、向新的项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,无向图:2,无向网:3):n);9scanf (%d,&G.kind);switch(G.kind)case 2: CreateUDG(G);break;ca
14、se 3: CreateUDN(G);break;default: return ERROR;/CreateGraphvoid Display(MGraph G)/输出图的邻接矩阵int i,j;printf(该图的邻接矩阵为：n);for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)printf(%d ,G.arcsij.adj);printf(n);/* main.cpp */#includeGraph.hvoid main()int i;MGraph G;CreateGraph(G);DepthFirstSearch1(G);BreadthFirstSea
15、rch1(G);Display(G);scanf(%d,&i);1、程序开始运行时输出：显示：请输入无向图 G的顶点数:输入：510显示：请输入无向图 G的边数:输入：6显示：请输入无向图G的弧是否含相关信息（是：1，否：0）:输入：0显示：请输入 5个顶点的值(1 个字符，空格隔开):输入：1 2 3 4 5显示：请输入%d 条边的顶点 1 顶点 2(以空格作为间隔):输入：1 2 1 4 2 3 2 5 3 4 3 5显示：深度优先遍历开始：1 2 3 4 5广度优先遍历开始：1 2 4 3 5该图的邻接矩阵为：0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0请输入任意键退出2、程序运行结果如图：
