2-深度优先遍历以邻接表存储的图-实验报告

数据结构与算法分析实验报告一、实验目的本次实验旨在通过实际操作和分析，深入理解数据结构和算法的基本概念、原理和应用，提高解决实际问题的能力，培养逻辑思维和编程技巧。

二、实验环境本次实验使用的编程语言为 Python，使用的开发工具为 PyCharm。

操作系统为 Windows 10。

三、实验内容（一）线性表的实现与操作1、顺序表的实现使用数组实现顺序表，包括插入、删除、查找等基本操作。

通过实验，理解了顺序表在内存中的存储方式以及其操作的时间复杂度。

2、链表的实现实现了单向链表和双向链表，对链表的节点插入、删除和遍历进行了实践。

体会到链表在动态内存管理和灵活操作方面的优势。

（二）栈和队列的应用1、栈的实现与应用用数组和链表分别实现栈，并通过表达式求值的例子，展示了栈在计算中的作用。

2、队列的实现与应用实现了顺序队列和循环队列，通过模拟银行排队的场景，理解了队列的先进先出特性。

（三）树和二叉树1、二叉树的遍历实现了先序、中序和后序遍历算法，并对不同遍历方式的结果进行了分析和比较。

2、二叉搜索树的操作构建了二叉搜索树，实现了插入、删除和查找操作，了解了其在数据快速查找和排序中的应用。

（四）图的表示与遍历1、邻接矩阵和邻接表表示图分别用邻接矩阵和邻接表来表示图，并比较了它们在存储空间和操作效率上的差异。

2、图的深度优先遍历和广度优先遍历实现了两种遍历算法，并通过对实际图结构的遍历，理解了它们的应用场景和特点。

（五）排序算法的性能比较1、常见排序算法的实现实现了冒泡排序、插入排序、选择排序、快速排序和归并排序等常见的排序算法。

2、算法性能分析通过对不同规模的数据进行排序实验，比较了各种排序算法的时间复杂度和空间复杂度。

四、实验过程及结果（一）线性表1、顺序表在顺序表的插入操作中，如果在表头插入元素，需要将后面的元素依次向后移动一位，时间复杂度为 O(n)。

删除操作同理，在表头删除元素时，时间复杂度也为 O(n)。

一．实验目的熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。

二．实验原理深度优先搜索遍历是树的先根遍历的推广。

假设初始状态时图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有与v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

图的邻接表的存储表示：#define MAX_VERTEX_NUM 20#define MAXNAME 10typedef char VertexType[MAXNAME];typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;}ArcNode;typedef struct VNode{VertexType data;ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{AdjList vertices;int vexnum,arcnum;int kind;}ALGraph;三．实验内容编写LocateVex函数，Create函数，print函数，main函数，输入要构造的图的相关信息，得到其邻接表并输出显示。

四。

实验步骤1）结构体定义,预定义，全局变量定义。

#include"stdio.h"#include"stdlib.h"#include"string.h"#define FALSE 0#define TRUE 1#define MAX 20typedef int Boolean;#define MAX_VERTEX_NUM 20#define MAXNAME 10typedef char VertexType[MAXNAME];typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;}ArcNode;typedef struct VNode{VertexType data;ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{AdjList vertices;int vexnum,arcnum;int kind;}ALGraph;ALGraph G;Boolean visited[MAX];int degree[MAX_VERTEX_NUM];//定义一个数组求每一个顶点的总度数（无向图）或出度（有向图）。

c语言邻接表的深度优先遍历深度优先遍历（Depth First Search，DFS）是一种常用的图遍历算法，适用于有向图或无向图。

在深度优先遍历算法中，从图中的某个节点开始，沿着一条路径走到底，直到无法再继续下去，然后回溯到上一个节点，再选择另一条路径继续遍历，直到所有节点都被访问过为止。

邻接表是一种常用的图的存储方式，它使用一个数组来存储图的所有顶点，每个顶点对应一个链表，链表中存储了该顶点的所有邻接点。

邻接表的优点是可以节省存储空间，适用于稀疏图；缺点是查找某个顶点的邻接点时需要遍历链表，效率较低。

深度优先遍历邻接表的实现可以采用递归或者非递归的方式。

下面以递归方式为例，介绍深度优先遍历邻接表的算法实现。

我们需要定义一个辅助数组visited，用来标记每个顶点是否被访问过。

