【数据结构】图的存储和遍历实验报告

数据结构实验报告图的遍历一、实验目的本实验旨在通过实践的方式学习图的遍历算法，掌握图的深度优先搜索（DFS）和广度优先搜索（BFS）的实现方法，加深对数据结构中图的理解。

二、实验步骤1. 创建图的数据结构首先，我们需要创建一个图的数据结构，以方便后续的操作。

图可以使用邻接矩阵或邻接表来表示，这里我们选择使用邻接矩阵。

class Graph:def__init__(self, num_vertices):self.num_vertices = num_verticesself.adj_matrix = [[0] * num_vertices for _ in range(num_vertic es)]def add_edge(self, v1, v2):self.adj_matrix[v1][v2] =1self.adj_matrix[v2][v1] =1def get_adjacent_vertices(self, v):adjacent_vertices = []for i in range(self.num_vertices):if self.adj_matrix[v][i] ==1:adjacent_vertices.append(i)return adjacent_vertices2. 深度优先搜索（DFS）DFS是一种遍历图的算法，其基本思想是从图的某一顶点开始，沿着一条路径一直走到最后，然后返回尚未访问过的顶点继续遍历，直到所有顶点都被访问过为止。

def dfs(graph, start_vertex):visited = [False] * graph.num_verticesstack = [start_vertex]while stack:vertex = stack.pop()if not visited[vertex]:print(vertex)visited[vertex] =Truefor neighbor in graph.get_adjacent_vertices(vertex):if not visited[neighbor]:stack.append(neighbor)3. 广度优先搜索（BFS）BFS同样是一种遍历图的算法，其基本思想是从图的某一顶点开始，首先访问其所有邻接点，然后再依次访问邻接点的邻接点，直到所有顶点都被访问过为止。

这是最后提交的文档资料格式，必须包含几个部分完成要求不少于50页。

《数据结构》课程设计题目图的存储与遍历学生姓名指导教师学院专业班级完成时间目录（要求自动生成）第一章课程设计目的 (2)第二章课程设计内容和要求 (2)第三章课程设计分析 (3)第四章算法描述 (4)第五章源代码 (8)第六章运行结果分析 (13)第七章结束语 (15)第八章参考文献 (15)第一章课程设计目的本学期我们对《数据结构》这门课程进行了学习。

这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。

这次课程设计不但要求实习者掌握《数据结构》中的各方面知识，还要求实习者具备一定的C语言基础和编程能力。

具体说来，这次课程设计主要有两大方面目的。

一是让实习者通过实习掌握《数据结构》中的知识。

对于《图的存储与遍历》这一课题来说，所要求掌握的数据结构知识主要有：图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现。

二是通过实习巩固并提高实习者的C语言知识，并初步了解Visual C++的知识，提高其编程能力与专业水平。

第二章课程设计内容和要求2.1课程设计内容该课题要求以邻接表的方式存储图，输出邻接表，并要求实现图的深度、广度两种遍历。

2.1.1图的邻接表的建立与输出对任意给定的图（顶点数和边数自定），并且对有向图与无向图都应进行讨论，根据邻接表的存储结构建立图的邻接表并输出之。

尽量用图形化的方式输出邻接表。

2.1.2 图的遍历的实现图的遍历包括图的广度优先遍历与深度优先遍历。

对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。

首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。

并以队列是否为空作为循环控制条件。

对于深度优先遍历则采用递归或非递归算法来实现。

一、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。

二、实验内容与实验步骤题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。

基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。

测试数据：如图所示题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。

基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。

