《数据结构》上机实验报告—有向图的邻接表的建立及遍历

数据结构实验五---图的遍历及其应用实现实验五图的遍历及其应用实现一、实验目的1．熟悉图常用的存储结构。

2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。

3．会用图的遍历解决简单的实际问题。

二、实验内容[题目] ：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。

该程序包括图类型以及每一种操作的具体的函数定义和主函数。

三、实验步骤（一）、数据结构与核心算法的设计描述：本实验主要在于图的基本操作，关键是图的两种遍历，仔细分析图的遍历的特点，不难发现，其符合递归的特点，因此可以采用递归的方法遍历。

本实验图的存储结构主要采用邻接表，总共分为四个模块：图的创建、位置的查找、深度优先遍历、广度优先遍历。

以下是头文件中数据结构的设计和相关函数的声明：#include#include#include#nclude#define OVERFLOW -2#define MAX_VERTEX_NUM 50 //最大顶点数#define MAXQSIZE 100# define OK 1typedef int VRType;typedef int InfoType;typedef int QElemType;typedef enum{DG,DN,UDG,UDN}GraphKind;typedef struct ArcNode // 弧结点{int adjvex; //邻接点域，存放与Vi邻接的点在表头数组中的位置struct ArcNode *nextarc; //链域指向vi的下一条边或弧的结点，InfoType *info; //定义与弧相关的权值，无权则为0 }ArcNode;typedef struct VNode //表头结点{char vexdata; //存放顶点信息struct ArcNode *firstarc; //指示第一个邻接点}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{ //图的结构定义AdjList vertices; //顶点向量int vexnum, arcnum; //vexnum为顶点数arcnum为弧或边的个数GraphKind kind; // 图的种类标志}MGraph;typedef struct Queue //构建循环队列{QElemType *base;int front;int rear;}Queue;void CreateGraph(MGraph &G); //图的创建void DFSTraverse(MGraph &G) ; //深度优先遍历void BFSTraverse(MGraph &G); //广度优先遍历int LocateVex(MGraph &G, char &v);//查找顶点v的位置（二）、函数调用及主函数设计void main(){int x;MGraph G;CreateGraph(G);cout<<"创建图成功!"<<endl;< p="">cout<<"1 深度优先搜索"<<endl<<"2 p="" 广度优先搜索"<<endl;<="">cin>>x;if(x==1){DFSTraverse(G);cout<<"深度优先搜索结束!"<<endl;< p="">}else if(x==2){BFSTraverse(G);cout<<"广度优先搜索结束!"<<endl;< p="">}elsecout<<"输入有误!"<<endl<<"再见!"<<endl;< p="">}（三）、实验总结由于图的基本操作在图这一章节中起着很主要的作用，所以在实验前就对实验做了充分的准备，实验的成功核心在于两种遍历的实现，因此只有充分理解遍历算法的精髓，才能更好的做好实验。

数据结构实验报告图的遍历一、实验目的本实验旨在通过实践的方式学习图的遍历算法，掌握图的深度优先搜索（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同样是一种遍历图的算法，其基本思想是从图的某一顶点开始，首先访问其所有邻接点，然后再依次访问邻接点的邻接点，直到所有顶点都被访问过为止。

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

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

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

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

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

测试数据: 如图所示三、附录:在此贴上调试好的程序。