初始时，visited数组所有元素均为false。

接下来，我们从某个起始顶点开始进行递归遍历。

具体的递归函数可以定义如下：```cvoid dfs(int v) {visited[v] = true; // 标记当前顶点为已访问// 输出当前顶点的值或进行其他操作printf("%d ", v);// 遍历当前顶点的邻接点for (Node* p = adjList[v]; p != NULL; p = p->next) {if (!visited[p->vertex]) {dfs(p->vertex); // 递归遍历邻接点}}}```在dfs函数中，首先将当前顶点标记为已访问，并输出其值。

然后遍历当前顶点的邻接点，如果邻接点未被访问过，则递归调用dfs 函数进行遍历。

我们可以从任意一个未被访问的顶点开始调用dfs函数进行深度优先遍历：```cvoid dfsTraversal() {for (int i = 0; i < numVertices; i++) {if (!visited[i]) {dfs(i); // 从未被访问的顶点开始深度优先遍历}}}```在dfsTraversal函数中，我们遍历所有顶点，如果某个顶点未被访问过，则调用dfs函数进行深度优先遍历。

实验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。

-实验三、图的遍历操作一、目的掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储构造；掌握DFS及BFS对图的遍历操作；了解图构造在人工智能、工程等领域的广泛应用。

二、要求采用邻接矩阵和邻接链表作为图的存储构造，完成有向图和无向图的DFS 和BFS操作。

三、DFS和BFS 的根本思想深度优先搜索法DFS的根本思想：从图G中*个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，……依次继续。

如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。

直到图中所有的顶点都被访问。

广度优先算法BFS的根本思想：从图G中*个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，……，Vt；再依次访问与V1，V2，……，Vt相邻的起且未被访问过的的所有顶点。

如此继续，直到访问完图中的所有顶点。

四、例如程序1．邻接矩阵作为存储构造的程序例如#include"stdio.h"#include"stdlib.h"#define Ma*Verte*Num 100 //定义最大顶点数typedef struct{char ve*s[Ma*Verte*Num]; //顶点表int edges[Ma*Verte*Num][Ma*Verte*Num]; //邻接矩阵，可看作边表int n,e; //图中的顶点数n和边数e}MGraph; //用邻接矩阵表示的图的类型//=========建立邻接矩阵=======void CreatMGraph(MGraph *G){int i,j,k;char a;printf("Input Verte*Num(n) and EdgesNum(e): ");scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数scanf("%c",&a);printf("Input Verte* string:");for(i=0;i<G->n;i++){scanf("%c",&a);G->ve*s[i]=a; //读入顶点信息，建立顶点表}for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0; //初始化邻接矩阵printf("Input edges,Creat Adjacency Matri*\n");for(k=0;k<G->e;k++) { //读入e条边，建立邻接矩阵 scanf("%d%d",&i,&j); //输入边〔Vi，Vj〕的顶点序号G->edges[i][j]=1;G->edges[j][i]=1; //假设为无向图，矩阵为对称矩阵；假设建立有向图，去掉该条语句}}//=========定义标志向量，为全局变量=======typedef enum{FALSE,TRUE} Boolean;Boolean visited[Ma*Verte*Num];//========DFS：深度优先遍历的递归算法======void DFSM(MGraph *G,int i){ //以Vi为出发点对邻接矩阵表示的图G进展DFS搜索，邻接矩阵是0，1矩阵 int j;printf("%c",G->ve*s[i]); //访问顶点Vivisited[i]=TRUE; //置已访问标志for(j=0;j<G->n;j++) //依次搜索Vi的邻接点if(G->edges[i][j]==1 && ! visited[j])DFSM(G,j); //〔Vi，Vj〕∈E，且Vj未访问过，故Vj为新出发点}void DFS(MGraph *G){int i;for(i=0;i<G->n;i++)visited[i]=FALSE; //标志向量初始化for(i=0;i<G->n;i++)if(!visited[i]) //Vi未访问过DFSM(G,i); //以Vi为源点开场DFS搜索}//===========BFS：广度优先遍历=======void BFS(MGraph *G,int k){ //以Vk为源点对用邻接矩阵表示的图G进展广度优先搜索 int i,j,f=0,r=0;int cq[Ma*Verte*Num]; //定义队列for(i=0;i<G->n;i++)visited[i]=FALSE; //标志向量初始化for(i=0;i<G->n;i++)cq[i]=-1; //队列初始化printf("%c",G->ve*s[k]); //访问源点Vkvisited[k]=TRUE;cq[r]=k; //Vk已访问，将其入队。

哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目名称：图的搜索与应用实验题目：图的深度和广度搜索与拓扑排序设计成绩报告成绩指导老师一、实验目的1.掌握图的邻接表的存储形式。

2.熟练掌握图的搜索策略，包括深度优先搜索与广度优先搜索算法。

3.掌握有向图的拓扑排序的方法。

二、实验要求及实验环境实验要求：1.以邻接表的形式存储图。

2.给出图的深度优先搜索算法与广度优先搜索算法。

3.应用搜索算法求出有向图的拓扑排序。

实验环境：寝室+机房+编程软件（NetBeans IDE 6.9.1）。

三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）数据类型定义：template <class T>class Node {//定义边public:int adjvex;//定义顶点所对应的序号Node *next;//指向下一顶点的指针int weight;//边的权重};template <class T>class Vnode {public:T vertex;Node<T> *firstedge;};template <class T>class Algraph {public:Vnode<T> adjlist[Max];int n;int e;int mark[Max];int Indegree[Max];};template<class T>class Function {public://创建有向图邻接表void CreatNalgraph(Algraph<T>*G);//创建无向图邻接表void CreatAlgraph(Algraph<T> *G);//深度优先递归搜索void DFSM(Algraph<T>*G, int i);void DFS(Algraph<T>* G);//广度优先搜索void BFS(Algraph<T>* G);void BFSM(Algraph<T>* G, int i);//有向图的拓扑排序void Topsort(Algraph<T>*G);/得到某个顶点内容所对应的数组序号int Judge(Algraph<T>* G, T name); };主程序流程图：程序开始调用关系：主函数调用五个函数 CreatNalgraph(G)//创建有向图 DFS(G) //深度优先搜索 BFS(G) //广度优先搜索 Topsort(G) //有向图拓扑排序 CreatAlgraph(G) //创建无向图其中 CreatNalgraph(G) 调用Judge(Algraph<T>* G, T name)函数；DFS(G)调用DFSM(Algraph<T>* G , int i)函数；BFS(G) 调用BFSM(Algraph<T>* G, int k)函数；CreatAlgraph(G) 调选择图的类型无向图有向图深 度 优 先 搜 索广度优先搜索 深 度 优 先 搜 索 广度优先搜索拓 扑 排 序程序结束用Judge(Algraph<T>* G, T name)函数。

一、实验背景数据结构是计算机科学中一个重要的基础学科，它研究如何有效地组织和存储数据，并实现对数据的检索、插入、删除等操作。

为了更好地理解数据结构的概念和原理，我们进行了一次数据结构实训实验，通过实际操作来加深对数据结构的认识。

二、实验目的1. 掌握常见数据结构（如线性表、栈、队列、树、图等）的定义、特点及操作方法。

2. 熟练运用数据结构解决实际问题，提高算法设计能力。

3. 培养团队合作精神，提高实验报告撰写能力。

三、实验内容本次实验主要包括以下内容：1. 线性表（1）实现线性表的顺序存储和链式存储。

（2）实现线性表的插入、删除、查找等操作。

2. 栈与队列（1）实现栈的顺序存储和链式存储。

（2）实现栈的入栈、出栈、判断栈空等操作。

（3）实现队列的顺序存储和链式存储。

（4）实现队列的入队、出队、判断队空等操作。

3. 树与图（1）实现二叉树的顺序存储和链式存储。

（2）实现二叉树的遍历、查找、插入、删除等操作。

（3）实现图的邻接矩阵和邻接表存储。

（4）实现图的深度优先遍历和广度优先遍历。

4. 算法设计与应用（1）实现冒泡排序、选择排序、插入排序等基本排序算法。

（2）实现二分查找算法。

（3）设计并实现一个简单的学生成绩管理系统。

四、实验步骤1. 熟悉实验要求，明确实验目的和内容。

2. 编写代码实现实验内容，对每个数据结构进行测试。

3. 对实验结果进行分析，总结实验过程中的问题和经验。

4. 撰写实验报告，包括实验目的、内容、步骤、结果分析等。

五、实验结果与分析1. 线性表（1）顺序存储的线性表实现简单，但插入和删除操作效率较低。

（2）链式存储的线性表插入和删除操作效率较高，但存储空间占用较大。

2. 栈与队列（1）栈和队列的顺序存储和链式存储实现简单，但顺序存储空间利用率较低。

（2）栈和队列的入栈、出队、判断空等操作实现简单，但需要考虑数据结构的边界条件。

3. 树与图（1）二叉树和图的存储结构实现复杂，但能够有效地表示和处理数据。

HUNAN UNIVERSITY数据结构实验报告题目：图的遍历问题学生姓名梁天学生学号************专业班级计科1403指导老师夏艳日期2016.05.14背景网络蜘蛛即Web Spider，是一个很形象的名字。

把互联网比喻成一个蜘蛛网，那么Spider 就是在网上爬来爬去的蜘蛛。

网络蜘蛛是通过网页的链接地址来寻找网页，从网站某一个页面（通常是首页）开始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。

如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。

这样看来，网络蜘蛛就是一个爬行程序，一个抓取网页的程序。

在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先（如下面这张简单化的网页连接模型图所示，其中A为起点也就是蜘蛛索引的起点）。

深度优先顾名思义就是让网络蜘蛛尽量的在抓取网页时往网页更深层次的挖掘进去讲究的是深度!也泛指: 网络蜘蛛将会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接! 则访问的节点顺序为==> A --> B --> E --> H --> I --> C --> D --> F --> K --> L --> G。

深度爬行的优点是:网络蜘蛛程序在设计的时候相对比较容易些；缺点是每次爬行一层总要向"蜘蛛老家" 数据库访问一下。

问问老总有必要还要爬下一层吗! 爬一层问一次.... 如果一个蜘蛛不管3721不断往下爬很可能迷路更有可能爬到国外的网站去，不仅增加了系统数据的复杂度更是增加的服务器的负担。

广度优先在这里的定义就是层爬行，即一层一层的爬行，按照层的分布与布局去索引处理与抓取网页。

则访问的节点顺序为==> A --> B --> C --> D --> E --> F --> G --> H --> I--> K --> L。

实现图的遍历算法实验报告实现图的遍历算法实验报告⼀实验题⽬: 实现图的遍历算法⼆实验要求:2.1:（1）建⽴如图（p126 8.1）所⽰的有向图 G 的邻接矩阵，并输出之（2）由有向图G的邻接矩阵产⽣邻接表，并输出之（3）再由（2）的邻接表产⽣对应的邻接矩阵，并输出之2.2 （1）输出如图8.1所⽰的有向图G从顶点0开始的深度优先遍历序列（递归算法）（2）输出如图8.1所⽰的有向图G从顶点0开始的深度优先遍历序列（⾮递归算法）（3）输出如图8.1所⽰的有向图G从顶点0开始的⼴度优先遍历序列三实验内容:3.1 图的抽象数据类型:ADT Graph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：R={VR}VR={|v,w∈V且P(v,w)，表⽰从v到w的弧，谓词P(v,w)定义了弧的意义或信息}基本操作：CreateGraph( &G, V, VR )初始条件：V是图的顶点集，VR是图中弧的集合。

操作结果：按V和VR的定义构造图G。

DestroyGraph( &G )初始条件：图G存在。

操作结果：销毁图G。

LocateVex( G, u )初始条件：图G存在，u和G中顶点有相同特征。

操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。

GetVex( G, v )初始条件：图G存在，v是G中某个顶点。

操作结果：返回v的值。

PutVex( &G, v, value )初始条件：图G存在，v是G中某个顶点。

初始条件：图G存在，v是G中某个顶点。

操作结果：返回v的第⼀个邻接顶点。

若顶点在G中没有邻接顶点，则返回“空”。

NextAdjVex( G, v, w )初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。

操作结果：返回v的（相对于w的）下⼀个邻接顶点。

若w是v 的最后⼀个邻接点，则返回“空”。

InsertVex( &G, v )初始条件：图G存在，v和图中顶点有相同特征。

数据结构图的遍历实验报告篇一：【数据结构】图的存储和遍历实验报告《数据结构B》实验报告系计算机与电子专业级班姓名学号XX年1 0 月9日1. 上机题目：图的存储和遍历2. 详细设计#include#define GRAPHMAX 10#define FALSE 0#define TRUE 1#define error printf#define QueueSize 30typedef struct{char vexs[GRAPHMAX];int edges[GRAPHMAX][GRAPHMAX];int n,e;}MGraph;int visited[10];typedef struct{int front,rear,count;int data[QueueSize];}CirQueue;void InitQueue(CirQueue *Q) {Q->front=Q->rear=0;Q->count=0;}int QueueEmpty(CirQueue *Q){return Q->count=QueueSize;}int QueueFull(CirQueue *Q){return Q->count==QueueSize;}void EnQueue(CirQueue *Q,int x) { if(QueueFull(Q)) error("Queue overflow");文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持else{ Q->count++;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize;}}int DeQueue(CirQueue *Q){int temp;if(QueueEmpty(Q)){ error("Queue underflow");return NULL;}else{ temp=Q->data[Q->front]; Q->count--;Q->front=(Q->front+1)%QueueSize;return temp;}}void CreateMGraph(MGraph *G){int i,j,k;char ch1,ch2;printf("\n\t\t 请输入定点数，边数并按回车 (格式如：3，4)：");scanf("%d,%d", &(G->n),&(G->e));for(i=0;in;i++){ getchar();printf("\n\t\t 请输入第%d个定点数并按回车：",i+1);scanf("%c",&(G->vexs[i]));}for(i=0;in;i++)for(j=0;jn;j++)G->edges[i][j]=0;for(k=0;ke;k++){ getchar();printf("\n\t\t 请输入第%d条边的顶点序号 (格式如：i,j )：",k+1);scanf("%c,%c",&ch1,&ch2);for(i=0;ch1!=G->vexs[i];i++);for(j=0;ch2!=G->vexs[j];j++);G->edges[i][j]=1;}}void DFSM(MGraph *G,int i){int j;printf("\n\t\t 深 度 优 列： %c\n",G->vexs[i]);visited[i]=TRUE;for(j=0;jn;j++)if(G->edges[i][j]==1 &&////////////////DFSM(G,j);} void BFSM(MGraph *G,int k){ int i,j;CirQueue Q;InitQueue(&Q);printf("\n\t\t 广 度 优列： %c\n",G->vexs[k]);visited[k]=TRUE;EnQueue(&Q,k); while(!QueueEmpty(&Q)){ i=DeQueue(&Q);先遍历序 visited[j]!=1)先遍历序for(j=0;jn;j++)if(G->edges[i][j]==1 && visited[j]!=1) { visited[j]=TRUE;EnQueue(&Q,j);}}}void DFSTraverseM(MGraph *G) {int i;for(i=0;in;i++)visited[i]=FALSE;for(i=0;in;i++)if(!visited[i]) DFSM(G,i);}void BFSTraverseM(MGraph *G) {int i;for(i=0;in;i++) visited[i]=FALSE;for(i=0;in;i++)if(!visited[i]) BFSM(G,i);}void main(){MGraph *G,a;char ch1;int i,j,ch2;G=&a;printf("\n\t\t 建立一个有向图的邻接矩阵表示\n"); CreateMGraph(G);printf("\n\t\t 已建立一个有向图的邻接矩阵存储\n"); for(i=0;in;i++){ printf("\n\t\t");for(j=0;jn;j++)printf("%5d",G->edges[i][j]);}getchar();ch1='y';while(ch1=='y'||ch1=='Y'){ printf("\n");printf("\n\t\t 图的存储与遍历");("\n\t\t** ******************************");printf("\n\t\t*1 ---- 更新邻接矩阵*"); printf("\n\t\t*2 ---- 深度优先遍历*"); printf("\n\t\t*3 ---- 广度优先遍历*"); printf("\n\t\t*0 ---- 退出*");printf("\n\t\t** ******************************");}} printf("\n\t\t 请选择菜单号 ( 0 ---------------- 3) "); scanf("%d",&ch2); getchar(); switch(ch2) { case1:CreateMGraph(G); printf("\n\t\t 图的邻接矩阵存储建立完成\n");break; case 2:DFSTraverseM(G);break; case3:BFSTraverseM(G);break; case 0:ch1='n';break;default:printf("\n\t\t 输出错误！清重新输入！"); }3. 调试分析（1）调试过程中主要遇到哪些问题？是如何解决的？由于实习之初对邻接表的存储结构了解不是很清楚，所以在运行出了一个小错误，即在输出邻接表时，每个结点都少了一个邻接点。