测试数据：如图所示三、附录：#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define M 5typedef struct node⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=010*******010101000100010A{int vex[M];int edge[M][M];int n,e;}Graph;typedef struct Node{int vertex;struct Node *next;}edgenode;typedef struct{int vex;edgenode *first;}Vexnode;Graph GA;Vexnode GL[M];Graph CreateGA(){int i,j,k;printf("请输入图的顶点数n及边数e:");scanf("%d,%d",&GA.n,&GA.e);printf("请输入顶点信息:");for(i=0;i<GA.n;i++)scanf("%d",&GA.vex[i]);printf("请输入边所对应的两顶点序号:");for(k=0;k<GA.e;k++){scanf("%d,%d",&i,&j);GA.edge[i][j]=1;}return GA;}Vexnode CreateGL(){int i,j,k,n,e;edgenode *p;printf("请输入顶点数n及边数e:");scanf("%d,%d",&n,&e);printf("请输入顶点信息:");for(i=0;i<n;i++){scanf("%d",&GL[i].vex);GL[i].first=NULL;}printf("请输入边所对应的两顶点序号:");for(k=0;k<e;k++){scanf("%d,%d",&i,&j);p=(edgenode*)malloc(sizeof(edgenode));p->vertex=j;p->next=GL[i].first;GL[i].first=p;}return GL[M];}void DFS1(Graph GA,int v,int visited[]){int i;printf("%3d\n",GA.vex[v]);visited[v]=1;for(i=0;i<GA.n;i++)if(GA.edge[v][i]!=0&&visited[i]==0)DFS1(GA,i,visited);}void traver1(Graph GA){int i;static int visited[M];for(i=0;i<GA.n;i++)visited[i]=0;for(i=0;i<GA.n;i++)if(visited[i]==0)DFS1(GA,i,visited);}void BFS1(Graph GA,int v,int visited[]){ int Q[M],f,r;int i,k;f=r=-1;printf("%3d\n",GA.vex[v]); visited[v]=1;r++; Q[r]=v;while(f!=r){ f++; k=Q[f];for(i=0;i<GA.n;i++)if(GA.edge[k][i]!=0&&visited[i]==0){ printf("%3d\n",GA.vex[i]); visited[i]=1; r++; Q[r]=i; } }}void DFS2(Vexnode GL[],int v,int visited[]){ int k;edgenode *p;printf("%3d\n",GL[v].vex);visited[v]=1;p=GL[v].first;while(p!=NULL){ k=p->vertex;if(visited[k]==0)DFS2(GL,k,visited);p=p->next;}}void traver2(Vexnode GL[],int n){int i;static int visited[M];for(i=0;i<n;i++)visited[i]=0;for(i=0;i<n;i++)if(visited[i]==0)DFS2(GL,i,visited);}void BFS2(Vexnode GL[],int v,int visited[]){ int Q[M],f,r;int i,k;edgenode *p;f=r=-1;printf("%3d\n",GL[v].vex);visited[v]=1;r++; Q[r]=v;while(f!=r){ f++; k=Q[f];p=GL[k].first;while(p!=NULL){ i=p->vertex;if(visited[i]==0){ printf("%3d\n",GL[i].vex); visited[i]=1; r++; Q[r]=i; }p=p->next;}}}void GAss(){int v,j,t=1;static int visited[M];while(t){printf(" |**************操作菜单****************|\n");printf(" |***********1.创建邻接矩阵************|\n");printf(" |***********2.DFS ************|\n");printf(" |***********3.BFS ************|\n");printf(" |***********4.退出************|\n");printf("Please input a number from 1 to 4 :");scanf("%d",&j);switch(j){ case 1: CreateGA();break;case 2: traver1(GA);break;case 3: for(v=0;v<GA.n;v++)if(visited[v]==0)BFS1(GA,v,visited);break;case 4: t=0;}}}void GLss(){int j,n,v,t=1;static int visited[M];while(t){printf(" |**************操作菜单****************|\n");printf(" |***********1.创建邻接表************|\n");printf(" |***********2.DFS ************|\n");printf(" |***********3.BFS ************|\n");printf(" |***********4.退出************|\n");printf("Please input a number from 1 to 4 :");scanf("%d",&j);switch(j){ case 1: CreateGL();break;case 2: printf("请输入顶点数n:");scanf("%d",&n);traver2(GL,n);break;case 3: for(v=0;v<M;v++)if(visited[v]==0)BFS2(GL,v,visited);break;case 4: t=0;}}}void main(){int j,t=1;while(t){printf(" |**************操作菜单****************|\n");printf(" |***********1.创建邻接矩阵************|\n");printf(" |***********2.创建邻接表************|\n");printf(" |***********3.退出************|\n");printf("Please input a number from 1 to 3 :");scanf("%d",&j);switch(j){ case 1: GAss();break;case 2: GLss();break;case 3: t=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。

数据结构实验报告实验：图的遍历一、实验目的：1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表2、掌握图的构造方法3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法4、掌握图的深度优先遍历和广度优先原理二、实验内容：1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。

2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图3、深度优先遍历第一步中构造的图G，输出得到的节点序列4、广度优先遍历第一部中构造的图G，输出得到的节点序列三、实验要求：1、无向图中的相关信息要从终端以正确的方式输入；2、具体的输入和输出格式不限；3、算法要具有较好的健壮性，对错误操作要做适当处理；4、程序算法作简短的文字注释。