#include<stdio.h>#include<malloc.h>#include<string.h>#define M 100typedef struct node{char vex[M][2];int edge[M ][ M ];int n,e;}Graph;int visited[M];Graph *Create_Graph(){ Graph *GA;int i,j,k,w;GA=(Graph*)malloc(sizeof(Graph));printf ("请输入矩阵的顶点数和边数(用逗号隔开): \n");scanf("%d,%d",&GA->n,&GA->e);printf ("请输入矩阵顶点信息: \n");for(i = 0;i<GA->n;i++)scanf("%s",&(GA->vex[i][0]),&(GA->vex[i][1]));for (i = 0;i<GA->n;i++)for (j = 0;j<GA->n;j++)GA->edge[i][j] = 0;for (k = 0;k<GA->e;k++){ printf ("请输入第%d条边的顶点位置(i,j)和权值(用逗号隔开): ",k+1);scanf ("%d,%d,%d",&i,&j,&w);GA->edge[i][j] = w;}return(GA);}void dfs(Graph *GA, int v){ int i;printf("%c%c\n",GA->vex[v][0],GA->vex[v][1]);visited[v]=1;for(i=0; i<GA->n; i++)if (GA->edge[v][i]==1 && visited[i]==0) dfs(GA, i);}void traver(Graph *GA){ int i;for(i=0; i<GA->n; i++)visited[i]=0;for(i=0; i<GA->n;i++)if(visited[i]==0)dfs(GA, i);}void bfs( Graph *GA, int v){ int j,k,front=-1,rear=-1;int Q[M];printf("%c%c\n",GA->vex[v][0],GA->vex[v][1]); visited[v]=1;rear=rear+1;Q[rear]=v;while (front!=rear){ front=front+1;k=Q[front];for (j=0; j<GA->n; j++)if (GA->edge[k][j]==1 && visited[j]==0){ printf("%c%c\n",GA->vex[j][0],GA->vex[j][1]);visited[j]=1;rear=rear+1;Q[rear]=j;}}}void traver1(Graph *GA){ int i;for (i=0; i<GA->n;i++)visited[i]=0;for (i=0; i<GA->n; i++)if (visited[i]==0)bfs(GA, i);}typedef struct NODE{ int adjvex;struct NODE *next;}ENode;typedef struct NODE1{ char vex[2];ENode *first;} VexNode;typedef struct FS1{VexNode GL[M];int bian,top;}FS;FS *CreateGL( ){ FS *kk=(FS *)malloc(sizeof(FS));int i,j,k;ENode *s;printf("请输入顶点数和边数(用逗号隔开): \n");scanf("%d,%d",&kk->top, &kk->bian);printf("请输入顶点信息: \n");for (i=0; i<kk->top; i++){ scanf("%s",kk->GL[i].vex);kk->GL[i].first=NULL; }printf("请输入边的信息(i,j): \n");for (k=0;k<kk->bian;k++){ scanf("\n%d,%d",&i,&j);s =(ENode*)malloc(sizeof(ENode));s->adjvex=j;s->next=kk->GL[i].first;kk->GL[i].first =s;}return kk;}void DFS(FS *kk, int v){ ENode *w; int i;printf("%s\n",kk->GL[v].vex); visited[v]=1;w=kk->GL[v].first ;while (w!=NULL){ i=w->adjvex;if (visited[i]==0)DFS(kk,i);w=w->next;}}void TRAVER(FS *kk){ int i;for(i=0; i<kk->top;i++)visited[i]=0;for(i=0; i<kk->top; i++)if(visited[i]==0)DFS(kk, i);}void BFS(FS *kk, int v){ int Q[M], front=-1,rear=-1;ENode *w;int i, k;printf("%s\n",kk->GL[v].vex);visited[v]=1;rear=rear+1; Q[rear]=v;while (front!=rear){ front=front+1;k=Q[front];w=kk->GL[k].first;while(w!=NULL){ i=w->adjvex;if( visited[i]==0){ visited[i]=1; printf("%s",kk->GL[i].vex);rear=rear+1; Q[rear]=i;}w=w->next;}}}void TRAVER1(FS *kk){ int i;for(i=0; i<kk->top;i++) visited[i]=0;for(i=0; i <kk->top;i++)if(visited[i]==0)BFS(kk,i);}int main(){int i=0;Graph *p;FS *q;while(i=1){/*建立菜单*/char jz[30]={"1.创建邻接矩阵"};char jd[30]={"2.邻接矩阵DFS遍历"};char jb[30]={"3.邻接矩阵BFS遍历"};char bg[30]={"4.创建邻接表"};char bd[30]={"5.邻接表DFS遍历"};char bb[30]={"6.邻接表BFS遍历"};char tc[30]={"7.退出"};char mn[30]={"菜单"};int l=strlen(jd);int o=strlen(mn);int m,n;printf("\n");for(m=0;m<=(2*l-o)/2;m++)printf(" ");printf("%s",mn);for(m=0;m<=(2*l-o)/2;m++)printf(" ");printf("\n");for(m=0;m<=2*l;m++)printf("*");printf("\n");printf("* %s *\n* %s*\n* %s *\n* %s *\n* %s *\n* %s *\n* %s*\n",jz,jd,jb,bg,bd,bb,tc);for(m=0;m<=2*l;m++)printf("*");printf("\n");/*选择功能*/printf("请输入所需功能序号: ");scanf("%d",&n);switch(n){case 1: p=Create_Graph();break;case 2: traver(p);break;case 3: traver1(p);break;case 4: q=CreateGL();break;case 5: TRAVER(q);break;case 6: TRAVER1(q);break;case 7: return 0;default:printf("输入功能序号有误！\n");}}return 0;}四、运行结果:在此把运行结果从屏幕上拷下来贴在此五、心得体会:测试数据要注意现实中矩阵是从1开始, 而数组里是从0开始。

