下载文档原格式
1图的遍历问题在实践中常常遇到这样的问题：给定n个点，从任一点出发对所有的点访问一次并且只访问一次。
如果用图中的顶点表示这些点，图中的边表示可能的连接，那么这个问题就可以表示成图的遍历问题，即从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。
图的遍历操作和树的遍历操作功能相似，是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础上。
由于图结构本身的复杂性，所以图的遍历操作也比较复杂，主要表现在以下几个方面：(1) 在图结构中，没有一个确定的首结点，图中任意一个顶点都可以作为第一个被访问的结点。
(2) 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需要考虑如何选取下一个出发点以访问图中其余的连通分量。
(3) 在图结构中，如果有回路存在，那么一个顶点被访问后，有可能沿回路又回到该顶点。
⑷在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。
基于以上分析，图的遍历方法目前有深度优先搜索(DFS)和广度优先搜索(BFS)两种算法。
下面将介绍两种算法的实现思路，分析算法效率并编程实现。
1.1深度优先搜索算法深度优先搜索算法是树的先根遍历的推广，它的实现思想是：从图G的某个顶点V o出发，访问V o,然后选择一个与V o相邻且没被访问过的顶点V i访问，再从V i出发选择一个与V i相邻且未被访问的顶点V j进行访问，依次继续。
如果当前被访问过的顶点的所有邻接顶点都已被访问，贝U退回已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样的方法向前遍历，直到图中所有顶点都被访问。
其递归算法如下：Boolean visited[MAX_VERTEX_NUM]; // 访问标志数组Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数void DFSTraverse (Graph G Status(*Visit)(i nt v)){VisitF unc = Visit;for(v=0; vvG.vex num; ++v)visited[v] = FALSE; //访问标志数组初始化for(v=0; v<G .vex num; ++v)if(!visited[v])DFS(G v); //对尚未访问的顶点调用DFS}void DFS(Graph G int v){ //从第v个顶点出发递归地深度优先遍历图Gvisited[v]=TRUE; VisitFunc(v); // 访问第v 个顶点for(w=FirstAdjVex(G ,v); w>=0;w=NextAdjVex(G ,v,w))//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空(0)。
实验6.1实现图的存储和遍历一，实验目的掌握图的邻接矩阵和邻接表存储以及图的邻接矩阵存储的递归遍历。
二，实验内容6.1实现图的邻接矩阵和邻接表存储编写一个程序，实现图的相关运算，并在此基础上设计一个主程序，完成如下功能：（1）建立如教材图7.9所示的有向图G的邻接矩阵，并输出。
（2）由有向图G的邻接矩阵产生邻接表，并输出。
（3）再由（2）的邻接表产生对应的邻接矩阵，并输出。
6.2 实现图的遍历算法（4）在图G的邻接矩阵存储表示基础上，输出从顶点V1开始的深度优先遍历序列（递归算法）。
（5）利用非递归算法重解任务（4）。
（6）在图G的邻接表存储表示基础上，输出从顶点V1开始的广度优先遍历序列。
三，源代码及结果截图#include<stdio.h>#include<stdlib.h>#include<string.h>#include<iostream.h>#include<malloc.h>#define MAX_VERTEX_NUM 20typedef char VRType;typedef int InfoType; // 存放网的权值typedef char VertexType; // 字符串类型typedef enum{DG,DN,AG,AN}GraphKind; // {有向图,有向网,无向图,无向网}/*建立有向图的邻接矩阵*/typedef struct ArcCell{VRType adj;//VRType是顶点关系类型，对无权图用1或0表示是否相邻;对带权图则为权值类型InfoType *info; //该弧相关信息的指针(可无)}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{VertexType vexs[MAX_VERTEX_NUM];//顶点向量AdjMatrix arcs;//邻接矩阵int vexnum,arcnum;;//图的当前顶点数和弧数GraphKind kind;//图的种类标志}MGraph;/* 顶点在顶点向量中的定位*/int LocateVex(MGraph &M,VRType v1){int i;for(i=0;i<M.vexnum;i++)if(v1==M.vexs[i])return i;return -1;}void CreateGraph(MGraph &M)//建立有向图的邻接矩阵{int i,j,k,w;VRType v1,v2;M.kind=DN;printf("构造有向网:\n");printf("\n输入图的顶点数和边数(以空格作为间隔):");scanf("%d%d",&M.vexnum,&M.arcnum);printf("输入%d个顶点的值(字符):",M.vexnum);getchar();for(i=0;i<M.vexnum;i++) //输入顶点向量{scanf("%c",&M.vexs[i]);}printf("建立邻接矩阵:\n");for(i=0;i<M.vexnum;i++)for(j=0;j<M.vexnum;j++){M.arcs[i][j].adj=0;M.arcs[i][j].info=NULL;}printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");for(k=0;k<M.arcnum;++k)// 构造表结点链表{cin>>w>>v1>>v2;i=LocateVex(M,v1);j=LocateVex(M,v2);M.arcs[i][j].adj=w;}}//按邻接矩阵方式输出有向图void PrintGraph(MGraph M){int i,j;printf("\n输出邻接矩阵:\n");for(i=0; i<M.vexnum; i++){printf("%10c",M.vexs[i]);for(j=0; j<M.vexnum; j++)printf("%2d",M.arcs[i][j].adj);printf("\n");}}// 图的邻接表存储表示typedef struct ArcNode{int adjvex; // 该弧所指向的顶点的位置struct ArcNode *nextarc; // 指向下一条弧的指针InfoType *info; // 网的权值指针）}ArcNode; // 表结点typedef struct VNode{VertexType data; // 顶点信息ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];// 头结点typedef struct{AdjList vertices;int vexnum,arcnum; // 图的当前顶点数和弧数int kind; // 图的种类标志}ALGraph;void CreateMGtoDN(ALGraph &G,MGraph &M){//由有向图M的邻接矩阵产生邻接表int i,j;ArcNode *p;G.kind=M.kind;G.vexnum=M.vexnum;G.arcnum=M.arcnum;for(i=0;i<G.vexnum;++i){//构造表头向量G.vertices[i].data=M.vexs[i];G.vertices[i].firstarc=NULL;//初始化指针}for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j)if(M.arcs[i][j].adj){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G.vertices[i].firstarc;p->info=M.arcs[i][j].info;G.vertices[i].firstarc=p;}}void CreateDNtoMG(MGraph &M,ALGraph &G){ //由邻接表产生对应的邻接矩阵int i,j;ArcNode *p;M.kind=GraphKind(G.kind);M.vexnum=G.vexnum;M.arcnum=G.arcnum;for(i=0;i<M.vexnum;++i)M.vexs[i]=G.vertices[i].data;for(i=0;i<M.vexnum;++i){p=G.vertices[i].firstarc;while(p){M.arcs[i][p->adjvex].adj=1;p=p->nextarc;}//whilefor(j=0;j<M.vexnum;++j)if(M.arcs[i][j].adj!=1)M.arcs[i][j].adj=0;}//for}//输出邻接表void PrintDN(ALGraph G){int i;ArcNode *p;printf("\n输出邻接表：\n");printf("顶点:\n");for(i=0;i<G.vexnum;++i)printf("%2c",G.vertices[i].data);printf("\n弧:\n");for(i=0;i<G.vexnum;++i){p=G.vertices[i].firstarc;while(p){printf("%c→%c(%d)\t",G.vertices[i].data,G.vertices[p->adjvex].data,p->info);p=p->nextarc;}printf("\n");}//for}int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)void(*VisitFunc)(char* v); // 函数变量(全局量)// 从第v个顶点出发递归地深度优先遍历图G。
数据结构课程设计报告设计题目：图的邻接矩阵存储结构院系计算机学院年级x 级学生xxxx学号xxxxxxxxxx指导教师xxxxxxxxx起止时间10-6/10-102013年10月10日目录1 需求分析 (3)2 概要设计 (4)2.1 ADT描述 (4)2.2程序模块结构 (5)2.3各功能模块 (6)3详细设计 (7)3.1类的定义 (7)3.2 初始化 (8)3.3 图的构建操作 (8)3.4 输出操作 (9)3.5 get操作 (9)3.6 插入操作 (10)3.7 删除操作 (10)3.8 求顶点的度操作 (11)3.10 判断连通操作 (12)3.11 主函数 (13)4 调试分析 (16)4.1调试问题 (16)4.2 算法时间复杂度 (16)5用户手册 (16)5.1 主界面 (16)5.2 创建图 (17)5.3插入节点 (17)5.4 深度优先遍历 (17)5.5 求各顶点的度 (18)5.6 输出图 (18)5.7 判断是否连通 (19)5.8 求边的权值 (19)5.9 插入边 (19)5.10 删除边 (20)结论 (20)参考文献 (20)摘要随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构的知识非常难，所以对“数据结构”的课程设计比不可少。
本说明书是对“无向图的邻接矩阵存储结构”课程设计的说明。
首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。
其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。
然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。
再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。
然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。
邻接矩阵和邻接表是图论中用于表示图结构的两种常见方式，而深度遍历和广度遍历则是图论中常用的两种图遍历算法。
本文将从简介、原理和应用三个方面探讨这四个主题。
一、邻接矩阵和邻接表1.邻接矩阵邻接矩阵是一种使用二维数组来表示图中顶点之间关系的方法。
如果图中有n个顶点，那么对应的邻接矩阵就是一个n*n的矩阵，其中元素a[i][j]表示顶点i和顶点j之间是否有边，通常用0和1表示。
邻接矩阵适用于稠密图，其存储结构简单，可以直观地展示图的结构，但对于稀疏图来说可能会造成存储空间的浪费。
2.邻接表邻接表是一种使用链表来表示图中顶点之间关系的方法。
对于图中的每一个顶点，都维护一个相邻顶点的列表，图中所有顶点的列表再组合成一个链表，用于表示整个图的结构。
邻接表适用于稀疏图，其存储结构灵活，可以有效地节省存储空间，但查找任意两个顶点之间的关系可能会比较耗时。
二、深度遍历和广度遍历原理1.深度遍历深度遍历是一种用于遍历或搜索图中节点的算法，其原理是从图的某一顶点出发，沿着一条路径不断向下遍历直到末端，然后回溯到上一个节点继续遍历。
深度遍历使用栈来实现，可以通过递归或迭代来进行。
2.广度遍历广度遍历是一种用于遍历或搜索图中节点的算法，其原理是从图的某一顶点出发，依次访问其所有相邻节点，然后再依次访问这些相邻节点的相邻节点，以此类推。
广度遍历使用队列来实现。
三、深度遍历和广度遍历的应用1.深度遍历的应用深度遍历常用于求解图的连通分量、拓扑排序、解决迷宫问题等。
在连通分量中，深度遍历可以帮助我们找到图中的所有连通分量，并对其进行标记，用于进一步的算法运算。
在拓扑排序中，深度遍历可以帮助我们找到一个合理的顺序，用以处理依赖关系问题。
在解决迷宫问题时，深度遍历可以帮助我们找到一条从起点到终点的路径。
2.广度遍历的应用广度遍历常用于求解最短路径、解决迷宫问题等。
在求解最短路径中，广度遍历可以帮助我们找到起点到终点的最短路径，从而解决了许多实际问题。
邻接矩阵的深度优先遍历算法简介邻接矩阵是一种常见的图存储结构，它使用二维数组来表示图中各个顶点之间的关系。
而深度优先遍历算法是一种常用的图遍历算法，用于遍历和搜索图的各个顶点。
本文将介绍邻接矩阵的深度优先遍历算法，包括其基本思想、实现步骤以及应用场景等内容。
基本思想深度优先遍历算法（Depth-First Search，DFS）是一种针对图和树的遍历算法，它通过从起始顶点开始，逐个探索图中的顶点，并沿着某一条路径一直深入，直到无法继续为止，然后回溯到前一顶点继续探索其它路径，直到所有顶点都被访问过为止。
邻接矩阵是一种常见的图表示方法，它通过一个二维数组来表示图中各个顶点之间的关系。
邻接矩阵中的每个元素表示两个顶点之间是否存在一条边，具体而言，如果顶点i和顶点j之间存在一条边，则邻接矩阵中下标为(i, j)和(j, i)的元素值为1；否则，它们的元素值为0。
邻接矩阵的深度优先遍历算法是通过对邻接矩阵进行遍历，找出与起始顶点相连接的顶点，并依次对这些顶点进行深度优先遍历。
实现步骤邻接矩阵的深度优先遍历算法可以使用递归或迭代的方式来实现。
下面分别介绍这两种实现方法的具体步骤。
递归实现1.创建一个数组visited，用来记录每个顶点是否已被访问过，初始时所有元素都设为0。
2.选择一个起始顶点v，并将visited[v]设置为1，表示该顶点已被访问过。
3.遍历邻接矩阵中与v相连的所有顶点w，如果visited[w]为0，则递归调用深度优先遍历函数，将w作为新的起始顶点。
4.重复步骤3，直到所有顶点都被访问过为止。
迭代实现1.创建一个数组visited，用来记录每个顶点是否已被访问过，初始时所有元素都设为0。
2.创建一个栈，用来存储待访问的顶点。
3.选择一个起始顶点v，并将visited[v]设置为1，表示该顶点已被访问过。
4.将v入栈。
5.当栈不为空时，执行以下操作：–出栈一个顶点u，访问它。
–遍历邻接矩阵中与u相连的所有顶点w，如果visited[w]为0，则将w入栈，并将visited[w]设置为1。
邻接矩阵例题
（原创版）
目录
1.邻接矩阵的定义和作用
2.邻接矩阵的存储方式
3.邻接矩阵的实例分析
4.邻接矩阵的计算方法
5.邻接矩阵在网络分析中的应用
正文
邻接矩阵是一种用于表示有向图或无向图中各个顶点间关系的矩阵。
在图论中，邻接矩阵被广泛应用于表示图的结构，以及进行图的遍历、寻找最短路径等算法。
邻接矩阵的存储方式通常采用二维数组。
对于有向图来说，设图中有n 个顶点，那么邻接矩阵就是一个 n×n 的矩阵。
如果图中的顶点 i 到顶点 j 有边，则矩阵的第 i 行第 j 列（记作 aij）处的元素为 1（如果是有向边），或者对应的边的权（如果是带权边）；如果顶点 i 到顶点 j 没有边，则 aij 为 0。
对于无向图来说，因为顶点 i 到顶点 j 的边和顶点 j 到顶点 i 的边是等价的，所以无向图的邻接矩阵总是对称的。
以一个简单的例子来说明邻接矩阵的计算方法。
假设有一个无向图，有 3 个顶点，分别是 1、2、3，它们之间的边关系是：1 到 2、1 到 3、2 到 3。
那么，这个图的邻接矩阵就是：
1 2 3
1 0 1 1
2 1 0 1
3 1 1 0
在网络分析中，邻接矩阵可以方便地表示网络的结构，并且可以快速进行图的遍历，寻找最短路径等操作。
例如，如果要从顶点 1 到顶点 3 寻找最短路径，可以通过遍历邻接矩阵，依次沿着最短路径前进，直到到达目标顶点。
实验五 图的邻接矩阵存储及遍历一、实验学时 2学时二、背景知识1．图的邻接矩阵存储结构设图G ＝（V ，E ）有 n>=1个顶点，其编号分别为1，2，…，n 。
描述图G 的邻接矩阵为二维数组A[1…n ，1…n]，A 的元素定义为：A []j i ,＝⎩⎨⎧，，01否则）属于）或（若（E ,,i j j i v v v v显然无向图的邻接矩阵一定是对称的。
对于网，其邻接矩阵A 的元素定义为：A []j i ,＝⎪⎩⎪⎨⎧∞=无邻接边到顶点若顶点若为该边上的权有邻接边，到顶点若顶点j i j i w j i w j i j i 0,,2.图的遍历深度优先遍历（DFS ）法：算法步骤：1）初始化：（1）置所有顶点“未访问”标志；（2）打印起始顶点；（3）置起始顶点“已访问”标志；（4）起始顶点进栈。
2）当栈非空时重复做：（1）取栈顶点；（2）如栈顶顶点存在被访问过的邻接顶点，则选择一个顶点做：① 打印该顶点；② 置顶点为“已访问”标志；③ 该顶点进栈；否则，当前栈顶顶点退栈。
3）结束。
广度优先遍历（BFS ）法：算法步骤：1) 初始化：（1）置所有顶点“未访问”标志；（2）打印起始顶点；（3）置起始顶点“已访问”标志；（4）起始顶点入队。
2）当队列非空时重复做：（1）取队首顶点；（2）对与队首顶点邻接的所有未被访问的顶点依次做：① 打印该顶点；② 置顶点为“已访问”标志；③ 该顶点入队；否则，当前队首顶点出队。
3) 结束。
三、目的要求1．掌握图的基本存储方法；2．掌握有关图的操作算法并用高级语言实现；3．熟练掌握图的两种搜索路径的遍历方法。
四、实验内容编写程序实现下图的邻接矩阵表示及其基础上的深度和广度优先遍历。
五、程序实例图的邻接矩阵表示法的C语言描述：#include<stdio.h>#include<conio.h>#include<stdlib.h>#define INFINITY 32767#define MAX_VERTEX_MUN 20int visited[20];typedef struct ArcCell{int adj;char *info;}ArcCell,AdjMatrix[20][20];typedef struct{char vexs[20];AdjMatrix arcs;int vexnum,arcnum;}MGragh;typedef struct QNode{int data;struct QNode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;int InitQueue(LinkQueue &Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(0);Q.front->next=NULL;return 1;}int EnQueue(LinkQueue &Q,int e){QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(0);p->next=NULL;p->data=e;Q.rear->next=p;Q.rear=p;return 1;}int DeQueue(LinkQueue &Q,int e){QueuePtr p;if(Q.front==Q.rear)exit(0);p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);return 1;}int EmptyQueue(LinkQueue Q){if(Q.front==Q.rear)return 1;return 0;}int LocateVex(MGragh G,char v){ int t;for(t=0;t<G.vexnum;t++)if(v==G.vexs[t])return t;return -1;}int FirstAdjVex(MGragh G,char v){ int i,j;i=LocateVex(G,v);if(i==-1)return 0;for(j=0;j<G.vexnum;j++)if(G.arcs[i][j].adj==1)return j;return -1;}int NextAdjVex(MGragh G,char v,char w){int j,i1,i2;i1=LocateVex(G,v);i2=LocateVex(G,w);if(i1==-1||i2==-1||i1==i2)return 0;for(j=i2+1;j<G.vexnum;j++)if(G.arcs[i1][i2].adj==1)return j;return -1;}int Visit(char v){printf("%c",v);return 1;}//构造无向图int CreateUDG(MGragh &G){int v,e,i,j,t;char v1,v2;printf("input the number of the vertices:");scanf("%d",&v);if(v<0)return 0;G.vexnum=v;printf("input the number of the arcs:");scanf("%d",&e);if(e<0)return 0;G.arcnum=e;for(t=0;t<G.vexnum;t++){printf("input the vertice %d 's information",t+1);fflush(stdin);scanf("%c",&G.vexs[t]);}for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}for(t=0;t<G.arcnum;t++){fflush(stdin);printf("input v1 and v2 is information :v1-v2");scanf("%c%*c%c",&v1,&v2);i=LocateVex(G,v1);j=LocateVex(G,v2);if(i==-1||j==-1||i==j)return 0;G.arcs[i][j].adj=G.arcs[j][i].adj=1;}return 1;}int BFSTraverse(MGragh G,int(*Visit)(char v)){LinkQueue Q;int v,w,u;for(v=0;v<G.vexnum;v++)visited[v]=0;InitQueue(Q);for(v=0;v<G.vexnum;v++){if(!visited[v]){visited[v]=1;Visit(G.vexs[v]);EnQueue(Q,v);while(!EmptyQueue(Q)){DeQueue(Q,v);w=FirstAdjVex(G,G.vexs[v]);for(;w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w])) if(!visited[w]){visited[w]=1;Visit(G.vexs[w]);EnQueue(Q,w);}}}}return 1;}void DFS(MGragh G,int v){int w;visited[v]=1;Visit(G.vexs[v]);w=FirstAdjVex(G,G.vexs[v]);for(;w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w])) if(!visited[w])DFS(G,w);}void DFSTraverse(MGragh G){int v;for(v=0;v<G.vexnum;v++)visited[v]=0;for(v=0;v<G.vexnum;v++)if(!visited[v])DFS(G,v);}void main(){MGragh G;printf("create the UND G:\n");if(CreateUDG(G)){printf("output the UDG G in DFS order:");DFSTraverse(G);printf("\n");printf("output the UDG G in BFS order:");BFSTraverse(G,Visit);printf("\n");}}。