四、程序实现及结果：1、邻接矩阵：#include <stdio.h>#include <malloc.h>#define VERTEX_MAX 30#define MAXSIZE 20typedef struct{intarcs[VERTEX_MAX][VERTEX_MAX] ;int vexnum,arcnum;} MGraph; void creat_MGraph1(MGraph *g) { int i,j,k;int n,m;printf("请输入顶点数和边数:");scanf("%d%d",&n,&m);g->vexnum=n;g->arcnum=m;for (i=0;i<n;i++)for (j=0;j<n;j++)g->arcs[i][j]=0;while(1){printf("请输入一条边的两个顶点：\n");scanf("%d%d",&i,&j);if(i==-1 || j==-1)break;else if(i==j || i>=n || j>=n){printf("输入错误,请重新输入！\n");}else{g->arcs[i][j]=1;g->arcs[j][i]=1;}}}void printMG(MGraph *g) {int i,j;for (i=0;i<g->vexnum;i++){for (j=0;j<g->vexnum;j++)printf(" %d",g->arcs[i][j]);printf("\n");}printf("\n");}main(){int i,j;int fg;MGraph *g1;g1=(MGraph*)malloc(sizeof(MGraph));printf("1:创建无向图的邻接矩阵\n\n");creat_MGraph1(g1);printf("\n此图的邻接矩阵为：\n"); printMG(g1);}2、邻接链表:#include<stdio.h>#include<malloc.h>#define MAX_SIZE 10typedef struct node{int vertex;struct node *next;}node,adjlist[MAX_SIZE];adjlist g;int visited[MAX_SIZE+1];int que[MAX_SIZE+1];void creat(){int n,e;int i;int start,end;node *p,*q,*pp,*qq;printf("输入无向图的顶点数和边数:");scanf("%d%d",&n,&e);for(i = 1; i <= n ; i++){visited[i] = 0;g[i].vertex = i;g[i].next = NULL;}printf("依次输入边:\n");for(i = 1; i <= e ; i++){scanf("%d%d",&start,&end);p=(node *)malloc(sizeof(node));p->vertex = end;p->next = NULL;q = &g[start];while(q->next)q = q->next;q->next = p;p1=(node*)malloc(sizeof(node));p1->vertex = start;p1->next = NULL;q1 = &g[end];while(qq->next)q1 = q1->next;q1->next = p1;}}void bfs(int vi){int front,rear,v;node *p;front =0;rear = 1;visited[vi] = 1;que[0] = vi;printf("%d ",vi);while(front != rear){v = que[front];p = g[v].next;while(p){if(!visited[p->vertex]){visited[p->vertex]= 1;printf("%d",p->vertex);que[rear++] = p->vertex;}p = p->next;}front++;}}int main(){creat();bfs(1);printf("\n");return 0;}五．实验心得与体会：(1)通过这次实验，使我基本上掌握了图的存储和遍历，让我弄清楚了如何用邻接矩阵和邻接链表对图进行存储(2)深度优先遍历和广度优先遍历都有着各自的优点，通过程序逐步调试，可以慢慢的理解这两种遍历方法的内涵和巧妙之处。

问题描述：若用有向网表示网页的链接网络，其中顶点表示某个网页，有向弧表示网页之间的链接关系。

试设计一个网络蜘蛛系统，分别以广度优先和深度优先的策略抓取网页。

一、需求分析：1．本程序要求采用利用图实现广度优先搜索。

2．首先输入顶点的数量，然后是各顶点对应的字母，再输入各条弧（权值都置为1）。

3．在Dos界面输出从首个顶点开始的广度优先遍历序列。

4．测试数据输入输入顶点数和弧数:8 9输入8个顶点.输入顶点0:a输入顶点1:b输入顶点2:c输入顶点3:d输入顶点4:e输入顶点5:f输入顶点6:g输入顶点7:h输入9条弧.输入弧0:a b 1输入弧1:b d 1输入弧2:b e 1输入弧3:d h 1输入弧4:e h 1输入弧5:a c 1输入弧6:c f 1输入弧7:c g 1输入弧8:f g 1输出广度优先遍历: a b d h e c f g深度优先遍历: a b c d e f g h二、概要设计：抽象数据类型：图的定义：ADT Graph {数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：R={VR}VR={<v,w>|v,w∈v且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息}基本操作P：CreateGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合操作结果：按V和VR的定义构造图GFirstAdjV ex(G,v)初始条件：图G存在,v是G中某个顶点操作结果：返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回“空”Next AdjV ex(G,v,w)初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点操作结果：返回v的（相对于w的）下一个邻接顶点，若w是v的最后一个邻接点，则返回“空”visit(G, k)初始条件：图G存在操作结果：访问图G中的第K个节点Locate(G, c)初始条件：图G存在操作结果：访问图G中的c顶点DFS(G, v)初始条件：图G存在操作结果：以图G中的第v个节点为起点深度优先访问图GBFS(G)初始条件：图G存在操作结果：广度优先访问图G} ADT Graph算法的基本思想：（1）图的特点是没有首尾之分，所以算法的参数要指定访问的第一个顶点。

数据结构实验报告--图
数据结构实验报告--图
1、实验目的
本实验主要旨在通过实践操作，深入理解图这种数据结构的基本概念、性质和基本操作，掌握图的存储结构与常见算法。

2、实验环境
本次实验使用编程语言C++，在Windows平台下进行开发和运行。

3、实验内容
3.1 图的定义与基本概念
在本章中，我们将介绍图的基本概念，包括有向图与无向图、顶点与边、度与入度出度、连通性等。

3.2 图的存储结构
在本章中，我们将介绍图的几种存储结构，包括邻接矩阵、邻接表和十字链表，以及它们的优缺点和适用场景。