数据结构上机报告班级：13 软件工程（本）班学号：姓名：周次：上机时间：一、上机目的：图的遍历；二、上机内容：一）建立一个无向图+遍历+插入（1）以邻接矩阵表示法作为存储结构，从键盘依次输入顶点数、弧数与各弧信息建立一个无向图；（2）对（1）中生成的无向图进行广度优先遍历并打印结果；（3）向（1）中生成的无向图插入一条新边并打印结果；二）建立一个有向图+遍历+插入+删除（1）以邻接表作为图的存储结构，从键盘输入图的顶点与弧的信息建立一个有向图；（2）对（1）中生成的有向图进行深度优先遍历并打印结果；（3）在（1）中生成的有向图中，分别插入与删除一条弧并打印其结果；三、实验要求：(1)程序要添加适当的注释，程序的书写要采用缩进格式。

(2)必须要有操作界面。

(2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。

(3)将本文件改名为：学号后三位+姓名+上机报告10.doc上交。

四．上机结果：给出代码和运行结果截图。

（一）#include<stdio.h>#include<string.h>#include<malloc.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define MAX_NAME 5 /* 顶点字符串的最大长度+1 */#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */#define INFINITY INT_MAX /* 用整型最大值代替∞*/#define MAX_VERTEX_NUM 20 /* 最大顶点个数*/typedef int Boolean;Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */typedef int Status;typedef int VRType;typedef char InfoType;typedef char VertexType[MAX_NAME];typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */typedef struct{VRType adj; /* 顶点关系类型。

数据结构与算法-图的邻接表实验报告课程: 数据结构与算法实验日期: 实验名称: 图的邻接表一、实验目的掌握图的邻接表的创建和遍历二、实验内容必做部分1、给出图的邻接表存储结构的类型定义。

2、设计并实现以邻接表的方式构造一个无向网的算法。

Status CreateUDN(ALGraph &G) 3、设计并实现无向网的输出算法，要求能显示顶点以及顶点之间的邻接关系(方式自定) 4、基于邻接表方式实现:a) int FirstAdjVex(ALGraph G,int v) //返回v的第一个邻接点的下标，若不存在，则返回-1 b) int NextAdjVex(ALGraph G,int v,int w) // 返回v相对于w的下一个邻接点，若不存在，则返回-15、基于邻接表存储结构实现图的深度优先搜索算法。

void DFSTraverse(ALGraph G)6、在主函数中调用上述操作函数。

要求给出至少两组测试数据。

选做部分基于邻接表存储结构实现图的广度优先搜索算法。

三、实验步骤必做部分1、给出图的邻接表存储结构的类型定义。

12、设计并实现以邻接表的方式构造一个无向网的算法。

Status CreateUDN(ALGraph &G)3、设计并实现无向网的输出算法，要求能显示顶点以及顶点之间的邻接关系(方式自定)24、基于邻接表方式实现:a) int FirstAdjVex(ALGraph G,int v) //返回v的第一个邻接点的下标，若不存在，则返回-1b) int NextAdjVex(ALGraph G,int v,int w) // 返回v相对于w的下一个邻接点，若不存在，则返回-135、基于邻接表存储结构实现图的深度优先搜索算法。

void DFSTraverse(ALGraph G)6、在主函数中调用上述操作函数。

要求给出至少两组测试数据。

选做部分基于邻接表存储结构实现图的广度优先搜索算法。

【关键字】实验数据结构图的遍历实验报告篇一：【数据结构】图的保存和遍历实验报告《数据结构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）调试过程中主要遇到哪些问题？是如何解决的？由于实习之初对邻接表的保存结构了解不是很清楚，所以在运行出了一个小错误，即在输出邻接表时，每个结点都少了一个邻接点。

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

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

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

三、实验仪器与设备计算机，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();}六、实验总结实验要求输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。

题目：图的遍历的实现完成日期：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）调试过程中主要遇到哪些问题？是如何解决的？由于实习之初对邻接表的存储结构了解不是很清楚，所以在运行出了一个小错误，即在输出邻接表时，每个结点都少了一个邻接点。

实验八图的表示与遍历一、实验目的1、掌握图的邻接矩阵和邻接表表示2、掌握图的深度优先和广度优先搜索方法3、理解图的应用方法二、实验预习说明以下概念1、深度优先搜索遍历：2、广度优先搜索遍历：3、拓扑排序：4、最小生成树：5、最短路径：三、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果。