3.3 图的遍历
在本章中，我们将介绍图的两种常用的遍历算法，即深度优先搜索（DFS）和广度优先搜索（BFS），并分别给出它们的实现代码和应用场景。

3.4 最短路径
在本章中，我们将介绍图的最短路径问题，包括单源最短路径和全源最短路径。

我们将使用Dijkstra算法和Floyd-Warshall算法来解决这些问题，并给出它们的实现代码和应用场景。

3.5 最小树
在本章中，我们将介绍图的最小树问题，即找到一棵树使得树上的边的权值之和最小。

我们将使用Prim算法和Kruskal算法来解决这个问题，并给出它们的实现代码和应用场景。

4、实验步骤和结果
在本章中，我们将详细介绍实验的具体步骤，并给出实验结果的详细分析和说明。

5、实验总结
在本章中，我们将对整个实验进行总结，总结实验中遇到的问题、解决方案和经验教训。

6、附件
本实验报告所涉及的附件包括实验代码和运行结果的截图。

7、法律名词及注释
本文所涉及的法律名词和注释详见附件中的相关文件。

实验五图的存储与遍历1、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(dfs)和广度优先遍历（BFS）操作的实现。

2、实验预备知识（1）图的存储结构：邻接矩阵表示法和邻接表表示法。

邻接矩阵表示法除了要用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组来存储顶点信息，另外还有图的顶点数和边数。

邻接表表示法类似于树的孩子链表表示法。

（2）图的遍历方法有深度优先遍历（Depth－First Traersal）和广度优先遍历（Breadth－First Traversal），简称 DFS和BFS。

DFS对图遍历时尽可能先对纵深方向进行搜索；BFS是类似于树的按层次遍历。

3、实验内容题目1对以邻接矩阵为存储结构的图进行 DFS和 BFS遍历(1) 问题描述：以邻接矩阵为图的存储结构，实现图的DFS和BFS遍历。

(2) 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS和BFS序列。

(3) 测试数据：如图4．18所示。

(4) 实现提示：图的DFS遍历可通过递归调用或用栈来实现。

其思想是：只要当前结点未访问过，就访问该结点，沿着其一条分支深入下去，每深入一个未访问过的结点，就访问这个结点，然后从这个结点继续进行DFS遍历。

在这一过程中，若深入时遇到一个已访问过的结点，则查找是否有与这个结点相邻的下一个未访问过的结点。

若有则继续深人，否则将退回到这个结点的前一个结点，再找下一个相邻的本访问过的结点，……如此进行下去，直到所有的结点都被访问过。

BFS遍历可利用队列来帮助实现，也可以用栈。

实现方法与二叉树的层次遍历类似。

题目2对以邻接表为存储结构的图进行DFS和BFS遍历(1) 问题描述：以邻接表为存储结构，实现图的DFS和BFS遍历。

(2) 基本要求：建立一个图的邻接表存储，输出顶点的一种DFS和BFS序列。

(3) 测试数据：如图4.19所示：(4) 实现提示：以邻接表为存储结构的图的DFS和BFS算法的实现思想与以邻接矩阵为存储结构的实现是一样的。

武汉东湖学院
实验报告
学院：计算机科学学院专业计算机科学与技术2016年11月18日
姓名付磊学号42
班级计科一班指导老师吴佳芬
课程名称数据结构成
绩
实验名称图的存储结构和遍历
1．实验目的
（1）了解邻接矩阵存储法和邻接表存储法的实现过程。

（2）了解图的深度优先遍历和广度优先遍历的实现过程。

2．实验内容
1. 采用图的邻接矩阵存储方法，实现下图的邻接矩阵存储，并输出该矩阵.
2. 设计一个将第1小题中的邻接矩阵转换为邻接表的算法，并设计一个在屏幕上显示邻接表的算法
3. 实现基于第2小题中邻接表的深度优先遍历算法，并输出遍历序列
4. 实现基于第2小题中邻接表的广度优先遍历算法，并输出遍历序列
3．实验环境
Visual C++ 6.0
4．实验方法和步骤（含设计）
我们通过二维数组中的值来表示图中节点与节点的关系。

通过上图可知，其邻接矩阵示意图为如下：
V0 v1 v2 v3 v4 v5
V0 0 1 0 1 0 1
V1 1 0 1 1 1 0
V2 0 1 0 0 1 0
V3 1 1 0 0 1 1
V4 0 1 1 1 0 0
V5 1 0 0 1 0 0
此时的“1”表示这两个节点有关系，“0”表示这两个节点无关系。

我们通过邻接表来在计算机中存储图时，其邻接表存储图如下：
}。

实验项目名称：图的遍历一、实验目的应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。

二、实验内容问题描述：建立有向图，并用深度优先搜索和广度优先搜素。

输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。

三、实验仪器与设备计算机，Code::Blocks。

四、实验原理用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。