#include<stdio.h>#define N 20#define TRUE 1#define FALSE 0int visited[N];typedef struct /*队列的定义*/{int data[N];int front,rear;}queue;typedef struct /*图的邻接矩阵*/{int vexnum,arcnum;char vexs[N];int arcs[N][N];}graph;void createGraph(graph *g); /*建立一个无向图的邻接矩阵*/ void dfs(int i,graph *g); /*从第i个顶点出发深度优先搜索*/ void tdfs(graph *g); /*深度优先搜索整个图*/void bfs(int k,graph *g); /*从第k个顶点广度优先搜索*/ void tbfs(graph *g); /*广度优先搜索整个图*/void init_visit(); /*初始化访问标识数组*/void createGraph(graph *g) /*建立一个无向图的邻接矩阵*/ { int i,j;char v;g->arcnum=0;i=0;printf("输入顶点序列(以#结束)：\n");while((v=getchar())!='#'){g->vexs[i]=v; /*读入顶点信息*/i++;}g->vexnum=i; /*顶点数目*/for(i=0;i<g->vexnum;i++) /*邻接矩阵初始化*/for(j=0;j<g->vexnum;j++)g->arcs[i][j]=0;printf("输入边的信息：\n");scanf("%d,%d",&i,&j); /*读入边i,j*/while(i!=-1) /*读入i,j为－1时结束*/{g->arcs[i][j]=1;g->arcs[j][i]=1;scanf("%d,%d",&i,&j);}}void dfs(int i,graph *g) /*从第i个顶点出发深度优先搜索*/ {int j;printf("%c",g->vexs[i]);visited[i]=TRUE;for(j=0;j<g->vexnum;j++)if((g->arcs[i][j]==1)&&(!visited[j]))dfs(j,g);}void tdfs(graph *g) /*深度优先搜索整个图*/{int i;printf("\n从顶点%C开始深度优先搜索序列：",g->vexs[0]); for(i=0;i<g->vexnum;i++)if(visited[i]!=TRUE)dfs(i,g);}void bfs(int k,graph *g) /*从第k个顶点广度优先搜索*/{int i,j;queue qlist,*q;q=&qlist;q->front=0;printf("%c",g->vexs[k]);visited[k]=TRUE;q->data[q->rear]=k;q->rear=(q->rear+1)%N;while(q->rear!=q->front){i=q->data[q->front];q->front=(q->front+1)%N;for(j=0;j<g->vexnum;j++)if((g->arcs[i][j]==1)&&(!visited[j])){printf("%c",g->vexs[j]);visited[j]=TRUE;q->data[q->rear]=j;q->rear=(q->rear+1)%N;}}}void tbfs(graph *g) /*广度优先搜索整个图*/{int i;printf("\n从顶点%C开始广度优先搜索序列：",g->vexs[0]); for(i=0;i<g->vexnum;i++)if(visited[i]!=TRUE)bfs(i,g);}void init_visit() /*初始化访问标识数组*/{int i;for(i=0;i<N;i++)visited[i]=FALSE;}int main(){graph ga;int i,j;createGraph(&ga);printf("无向图的邻接矩阵：\n");for(i=0;i<ga.vexnum;i++){for(j=0;j<ga.vexnum;j++)printf("%3d",ga.arcs[i][j]);printf("\n");}init_visit();tdfs(&ga);init_visit();tbfs(&ga);return 0;}▪根据右图的结构验证实验，输入：ABCDEFGH#0,10,20,51,31,42,52,63,74,7-1,-1▪运行结果：2.指定从某个顶点开始进行深度优先搜索遍历和广度优先搜索遍历，把结果输出输入结果6 81 55 22 61 44 52 33 64 3输出结果1 4 32 5 6AB CD E F GH12345671 4 5 32 6▪实验小结：输出输入结果#include<stdio.h>定义函数库<stdio.h>便于后面程序中的函数可以被使用；#define N 20定义大写字母N为20是后面程序简洁并且提高运算效率；#define TRUE 1定义TRUE用1表示使得后面输出结果是简洁并且便于理解；#define FALSE 0定义FALSE用1表示使得后面输出结果是简洁并且便于理解；int visited[N];定义访问空间并且定义其大小为N；typedef struct建立队列结构体；{int data[N];初始化int类型数组；int front,rear;定义对头指针和队尾指针；}queue;队列结构建立完成；typedef struct建立矩阵结构体；{int vexnum,arcnum;定义顶点数和边数；char vexs[N];定义顶点数为一维数组；int arcs[N][N];定义边数为二维数组；}graph;void createGraph(graph *g);建立一个无向图的邻接矩阵；void dfs(int i,graph *g);从第i个顶点出发深度优先搜索,dfs表示深度优先搜索；void tdfs(graph *g);深度优先搜索整个图；void bfs(int k,graph *g);从第k个顶点出发广度优先搜索,bfs表示广度优先搜索；void tbfs(graph *g);广度优先搜索整个图；void init_visit();初始化访问标识数组；以上是对邻接矩阵的声明；void createGraph(graph *g)建立一个无向图的邻接矩阵；{int i,j;定义i与j两个整型值；char v;定义v字符变量；g->vexnum=0;g指针引用的顶点初始为0；g->arcnum=0;g指针引用的边数初始为0；i=0;i值初始为0；printf("输入顶点序列（以#结束）：\n");printf()函数可以输出()中的标题提示语；while((v=getchar())!='#')while循环函数{g->vexs[i]=v;引用指针g指向顶点被赋值为v的一维数组；i++;让i值进行自加；}g->vexnum=i;引用指针g指向被赋值为i的顶点,顶点数目；for(i=0;i<g->vexnum;i++)for()使i值初始为0,当i值小于g,引用指针g指向的顶点并且i自加，邻接矩阵初始化；for(j=0;j<g->vexnum;j++)for()使j值初始为0,当j值小于g,引用指针g指向的顶点并且j自加,邻接矩阵初始化；g->arcs[i][j]=0; 引用指针g指向的边数的二维数组将其赋值为0表示没有连接；printf("输入边的信息：\n");提示输入语句；scanf("%d,%d",&i,&j);输入函数输入二个十进制的数字将其存入i与j的两个地址，读入边i,j；while(i!=-1)while循环当i读入i,j为-1时结束；{g->arcs[i][j]=1;引用指针g指向的边数的二维数组将其赋值为1表示有连接；g->arcs[j][i]=1;引用指针g指向的边数的二维数组对应另外点将其赋值为1表示有连接；scanf("%d,%d",&i,&j);输入二个十进制的数值并将其放在i与j两个地址中；}}以上是通广度优先和深度优先搜索遍历输出得到的矩阵；void dfs(int i,graph *g)从第i个顶点出发深度优先搜索（从顶点i出发对图进行dfs遍历）,类似于树的先序遍历；{int j;定义整型量j；printf("%c",g->vexs[i]); 输出单字符指针顶点i；visited[i]=TRUE;修改顶点i的访问标志为TRUE；for(j=0;j<g->vexnum;j++)for()函数循环初始j值为0当j小于g所引用的顶点数值时对j进行自加；if((g->arcs[i][j]==1)&&(!visited[j]))如果同时满足g所引导的边数二维数组的值为1进行访问操作且对i的尚未访问的邻接顶点j递归调用dfs；dfs(j,g);则得到深度搜索的j值与g指针；}void tdfs(graph *g)深度优先搜索整个图；{int i;定义整型数值i；printf("\n从顶点%C开始深度优点搜索序列；”,g->vexs[0]);输出提示标语从顶点%C开始深度优点搜索序列for(i=0;i<g->vexnum;i++)for()循环初始i为0当i值小于指针g所引用的顶点时,对i进行自加进行访问操作；if(visited[i]!=TRUE)判断i的尚未访问的顶点是否被修改为TRUE；dfs(i,g);则得到深度搜索的i值与g指针；}void bfs(int k,graph *g)从第k个顶点出发广度优先搜索（从顶点k出发对图进行bfs遍历），类似于树的按层遍历，算法借助队列；{int i,j;定义两个整型变量i,j；queue qlist,*q;建立一个队列链表和一个指针；q=&qlist;将q赋值于一个链表地址；q->rear=0;q引用为队尾且队尾为空；q->front=0;q引用为队头且队头为空；printf("%c",g->vexs[k]);输出单字符指针顶点k；visited[k]=TRUE;修改顶点k的访问标志为TRUE；q->data[q->rear]=k;q引用为数据类型的队尾指针k；q->rear=(q->rear+1)%N;q引用为队尾的后一位；while(q->rear!=q->front)while循环q引用的队尾指针不等于q引用的队头指针；{i=q->data[q->front];i赋值为q引用为q引用对头指针的数据类型；q->front=(q->front+1)%N;q引用被赋值到下一位的队头指针且对其取余数操作；for(j=0;j<g->vexnum;j++)for()初始j为0当j小于g引用的顶点时对j进行自加便于完成对整的数据的计算；if((g->arcs[i][j]==1)&&(!visited[j]))如果g引用的二维数组的值为1并且对i的尚未访问的邻接顶点j递归调用bfs广度优先操作；{printf("%c",g->vexs[j]);输出g引用的一维数组的单个字符；visited[j]=TRUE;修改顶点访问指针为TRUE；q->data[q->rear]=j;将q引用为队尾指针数据j；q->rear=(q->rear+1)%N;将q引用为下一位队尾指针数据并且对其取余；}}}void tbfs(graph *g)广度优先搜索整个图；{int i;定义一个整型变量i；printf("\n从顶点%C开始广度优先搜索序列；”,g->vexs[0]);输出提示标语并且输出g引用的初始地址；for(i=0;i<g->vexnum;i++)for()循环i初始为0，当i小于顶点项目数时，变量i进行自加；if(visited[i]!=TRUE) 判断i的尚未访问的顶点是否被修改为TRUE递归调用bfs；bfs(i,g);得到i与g的结果遍历完成；}void init_visit()初始化访问标识数组；{int i;定义一个整型变量i；for(i=0;i<N;i++)for()循环初始i为0，当i小于数组所定义的长度时对i进行自加以达到完成整个数组的访问；visited[i]=FALSE;访问i未被访问的顶点；}int main()函数调用提高算法效率；{graph ga;矩阵ga建立声明；int i,j;定义两个整型变量；createGraph(&ga);创建矩阵并且创建了地址ga；printf(“无向图的邻接矩阵:\n”);输出提示语;for(i=0;i<ga.vexnum;i++)for()循环初始变量i为0，当变量i小于矩阵中顶点项目数时对i进行自加； {for(j=0;j<ga.vexnum;j++)for()循环j初始为0开始当j小于矩阵中顶点项目数时对j进行自加； printf("%3d",ga.arcs[i][j]);输出三位整数型数据分别是ga和二维数组中的数值；printf("\n");输出结果}init_visit();访问顶点；tdfs(&ga);深度优先遍历init_visit();访问顶点；tbfs(&ga);广度优先遍历；return 0;返回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. 结论通过本次实验，我们了解了图的遍历数据结构及相关算法的原理和实现方式。

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

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

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

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