五、实验程序及结果#define INFINITY 10000 /* 无穷大*/#defi ne MAX_VERTEX_NUM 40#defi ne MAX 40#i nclude<stdlib.h>#i nclude<stdio.h>#in clude<c oni o.h>#i nclude<stri ng.h>typedef struct ArCell{int adj;}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{ char n ame[20];实验项目名称：图的遍历}in fotype;typedef struct{ in fotype vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vex nu m,arc num;}MGraph;int LocateVex(MGraph *G,char* v){ int c = -1,i;for(i=0;i<G->vex nu m;i++)if(strcmp(v,G->vexs[i]. name)==0){ c=i; break;}return c;}MGraph * CreatUDN(MGraph *G)〃初始化图，接受用户输入{int i,j,k,w;char v1[20],v2[20];printf("请输入图的顶点数，弧数:");sca nf("%d%d",&G->vex num,&G->arc num);printf("结点名字:\n");for(i=0;i<G->vex nu m;i++){prin tf("No.%d:",i+1);sca nf("%s",G->vexs[i]. name);}for(i=0;i<G->vex nu m;i++)for(j=0;j<G->vex nu m;j++)G->arcs[i][j].adj=INFINITY;printf("请输入一条边依附的两个顶点和权值:\n");for(k=0;k<G->arc nu m;k++){printf("第%d 条边:\n",k+1);printf("起始结点:");sca nf("%s",v1);printf("结束结点:");sca nf("%s",v2);//printf(” 边的权值:");//sca nf("%d",&w);i=LocateVex(G,v1); j=LocateVex(G,v2);if(i>=0&&j>=0){//G->arcs[i][j].adj=w;G->arcs[j][i]=G->arcs[i][j];}}return G;}int FirstAdjVex(MGraph *G ,int v){int i;if(v<=0 && v<G->vex num){ //v 合理for(i=0;i<G->vex nu m;i++)if(G->arcs[v][i].adj!=INFINITY)return i;} return -1;} void VisitFu nc(MGraph *G ,int v){printf("%s ",G->vexs[v].name);}int NextAdjVex(MGraph *G ,int v,int w){int k;if(v>=0 && v<G->vex num && w>=0 && w<G->vex num)//v,w 合理{for( k=w+1;k<G->vex nu m;k++)if(G->arcs[v][k].adj!=INFINITY)return k;}return -1;}in t visited[MAX];void DFS(MGraph *G,int v)〃从第v个顶点出发递归地深度优先遍历图G {int w;visited[v]=1;VisitFunc(G,v);//访问第v个结点for(w=FirstAdjVex(G ,v);w>=O;w=NextAdjVex(G ,v,w))if(!visited[w]){DFS(Gw);prin tf("%d ",G->arcs[v][w]);}}void DFSTraverse(MGraph *G,char *s)//深度优先遍历{in t v,k;for(v=O;v<G->vex num ;v++)visited[v]=O;k=LocateVex(Gs);if(k>=0&&k<G->vex num){for(v=k;v>=0;v__){if(!visited[v])DFS(Gv);}for(v=k+1;v<G->vex nu m;v++)if(!visited[v])DFS(Gv);}}typedef struct Qnode{int vex num;struct Qnode *n ext;}QNode,*QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}Lin kQueue;int Ini tQueue(Li nkQueue *Q){Q->fro nt=Q->rear=(QueuePtr)malloc(sizeof(QNode));if(!Q->fro nt)exit(O);Q->fro nt-> next=NULL;return 1;}void En Queue(L in kQueue *Q,i nt a ){QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(0);p->vex num=a;p-> next=NULL;Q->rear- >n ext=p;Q->rear=p;}int DeQueue(L in kQueue *Q,int *v){ QueuePtr p;if(Q->fr on t==Q->rear){printf("结点不存在!\n");exit(0);}p=Q->fr ont->n ext;*v=p->vex num;Q->front->n ext=p->n ext;if(Q->rear==p)Q->fro nt=Q->rear;return *v;}int QueueEmpty(L in kQueue *Q){if(Q->rear==Q->fro nt)return 0;return 1;}int Visited[MAX];void BFSTraverse(MGraph *G,char *str)〃广度优先遍历{int w,u,v,k;Lin kQueue Q,q; for(v=0;v<G->vex num ;v++) Visited[v]=O; Ini tQueue(&Q);I nitQueue(&q); k=LocateVex(Gstr);for(v=k;v>=0;v__) if(!Visited[v]){Visited[v]=1;VisitFu nc(G,v);EnQueue(&Q,v);//v 入队while(!QueueEmpty(&Q)){DeQueue(&Q,&u);〃出队for(w=FirstAdjVex(G ,u);w>=0;w=NextAdjVex(G ,u,w)) if(!Visited[w]) {Visited[w]=1;VisitFu nc(G,v);En Queue(&Q,w);}}}for(v=k+1;v<G->vex nu m;v++)if(!Visited[v]){Visited[v]=1;VisitFu nc(G,v);EnQueue(&Q,v);//v 入队while(!QueueEmpty(&Q)){DeQueue(&Q,&u);〃出队for(w=FirstAdjVex(G ,u);w>=0;w=NextAdjVex(G ,u,w)) if(!Visited[w]) {Visited[w]=1;VisitFu nc(G,v);En Queue(&Q,w);}}}}void mai n(){MGraph *G,b;char v[10];G=CreatUDN (&b);printf("请输入起始结点名称："); sea nf("%s",v);printf("\n深度优先遍历:\n");DFSTraverse(Qv)；printf("\n广度优先遍历:\n");BFSTraverse(Qv)； geteh();}六、实验总结实验要求输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。