《数据结构》实验报告
姓名：学号：
班级：日期：
程序名：
一、上机实验的问题和要求：
要求采用邻接矩阵作为无向图的存储结构，邻接表作为有向图的存储结构，完成无向图和有向图的建立，并对建立好的图进行深度和广度优先遍历。

具体实现要求：
1.通过键盘输入图的顶点和边信息，分别构造一个无向图的邻接矩阵和一个有向图的邻接
表。

2.分别对建立好的两个图进行深度和广度优先遍历，输出相应的遍历序列。

3.统计两个图的连通分量的个数。

二、程序设计的基本思想，原理和算法描述：
（包括程序的结构，数据结构，输入/输出设计，符号名说明等）
三、源程序及注释：
四、运行输出结果：
五、调试和运行程序过程中产生的问题及采取的措施：
六、对算法的程序的讨论、分析，改进设想，其它经验教训：
七、对实验方式、组织、设备、题目的意见和建议：。

图的建立与遍历实验报告------------图的建立与遍历姓名:曹庆松班级:1104学号:1111611512实验日期:2012.10.15报告撰写日期:2012.10.16一、实验目的:1、熟悉图的概念、存储结构和遍历方法。

2、以邻接表为存储结构，掌握无向图的基本操作和实现方法。

3、以邻接表为存储结构，掌握无向图的深度优先遍历的算法实现。

二、实验内容:以邻接表为存储结构，编写程序实现。

1、要求通过键盘输入图的顶点，以及每一条边的两个顶点从而建立无向。

为了简化实验，顶点用数字表示。

2、在以上实验的基础上，实现无向图的深度优先遍历算法。

要求以用户给定的顶点为起始点，显示深度优先遍历的次序。

三、程序代码及结果展示:#include "stdafx.h"#include<stdio.h>#include<stdlib.h>#include <malloc.h>#define MAX_VERTER_NUM 20typedef struct ArcNode{ //表节点int adjvex; //邻接点struct ArcNode *nextarc; //指向下一条弧的指针}ArcNode;typedef struct VNode{ //头结点int data; //定点信息ArcNode * firstarc; //指向第一个依附该顶点的弧的指针}VNode,AdjList[MAX_VERTER_NUM];typedef struct{ //图AdjList vertices; //顶int vexnum,arcnum;//图的顶点数和弧数int Kind;// 图的种类标志}ALGraph;// 对图 G 作深度优先遍历int LocateVex(ALGraph * G,int v) //寻找节点V的位置 { int k,n;for(k=0;k<G->vexnum;k++){ if(G->vertices[k].data==v){n=k;break;}}return n;}int n=1;int visited[MAX_VERTER_NUM]; void DFS(ALGraph *G,int v)//递归调用{ArcNode *p;>vertices[v].firstarc; p=G-if(n<G->vexnum+1){printf(" V%d ",G->vertices[v].data);n++;}visited[v]=1;while(p){if(!visited[p->adjvex])DFS(G,p->adjvex);p=p->nextarc;}}void DFSVisited(ALGraph * G)//深度遍历{int v;int n;printf("请输入遍历的起始的顶点:");scanf("%d",&n);n"); printf("递归深度优先遍历点顺序: \DFS(G,n-1);for(v=0;v<G->vexnum;v++)visited[v]=0;for(v=0;v<G->vexnum;v++)if(!visited[v])DFS(G,v);}void Insertadj(ALGraph * G,int i,int j) //插入邻接点的下标 { ArcNode *a1,*a2;a1=(ArcNode *)malloc(sizeof(ArcNode));a1->adjvex=j;a1->nextarc=NULL;if(G->vertices[i].firstarc==NULL){G->vertices[i].firstarc=a1;}else{a2=G->vertices[i].firstarc;while(a2->nextarc){a2=a2->nextarc;}a2->nextarc=a1;}}void Init_ALGraph(ALGraph * G) //初始化图并建图 { int v,v1,v2,i,j,q,p;int m=0;printf("请输入顶点数:");scanf("%d",&G->vexnum);printf("请输入边数:");scanf("%d",&G->arcnum);for(v=0;v<G->vexnum;v++){printf("顶点 V%d:",(v+1));scanf("%d",&(G->vertices[v].data));>vertices[v].firstarc=NULL; G-}for(v=0;v<G->arcnum;v++) {printf("请输入点点: ");scanf("%d%d",&v1,&v2);i=LocateVex(G,v1); //v1的位置j=LocateVex(G,v2); //v2的位置Insertadj(G,i,j);Insertadj(G,j,i);}}int main(int argc,char **argv) {ALGraph G;Init_ALGraph(&G);//初始化图并建图DFSVisited(&G);//深度优先遍历printf("\n");return 0;}四、实验总结:通过本实验，我对图的存储结构、图的遍历等有了比较深的理解与运用，图的遍历和树的遍历很类似，但是却比树的遍历复杂很多。