数据结构实验报告图的存储数据结构图实验报告一、实验目的和要求（1）掌握图的相关概念，包括图，有向图，无向图，完全图，子图，连通图，度，入度，出度，简单回路和环等定义。

（2）重点掌握图的各种存储结构，包括邻接矩阵和邻接表等。

（3）重点掌握图的基本运算，包括创建图，输出图，深度优先遍历，广度优先遍历等。

（4）掌握图的其他运算，包括最小生成树，最短路径，拓扑排序和关键路径等算法。

（5）灵活运用图这种数据结构解决一些综合应用问题。

二、实验内容和方法(1)实验内容：1、编写一个程序algo8-1.cpp，实现不带权图和带权图的邻接矩阵与邻接表的相互转换算法、输出邻接矩阵与邻接表的算法，并在此基础上设计一个程序exp8-1.cpp实现如下功能：①建立如图1所示的有向图G的邻接矩阵，并输出；②由有向图G的邻接矩阵产生邻接表，并输出；③再由②的邻接表产生对应的邻接矩阵，并输出。

图12、编写一个程序algo8-2.cpp，实现图的遍历运算，并在此基础上设计一个程序exp8-2.cpp完成如下功能：①输出图1所示的有向图G从顶点0开始的深度优先遍历序列（递归算法）；②输出图1所示的有向图G从顶点0开始的深度优先遍历序列（非递归算法）；③输出图1所示的有向图G从顶点0开始的广度优先遍历序列。

3、设计一个程序exp8-3.cpp,采用邻接表存储图，并输出图8.1（a）中从指定顶点1出发的所有深度优先遍历序列。

(2)实验方法：1、综合运用课本所学的知识，用不同的算法实现在不同的程序功能。

2、结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。

3、根据实验内容，编译程序。

三、实验环境：Windows 7，Visual C++6.0三、实验过程描述文件graph.h中定义了图的邻接矩阵表示类型和邻接表表示类型，该头文件在以下三个实验中都会使用到。

其代码如下：#ifndef GRAPH_H_INCLUDED#define GRAPH_H_INCLUDEDtypedef int InfoType;#define MAXV 100 //最大顶点个数#define INF 32767 //INF表示无限大//以下定义邻接矩阵类型typedef struct{int no;InfoType info;}VertexType;typedef struct{int edges[MAXV][MAXV];int n,e;VertexType vexs[MAXV];}MGraph;//以下定义邻接表类型typedef struct ANode{int adjvex;struct ANode* nextarc;InfoType info;}ArcNode;typedef int Vertex;typedef struct VNode{Vertex data;实验①源程序。

数据结构图实验报告数据结构图实验报告引言：数据结构是计算机科学中非常重要的一个概念，它用于存储和组织数据，使得数据的操作更加高效和方便。

图是一种常见的数据结构，它由节点和边组成，用于表示各种实际问题中的关系和连接。

本实验旨在通过实际操作，深入理解图的基本概念和常见操作。

实验目的：1. 理解图的基本概念和特性；2. 掌握图的存储结构和基本操作；3. 实现图的遍历算法；4. 分析图的应用场景。

实验过程：1. 图的存储结构：在本次实验中，我们选择邻接矩阵来存储图。

邻接矩阵是一个二维数组，其中行和列分别表示图中的节点，数组元素表示节点之间的边的关系。

具体而言，如果节点i和节点j之间存在边，则邻接矩阵中的第i行第j列元素为1；否则为0。

2. 图的基本操作：在实验中，我们实现了以下几个图的基本操作：- 添加节点：通过向邻接矩阵中添加一行一列，并设置对应的边的关系，来添加一个节点；- 添加边：通过修改邻接矩阵中对应元素的值，来添加一条边；- 删除节点：通过删除邻接矩阵中对应行和列，并更新其他节点的索引，来删除一个节点；- 删除边：通过修改邻接矩阵中对应元素的值，来删除一条边；- 查找节点：通过遍历邻接矩阵，找到对应节点的索引；- 查找边：通过遍历邻接矩阵，找到对应边的关系。

3. 图的遍历算法：在实验中，我们实现了深度优先搜索（DFS）和广度优先搜索（BFS）两种图的遍历算法。

DFS通过递归的方式，先访问当前节点，再依次访问相邻节点，直到所有节点都被访问。

BFS则通过队列的方式，先访问当前节点，再依次访问当前节点的相邻节点，直到所有节点都被访问。

实验结果：通过实验，我们成功实现了图的存储结构和基本操作，并且正确实现了DFS和BFS两种遍历算法。

我们对不同规模的图进行了测试，并分析了算法的时间复杂度。

实验结果表明，邻接矩阵的存储结构在添加和删除节点时的时间复杂度较高，而在查找节点和边时的时间复杂度较低。

DFS和BFS的时间复杂度都为O(V+E)，其中V表示节点数，E表示边数。

题目：图的遍历的实现完成日期：2011.12.22一、需求分析1.本演示程序中，输入的数据类型均为整型数据，不允许输入字符等其他数据类型，且需要按照提示内容进行输入，成对的关系数据必须在所建立的图中已经存在对应的结点。

2.演示程序以用户和计算机的对话方式执行，在计算机终端上显示的提示信息的说明下，按照要求输入数据，运算结果在其后显示。

3.本程序实现分别基于邻接矩阵和邻接表存储结构的有、无向图，有、无向网的建立和遍历。

遍历分DFS和BFS两种算法，并分别以递归和非递归形式实现。

4.测试数据：（1）无向图结点数4 弧数3 结点：1 2 3 4 结点关系：1 2；1 3；2 4（2）有向图结点数6 弧数6 结点：1 2 3 4 5 6 结点关系：1 2；1 3；2 4；3 5；3 6；2 5 二、概要设计为实现上述程序功能，图的存储结构分为邻接矩阵和邻接表两种。

遍历过程中借助了栈和队列的存储结构。

1.邻接矩阵存储结构的图定义：ADT mgraph{数据对象V：V是具有相同特性的的数据元素的集合，成为顶点集。

数据关系R:R=｛VR｝VR={ <v,w>| v,w є V且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息}基本操作P：locatevex(G, mes)；初始条件：图G存在，mes和G中顶点有相同的特征。

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

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

操作结果：创建无向图。

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

操作结果：创建有向图。

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

操作结果：创建无向网。

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

操作结果：创建有向网。

DFS(G,v)；初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。

数据结构实验报告图的遍历数据结构实验报告：图的遍历引言在计算机科学中，图是一种重要的数据结构，它由节点和边组成，用于表示不同实体之间的关系。

图的遍历是一种重要的操作，它可以帮助我们了解图中节点之间的连接关系，以及找到特定节点的路径。

在本实验中，我们将讨论图的遍历算法，并通过实验验证其正确性和效率。

深度优先搜索（DFS）深度优先搜索是一种常用的图遍历算法，它通过递归或栈的方式来遍历图中的节点。

在实验中，我们实现了深度优先搜索算法，并对其进行了测试。

实验结果表明，深度优先搜索算法能够正确地遍历图中的所有节点，并找到指定节点的路径。

此外，我们还对算法的时间复杂度进行了分析，验证了其在不同规模图上的性能表现。

广度优先搜索（BFS）广度优先搜索是另一种常用的图遍历算法，它通过队列的方式来遍历图中的节点。

在实验中，我们也实现了广度优先搜索算法，并对其进行了测试。

实验结果显示，广度优先搜索算法同样能够正确地遍历图中的所有节点，并找到指定节点的路径。

我们还对算法的时间复杂度进行了分析，发现其在不同规模图上的性能表现与深度优先搜索算法相近。

实验结论通过本次实验，我们深入了解了图的遍历算法，并验证了其在不同规模图上的正确性和效率。

我们发现深度优先搜索和广度优先搜索算法都能够很好地应用于图的遍历操作，且在不同情况下都有良好的性能表现。

这些算法的实现和测试为我们进一步深入研究图的相关问题提供了重要的基础。

总结图的遍历是图算法中的重要操作，它为我们提供了了解图结构和节点之间关系的重要手段。

本次实验中，我们实现并测试了深度优先搜索和广度优先搜索算法，验证了它们的正确性和效率。

我们相信这些算法的研究和应用将为我们在图相关问题的研究中提供重要的帮助。

数据结构图的遍历实验报告篇一：【数据结构】图的存储和遍历实验报告《数据结构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");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 && visited[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);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图的存储与遍历 ");printf("\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) { case 1:CreateMGraph(G); printf("\n\t\t图的邻接矩阵存储建立完成\n");break; case 2:DFSTraverseM(G);break; case 3:BFSTraverseM(G);break; case 0:ch1='n';break; default:printf("\n\t\t输出错误！清重新输入！"); }3. 调试分析（1）调试过程中主要遇到哪些问题？是如何解决的？由于实习之初对邻接表的存储结构了解不是很清楚，所以在运行出了一个小错误，即在输出邻接表时，每个结点都少了一个邻接点。

武汉东湖学院
实验报告
学院：计算机科学学院专业计算机科学与技术2016年11月18日
姓名付磊学号2015040131042
班级计科一班指导老师吴佳芬
课程名称数据结构成
绩
实验名称图的存储结构和遍历
1．实验目的
（1）了解邻接矩阵存储法和邻接表存储法的实现过程。

（2）了解图的深度优先遍历和广度优先遍历的实现过程。

2．实验内容
1. 采用图的邻接矩阵存储方法，实现下图的邻接矩阵存储，并输出该矩阵.
2. 设计一个将第1小题中的邻接矩阵转换为邻接表的算法，并设计一个在屏幕上显示邻接表的算法
3. 实现基于第2小题中邻接表的深度优先遍历算法，并输出遍历序列
4. 实现基于第2小题中邻接表的广度优先遍历算法，并输出遍历序列
3．实验环境
Visual C++ 6.0
4．实验方法和步骤（含设计）
我们通过二维数组中的值来表示图中节点与节点的关系。

通过上图可知，其邻接矩阵示意图为如下：
V0 v1 v2 v3 v4 v5
V0 0 1 0 1 0 1
V1 1 0 1 1 1 0
V2 0 1 0 0 1 0
V3 1 1 0 0 1 1
V4 0 1 1 1 0 0
V5 1 0 0 1 0 0
此时的“1”表示这两个节点有关系，“0”表示这两个节点无关系。

我们通过邻接表来在计算机中存储图时，其邻接表存储图如下：
}。