实验八、图的邻接表的实现及遍历班级 学号 姓名 指导教师 李红岩一、实验目的理解邻接表类中的生成与遍历算法二、实验内容 AB C DE84443537499563编写代码，创建图的邻接表，并进行遍历，输出该图的邻接表与遍历序列。

1、创建头文件，文件名Link_GP.h//定义图邻接表中单链表结点类型//定义图邻接表中顺序存储空间结点类型//定义图邻接表类//由键盘输入生成图邻接表//纵向优先搜索法遍历图（深度优先）//输出图邻接表2、创建源文件，文件名Link_GP.cpp#include "Link_GP.h"int main(){char d[5]={'A','B','C','D','E'};Link_GP<int, char> g;g. creat_Link_GP(5, d); //由数据文件生成图g 邻接表cout <<"图g 邻接表:" <<endl;g.prt_Link_GP(); //输出图邻接表cout <<"纵向优先搜索法遍历图g:" <<endl;g.dfs_Link_GP(); //纵向优先搜索法遍历图greturn 0;}3、编译、运行，根据提示进行输入创建图的邻接表，要求单链表中各结点次序从小到大排列三、实验报告1、调试运行成功后，记录输出结果2、思考广度优先的遍历方法的实现（可借助队列的思想）3、思考图的邻接矩阵的实现及遍历四、实验体会。