图的遍历数据结构实验报告图的遍历数据结构实验报告1. 实验目的本实验旨在通过使用图的遍历算法，深入理解图的数据结构以及相关算法的运行原理。

2. 实验背景图是一种非线性的数据结构，由顶点和边组成。

图的遍历是指按照某种规则，从图中的一个顶点出发，访问图中的所有顶点且仅访问一次的过程。

3. 实验环境本次实验使用的操作系统为Windows 10，编程语言为Python3.8，使用的图数据结构库为NetworkX。

4. 实验步骤4.1 创建图首先，我们使用NetworkX库创建一个有向图。

通过调用add_nodes_from()方法添加顶点，并调用add_edge()方法添加边，构建图的结构。

4.2 深度优先搜索（DFS）接下来，我们使用深度优先搜索算法来遍历这个图。

深度优先搜索是一种递归的遍历法，从一个顶点开始，沿着深度方向访问图中的顶点，直到不能继续深入为止。

4.3 广度优先搜索（BFS）然后，我们使用广度优先搜索算法来遍历这个图。

广度优先搜索是一种先访问离起始顶点最近的顶点的遍历法，从一个顶点开始，依次访问与之相邻的顶点，直到访问完所有的顶点为止。

5. 实验结果我们根据深度优先搜索和广度优先搜索算法，分别得到了图的遍历结果。

通过实验可以观察到每种遍历方式所访问的顶点顺序以及所需的时间复杂度。

6. 结论通过本次实验，我们了解了图的遍历数据结构及相关算法的原理和实现方式。

深度优先搜索和广度优先搜索算法适用于不同的场景，可以根据具体情况选择合适的算法进行图的遍历。

附件：无附录：本文所涉及的法律名词及注释：- 图：由结点和边组成的非线性数据结构。

- 顶点：图中的每个元素都称为顶点，也称为结点。

- 边：顶点之间的连接关系称为边。

图的遍历实验报告数据结构实验报告计科101 冯康 201000814128实验图的基本操作一、实验目的及要求1、使学生1、使学生可以巩固所学的有关图的基本知识。

2、熟练掌握图的存储结构。

3、熟练掌握图的两种遍历算法。

基本要求:以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。

以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。

二、算法描述[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历。

【测试数据】由学生依据软件工程的测试技术自己确定。

四、实验报告要求1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

编程思路:深度优先算法:计算机程序的一种编制原理，就是在一个问题出现多种可以实现的方法和技术的时候，应该优先选择哪个更合适的，也是一种普遍的逻辑思想，此种思想在运算的过程中，用到计算机程序的一种递归的思想。

度优先搜索算法:又称广度优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。

Dijkstra单源最短路径算法和Prim 最小生成树算法都采用了和宽度优先搜索类似的思想。

其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。

换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。

以临接链表作为存储结构，结合其存储特点和上面两种算法思想，给出两种遍历步骤: (1)既然图中没有确定的开始顶点，那么可从图中任一顶点出发，不妨按编号的顺序，先从编号小的顶点开始。

中原工学院计算机学院打印时间:2016-4-30 上午 00:04 第1页共4页数据结构实验报告计科101 冯康 201000814128(2)要遍历到图中所有顶点，只需多次调用从某一顶点出发遍历图的算法。

所以，下面只考虑从某一顶点出发遍历图的问题。

(3)为了在遍历过程中便于区分顶点是否已经被访问，设置一个访问标志数组visited[n]，n为图中顶点的个数，其初值为0，当被访问过后，其值被置为1。