C语言_数据结构_实验7_图的创建与遍历 2

数据结构课程实验报告一、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示, 以及在此两种常用存储方式下深度优先遍历(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开始。

数据结构实验报告实验：图的遍历一、实验目的：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．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。

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

二、需求分析很多问题都是建立在图的遍历的基础上实现的，所以必须有一个程序能够实现将图进行广度和深度遍历，必须对图的所有节点进行访问。

以无向图为例，以无向图的邻接表和邻接矩阵为存储结构，分别实现对图进行广度和深度遍历。

以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应的生成树的边集。

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

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

提示：输入示例上图的顶点和边的信息输入数据为：5 7 DGA B C D EAB AE BC CD DA DB EC四、结构算法模块：typedef struct ArcNode//定义邻接表结构{int adjvex;//该弧所指向的顶点的位置struct ArcNode *nextarc;//指向下一条弧的指针}ArcNode;typedef struct VNode//定义顶点结构类型{char data;//存放顶点信息ArcNode *firstarc;//指向第一条依附于该定点的指针}VNode,Adjlist[MAX_VEX_NUM];typedef struct ALGraph{Adjlist vertices;int vexnum;int arcnum;}ALGraph;五、相关函数设计Create_DG(ALGraph &G)//创建一个有向图图的邻接链表表示DFSTraverse(ALGraph G,int vex)//对图G做深度优先遍历BFSTraverse(ALGraph G)//有向图的广度遍历，从第v个顶点出发，v为顶点下标locatevex(ALGraph G,char v)//图的基本操作，寻找顶点位置的下标DFS(ALGraph G,int v)//从第v个顶点出发递归地深度优先遍历图G六、程序流程图七、运行结果截图最初程序运行界面如下：输入图的先相关信息后运行结果(其中深度优先遍历的起点选择的是字符所在序列的序号，且0是起点)，一下是深度优先遍历时选择不同的起点所出现的最终运行结果：程序源代码：//图的邻接表表示：#include<iostream>#include<malloc.h>#include<queue>using namespace std;# define MAX_VEX_NUM 20//宏定义数组最大int visited[MAX_VEX_NUM];//设置标志数组queue<int>q;typedef struct ArcNode//定义邻接表结构{int adjvex;//该弧所指向的顶点的位置struct ArcNode *nextarc;//指向下一条弧的指针}ArcNode;typedef struct VNode//定义顶点结构类型{char data;//存放顶点信息ArcNode *firstarc;//指向第一条依附于该定点的指针}VNode,Adjlist[MAX_VEX_NUM];typedef struct ALGraph{Adjlist vertices;int vexnum;int arcnum;}ALGraph;ALGraph G;//申明一个无向图的邻接矩阵类型int locatevex(ALGraph G,char v)//图的基本操作，寻找顶点位置的下标{int i=0;while(i<G.vexnum && v!=G.vertices[i].data)i++;if(i<G.vexnum)return i;}void Create_DG(ALGraph &G)//创建一个有向图图的邻接链表表示{cout<<"请输入图的顶点数和弧数:"<<endl;cin>>G.vexnum;cin>>G.arcnum;char v1;char v2;int v1locate;int v2locate;ArcNode * p;cout<<"输入图的顶点信息"<<endl;for(int i=0;i<G.vexnum;i++)//构造表头向量{cin>>G.vertices[i].data;//输入顶点值G.vertices[i].firstarc=NULL;//初始化指针}cout<<"请输入从起点到终点的一条弧所对应的顶点"<<endl; for(int k=1;k<=G.arcnum;k++)//输入各弧并创建十字链表{cin>>v1>>v2;//输入一条弧的起点和终点v1locate=locatevex(G,v1);//确定v1在图G中位置v2locate=locatevex(G,v2);//确定v2在图G中位置p=new ArcNode;//假定有足够空间p->adjvex=v2locate;//有一条弧指向v2p->nextarc=G.vertices[v1locate].firstarc;//对弧节点赋值G.vertices[v1locate].firstarc=p;//完成在入弧和出弧链表的插入/*q=new ArcNode;q->adjvex=v1locate;q->nextarc=G.vertices[v2locate].firstarc;G.vertices[v2locate].firstarc=q;*/}}//Create_DGvoid DFS(ALGraph G,int v)//从第v个顶点出发递归地深度优先遍历图G {visited[v]=1;//访问第v个节点cout<<G.vertices[v].data<<" ";//输出节点值for(ArcNode *p=G.vertices[v].firstarc;p;p=p->nextarc){if(!visited[p->adjvex])DFS(G,p->adjvex);//对v的尚未访问的邻接顶点p递归调用dfs}}//DFSvoid DFSTraverse(ALGraph G,int vex)//对图G做深度优先遍历{for(int i = 0;i < G.vexnum;i++)visited[i]=0; //访问数组初始化DFS(G,vex); //先对图从指定定点访问for(int v = 0;v < G.vexnum;v ++) //对可能出现的子图遍历if(!visited[v]) //对尚未访问的顶点调用dfsDFS(G,v);}//DFSTraverseint BFSTraverse(ALGraph G)//无向图的广度遍历，从第v个顶点出发，v 为顶点下标{for(int i = 0;i < G.vexnum;i++) //访问数组初始化visited[i]=0;q.empty();int v;int u;for(v=0;v<G.vexnum;v++)if(!visited[v])//v尚未被访问{visited[v]=1;cout<<G.vertices[v].data<<" ";q.push(v);//V入队列while(!q.empty()){u=q.front();//对头元素出队并置为uq.pop();for(ArcNode *p=G.vertices[v].firstarc;p;p=p->nextarc) if(!visited[p->adjvex])//p为u的尚未访问的邻接节点{visited[p->adjvex]=1;cout<<G.vertices[p->adjvex].data<<" "; q.push(p->adjvex);}//if}//while}//ifreturn 1;}//BFSTraversevoid main(){int a;Create_DG(G);cout<<"输入图深度遍历的起点"<<endl; cin>>a;cout<<"深度优先遍历"<<endl; DFSTraverse(G,a);cout<<endl;cout<<"广度优先遍历"<<endl; BFSTraverse(G);}。

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

//图的建立#include <stdio.h>#define MAX_VERTEX_NUM 20//图的数据结构typedef struct{int adj;int *info; //该弧相关信息的指针}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];struct MGraph{char vertex[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum, arcnum;};//返回顶点在数组的下标int LocateVex(MGraph G,char v){int j=0,i;for(i=0;i<G.vexnum;++i)if(G.vertex[i]==v){j=i;break;}return j;}//创建无向图void CreateUDG(MGraph &G){int i,j,k;char v1,v2,t;printf("请输入无向图G的顶点数,边数:\n");scanf("%d%d",&G.vexnum,&G.arcnum);printf("请输入%d个顶点的值,空格隔开:\n",G.vexnum);for(i=0;i<G.vexnum;++i){scanf("%c%c",&t,&G.vertex[i]);}printf("请输入%d条边的顶点(如0 1):\n",G.arcnum);for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j){G.arcs[i][j].adj=0;}for(k=0;k<G.arcnum;++k){scanf("%c%c%c%c",&t,&v1,&t,&v2);i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j].adj=G.arcs[j][i].adj=1;}}//输出图的邻接矩阵void Display(MGraph G){int i,j;printf("该图的邻接矩阵为：\n");for(i=0;i<G.vexnum;++i){for(j=0;j<G.vexnum;++j)printf("%d ",G.arcs[i][j].adj);printf("\n");}}//主函数int main(){MGraph G;CreateUDG(G);Display(G);return 0;}//图的遍历#include<stdio.h>#include<malloc.h>#define MaxVerNum 50struct edgenode{int endver; //该边所指向的顶点的位置int inform;edgenode* edgenext;//指向下一条边的指针};struct vexnode{char vertex; //顶点信息（字符型）edgenode* edgelink;//指向第一条依附于该顶点的指针};struct Graph //图信息{vexnode adjlists[MaxVerNum];int vexnum,arcnum;//无向图的当前顶点和边数};struct QueueNode{//队列的定义及相关函数的实现int data;QueueNode* next;};struct QueueList{QueueNode* front;QueueNode* rear;};void EnQueue(QueueList* Q,int e){*q=(QueueNode *)malloc(sizeof(QueueNode));q->data=e;q->next=NULL;if(Q==NULL)return;if(Q->rear==NULL)Q->front=Q->rear=q;else{Q->rear->next=q;Q->rear=Q->rear->next;}}void DeQueue(QueueList* Q,int* e){if (Q==NULL)return;if (Q->front==Q->rear){*e=Q->front->data;Q->front=Q->rear=NULL;}else{*e=Q->front->data;Q->front=Q->front->next;}}void CreatAdjList(Graph* G)//创建图{int i,j,k;edgenode* p1;edgenode* p2;printf("请输入顶点数和边数:\n");scanf("%d,%d",&G->vexnum,&G->arcnum);printf("开始输入顶点信息:\n");for (i=0;i<G->vexnum;i++){scanf("%d",&G->adjlists[i].vertex);G->adjlists[i].edgelink=NULL;}printf("开始输入边表信息:\n");for (k=0;k<G->arcnum;k++){printf("请输入边<Vi,Vj>对应的顶点:");scanf("%d,%d",&i,&j);p1 =(edgenode *)malloc(sizeof(edgenode));p1->endver=j;//endve指该边所指向的顶点的位置p1->edgenext=G->adjlists[i].edgelink;//edgenext指向下一条边的指针G->adjlists[i].edgelink=p1;// edgelink指向第一条依附于该顶点的指针p2 =(edgenode *)malloc(sizeof(edgenode));p2->endver=i;p2->edgenext=G->adjlists[j].edgelink;G->adjlists[j].edgelink=p2;//因为是无向图，所以有两次建立边表的过程}void PrintGaph(Graph * G)//无向图的邻接表的输出{edgenode *p;for(int k=1;k<=G->vexnum;k++){printf("%d",G->adjlists[k]. vertex);p=G->adjlists[k].edgelink;while(p!=NULL){printf("%d",p->endver);p=p->edgenext;if(p!=NULL)printf("->");}printf("\n");}}void DFS(Graph *G,int i,int visit[]) //深度优先遍历,从第v个顶点出发递归地深度优先遍历无向图G{printf("%d",G->adjlists[i].vertex);printf(" ");visit[i]=1; //设置访问标志数组，未访问为0，访问后后为1edgenode *p=new edgenode;p=G->adjlists[i].edgelink; //指向第一条依附于该顶点vi的边的指针if(G->adjlists[i].edgelink&&!visit[p->endver]){ //指向第一条依附于该顶点vi 的便得指针非空，且顶点位被访问DFS(G,p->endver,visit); //递归自我调用}}void DFStraversal(Graph *G,char c) //深度优先遍历结果输出{printf("该图的深度优先遍历结果为:\n");int visit[MaxVerNum];for(int i=0;i<G->vexnum;i++)visit[i]=0;//全部初始化为0，即未访问状态}int m;for (i=0;i<G->vexnum;i++){if (G->adjlists[i].vertex==c)//根据字符查找序号{m=i;DFS(G,i,visit);//调用上面的函数break;}}for(i=0;i<G->vexnum;i++)//继续访问未被访问的结点{if(visit[i]==0)DFS(G,i,visit);}printf("\n");}void BFS(Graph* G,int v,int visit[])//广度优先遍历{QueueList *Q=new QueueList;Q->front=Q->rear=NULL;//初始化队列EnQueue(Q,v);//v入队列while(Q->rear!=NULL){int e=0;DeQueue(Q,&e);//对头（指定的）元素出队并设置为eprintf("%d",G->adjlists[e].vertex);//输出定点信息printf(" ");visit[e]=1;edgenode* p =(edgenode *)malloc(sizeof(edgenode));p=G->adjlists[e].edgelink;//指向第一天依附于该顶点的边的指针if(p){int m=p->endver;//该边所指向的顶点的位置if(m==0){EnQueue(Q,m);while(visit[m]==0){p=p->edgenext;if(p==NULL)break;m=p->endver;EnQueue(Q,m);}}}}}void BFStraversal(Graph *G,char c){printf("该图的广度优先遍历结果为:\n");int visited[MaxVerNum];for (int i=0;i<G->vexnum;i++){visited[i]=0;}int m;for (i=0;i<G->vexnum;i++){if (G->adjlists[i].vertex==c)//顶点信息{m=i;BFS(G,i,visited);break;}}for(i=0;i<G->vexnum;i++)//继续访问未被访问的结点{if(visited[i]==0)BFS(G,i,visited);}printf("\n");}void main(){Graph * G=(Graph *)malloc(sizeof(Graph));CreatAdjList(G);// PrintGaph(G);char ch;printf("请输入开始遍历的顶点:\n");scanf("%d",&ch);DFStraversal(G,ch);BFStraversal(G,ch); }。

图的建立，图的广度，深度遍历#include "stdio.h"#define maxsize 1000# define n 100typedef struct{ char vexs[n] ;int arcs[n][n] ;int num ;}G;typedef struct{int data[maxsize];int front,rear;} V;void GInit(G *L){L->num=0;}int GVexs(G *L){return(L->num);}void GCreate(G *L){int i,j;GInit(L);printf("请输入顶点数目：\n");scanf("%d",&L->num);printf("请输入各顶点：\n");for(i=0;i<L->num;i++){fflush(stdin);scanf("%c",&L->vexs[i]);}printf("请输入各顶点边的关系（1是有关0是无关）：\n"); for(i=0;i<L->num;i++){for(j=0;j<L->num;j++){scanf("%d",&L->arcs[i][j]);}}}void GOut(G L){int i,j;printf("\n图的顶点数目为：%d",L.num); printf("\n图的各顶点的信息为：\n");for(i=0;i<L.num;i++)printf("%7c",L.vexs[i]);printf("\n");for(i=0;i<L.num;i++){for(j=0;j<L.num;j++){printf("%7d ",L.arcs[i][j]);}printf("\n");}}void DFS(G g,int qidian,int mark[]){int v1;mark[qidian]=1;printf("%c ",g.vexs[qidian]);for(v1=0;v1<g.num;v1++){if(g.arcs[qidian][v1]!=0&&mark[v1]==0) DFS(g,v1,mark);}}void GDFS(G g){int qidian,v,v1,mark[maxsize];printf("\n深度遍历：");printf("\n请输入起点的下标：");scanf("%d",&qidian);getchar();for(v=0;v<g.num;v++){mark[v]=0;}for(v=qidian;v<g.num+qidian;v++){v1=v%g.num;if(mark[v1]==0)DFS(g,v1,mark);}}void QueueInit(V *sq){sq->front=0;sq->rear=0;}int QueueIsEmpty(V sq){if (sq.rear==sq.front)return(1);elsereturn(0);}int QueueFront(V sq, int *e){if (QueueIsEmpty(sq)){ printf("queue is empty!\n");return 0;} else{ *e=sq.data[(sq.front)]; return 1;}}int QueueIn (V *sq, int x){if (sq->front==(sq->rear+1)%maxsize) {printf("queue is full!\n");return 0;}else{sq->data[sq->rear]=x;sq->rear=(sq->rear+1)%maxsize; return(1);}}int QueueOut(V *sq){if (QueueIsEmpty(*sq)){printf("queue is empty!\n"); return 0;}else{sq->front=(sq->front+1)%maxsize; return 1;}}void BFS(G g,int v,int mark[]){int v1,v2;V q;QueueInit(&q);QueueIn(&q,v);mark[v]=1;printf("%c ",g.vexs[v]);while(QueueIsEmpty(q)==0){QueueFront(q,&v1);QueueOut(&q);for(v2=0;v2<g.num;v2++)if(g.arcs[v1][v2]!=0&&mark[v2]==0) {QueueIn(&q,v2);mark[v2]=1;printf("%c ",g.vexs[v2]);}}}}void GBFS(G g){int qidian,v,v1,mark[maxsize];printf("\n广度遍历：");printf("\n");scanf("%d",&qidian);for(v=0;v<g.num;v++){mark[v]=0;}for(v=qidian;v<g.num+qidian;v++) {v1=v%g.num;if(mark[v1]==0)BFS(g,v1,mark);}}void main(){G tu;GCreate(&tu);GOut(tu);GDFS(tu);GBFS(tu);}。

实验八图的创建与遍历实验目的：掌握图的邻接矩阵、邻接表、十字链表和邻接多重表四种存储结构，能够实现在任意一种存储结构上的创建和遍历两种基本操作实验要求：1、认真阅读和掌握教材上和本实验相关内容和算法（见P161~170）。

2、上机将图的任意一种存储表示的创建和遍历（DFS和BFS至少实现一种）算法实现。

3、实现下面实验内容要求的功能，并能够进行简单的输入输出验证。

实验内容：1、图的创建部分编程实现图的任意一种存储表示的创建算法，要求能够进行简单的输入输出验证。

#include <iostream.h>typedef struct Graph{char vexs[10];int arc[10][10];int vexnum;int arcnum;}Graph;int locatevex(Graph G,char x){int i=0;while(G.vexs[i]!=x)i++;return i;}void creatgraph(Graph &G){int i,j,k;char v1,v2;cin>>G.vexnum>>G.arcnum;for(i=0;i<G.vexnum;i++)cin>>G.vexs[i];for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)G.arc[i][j]=0;for(k=0;k<G.arcnum;k++){cin>>v1>>v2;i=locatevex(G,v1);j=locatevex(G,v2);G.arc[i][j]=1;G.arc[j][i]=1;}}void printgraph(Graph G){for(int i=0;i<G.vexnum;i++)cout<<G.vexs[i]<<" ";cout<<endl;for(i=0;i<G.vexnum;i++)for(int j=0;j<G.vexnum;j++){if(G.arc[i][j]==1)cout<<G.vexs[i]<<" ->"<<G.vexs[j]<<" ";}}int FirstAdjVex(Graph G,char v){ /* 初始条件: 图G存在,v是G中某个顶点*//* 操作结果: 返回v的第一个邻接顶点的序号。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

图的建立和遍历题目1：用邻接表存储无向图：采用邻接表作为图的存储结构；程序运行时输入图的顶点及边的信息；实现建立图的基本操作；题目2：对题目1建立的图进行深度遍历。

可以从任意顶点出发深度遍历该图；格式化输出：输出顶点的序列，各数据之间用“－>”分开；要求实现FirstAdjVex,NextAdjVex,DFS等基本操作；算法描述创建图：包括建立结点的函数CreatVex(Graph *G)，以及GreatUDG(Graph *G) ，GreatUDN(Graph *G) ，GreatDG(Graph *G) GreatDN(Graph *G)1提示用户输入图的基本信息：顶点数，边数以及图的基本类型；2通过for循环语句提示用户输入顶点的值；3图Graph结构体类型包括：AdjList用来存储头结点的数组；int类型vexnum 和arcnum，用来表示顶点数和边数的变量；int类型kind，用来存储图的类型。

边ArcNode结构包括：adjvex,ArcNode *nextarc,int info前者表示指向的结点的下标，后者表示指向结点的下一条边结点，最后的变量为边所带的权值信息；4根据图的类型决定是否要使用边中的info变量；5提示用户按照正确的形式输入边的端点以及边上的权值信息；遍历图：包括DFSTraverse(Graph G,VertexType vex)以及DFS(Graph G,int v)两个主要的便历函数。

前者第二个参数表示开始进行便历的顶点，后者的第二个参数表示对图的下标为v的顶点访问。

1遍历前首先建立一个标志数组Visited[]，长度为图中结点的数目，用来表示是否访问过一结点，访问前全置为0;2接收用户要求开始访问的顶点，通过函数Adjfound(Graph G,VertexType c)找到改点在图的结点中的下标；3若该下标对应的标志数组的值为0,访问该下标的firstArcNode结点，同时把该结点的在访问标志数组中的值设置为1;若该下标对应的标志数组的值为1,则进行第5步；4继续进行操作2;5在标志数组中查找仍为0的项，得到下标值再进行第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算法结束；}。

#include<iostream>#include<queue>using namespace std;# define MAXSIZE 20int visited[MAXSIZE];//设置标志数组queue<int> q;struct ArcNode{int adjvex;ArcNode *nextarc;};//定义邻接表结构typedef struct VNode{char data;//存放顶点信息ArcNode *firstarc;//指向第一条依附于该定点的指针}Adjlist[MAXSIZE];//顶点结构类型struct ALGraph{Adjlist vertices;//顶点向量int vexnum;//弧的数目int arcnum;//顶点的数目};ALGraph G;//申明一个无向图的邻接矩阵类型//邻接表类的声明class Graph{public:int Locatevex(ALGraph G,char v);//图的基本操作，寻找顶点位置的下标void CreateALGraph(ALGraph &G);//创建一个无向图的邻接链表表示void DFS(ALGraph G,int v);//从顶点v开始进行深度遍历(直到不能进行了为止)void DFStraverse(ALGraph G,int vex);//对图从指定的顶点开始深度遍历(因为图不一定是连通的，所以有可能以多个结点为顶点进行深度遍历)void BFStraverse(ALGraph G);//对图进行广度遍历};#include "Graph.h"//寻找顶点位置的下标int Graph::Locatevex(ALGraph G, char v){int i=0;while(i<G.vexnum && v!=G.vertices[i].data)i++;if(i<G.vexnum)return i;}//创建一个无向图的邻接链表void Graph::CreateALGraph(ALGraph &G)//这里的变量应是&AG，若写成AG，则是在使用时未定义{cout<<"请输入图的顶点数和弧数:";cin>>G.vexnum;cin>>G.arcnum;char v1;char v2;int v1locate;int v2locate;ArcNode * p,* q;cout<<"开始输入图的信息"<<endl;cout<<"输入顶点信息"<<endl;for(int i=0;i<G.vexnum;i++){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;//初始化}for(int k=1;k<=G.arcnum;k++)//创建邻接链表{cout<<"输入相关的边"<<endl;cin>>v1>>v2;//输入的是边的顶点v1locate=Locatevex(G,v1);v2locate=Locatevex(G,v2);p=new ArcNode;p->adjvex=v2locate;p->nextarc=G.vertices[v1locate].firstarc;G.vertices[v1locate].firstarc=p;q=new ArcNode;q->adjvex=v1locate;q->nextarc=G.vertices[v2locate].firstarc;G.vertices[v2locate].firstarc=q;}}//从顶点v开始进行深度遍历(直到不能进行了为止)void Graph::DFS(ALGraph G,int v){visited[v]=1;cout<<G.vertices[v].data<<" ";//输出现在结点的值for(ArcNode *p=G.vertices[v].firstarc;p;p=p->nextarc)//以v结点的第一个邻接结点开始，对v的所有结点执行深度遍历{if(!visited[p->adjvex])//如果v的邻接点没有被访问过，以此结点为顶点进行递归深度遍历DFS(G,p->adjvex); //递归遍历}}//对图从指定的顶点开始深度遍历(因为图不一定是连通的，所以有可能以多个结点为顶点进行深度遍历)void Graph::DFStraverse(ALGraph G, int vex){for(int i = 0;i < G.vexnum;i++)visited[i]=0; //访问数组初始化DFS(G,vex); //从给定的结点开始深度遍历for(int v = 0;v < G.vexnum;v ++) //查找图的每个顶点，如果有没有被访问的，以此顶点进行深度遍历if(!visited[v])DFS(G,v);}//对图进行广度遍历void Graph::BFStraverse(ALGraph G){for(int i = 0;i < G.vexnum;i++) //访问数组初始化visited[i]=0;q.empty();int v;int u;for(v=0;v<G.vexnum;v++)//依次处理各顶点if(!visited[v])//如果没有被访问，访问后加入队列{visited[v]=1;cout<<G.vertices[v].data<<" ";q.push(v);while(!q.empty())//在队列不空时处理队头结点{u=q.front();q.pop();for(ArcNode *p=G.vertices[v].firstarc;p;p=p->nextarc)if(!visited[p->adjvex]){visited[p->adjvex]=1;cout<<G.vertices[p->adjvex].data<<" ";q.push(p->adjvex);}}}}int main(){int a;class Graph ALG;ALG.CreateALGraph(G);cout<<"输入图深度遍历的起点"<<endl;cin>>a;cout<<"深度优先遍历"<<endl;ALG.DFStraverse(G,a);cout<<endl;cout<<"广度遍历"<<endl;ALG.BFStraverse(G);cout<<endl;cout<<endl;system("pause");}。

图的建立与遍历实验报告------------图的建立与遍历姓名:曹庆松班级: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;}四、实验总结:通过本实验，我对图的存储结构、图的遍历等有了比较深的理解与运用，图的遍历和树的遍历很类似，但是却比树的遍历复杂很多。

实验图的建立与遍历姓名：曹国君梁辰唐琪皓黄悦班级：信息1班学号:09125676 09125675 09125672 09125673 实验时间：第9周1.问题描述输入图的顶点和边的信息建立图,并对其进行深度和广度遍历,输出遍历结果。

2.数据结构设计template <class ElemType>void AdjMatrixUndirGraph<ElemType>::InsertArc(int v1, int v2)// 操作结果：插入依附顶点v1和v2的边{if (v1 < 0 || v1 >= vexNum)throw Error("v1不合法!"); // 抛出异常if (v2 < 0 || v2 >= vexNum)throw Error("v2不合法!"); // 抛出异常if (v1 == v2)throw Error("v1不能等于v2!");// 抛出异常if (Matrix[v1][v2] == 0) { // 原无向图中没有边(v1, v2)arcNum++;Matrix[v1][v2] = 1;Matrix[v2][v1] = 1;}}template <class ElemType>void BFS(const AdjMatrixUndirGraph<ElemType> &g, int v, void (*Visit)(constElemType &))// 初始条件：存在图g// 操作结果：从顶点v出发进行广度优先搜索{LinkQueue<int> q;int u, w;ElemType e;g.SetTag(v, VISITED); // 作访问标志g.GetElem(v, e); // 取顶点v的数据元素值Visit(e); // 访问顶点vq.EnQueue(v); // 顶点v入队while (!q.Empty()) {q.DelQueue(u);for (w = g.FirstAdjVex(u); w != -1; w = g.NextAdjVex(u, w))if (g.GetTag(w) == UNVISITED){ // 对u尚未访问过的邻接顶点w 进行访问g.SetTag(w, VISITED);g.GetElem(w, e);Visit(e);q.EnQueue(w);}}}template <class ElemType>void DFS(const AdjMatrixUndirGraph<ElemType> &g, int v, void (*Visit)(const ElemType &))// 初始条件：存在图g// 操作结果：从顶点v出发进行深度优先搜索{ElemType e;g.SetTag(v, VISITED); // 设置顶点v已访问标志g.GetElem(v, e); // 取顶点v的数据元素值Visit(e); // 访问顶点vfor (int w = g.FirstAdjVex(v); w != -1; w = g.NextAdjVex(v, w)) if (g.GetTag(w) == UNVISITED)DFS(g, w , Visit); // 从v的尚未访问过的邻接顶点w开始进行深度优先搜索}3.算法设计#include "assistance.h" // 实用程序软件包#include "adj_matrix_undir_graph.h" // 无向图邻接矩阵#include "dfs.h" // 图的深度优先遍历#include "bfs.h" // 图的广度优先遍历int main(void){try // 用try封装可能出现异常的代码{int n=0, i, j, k, l;cout<<"请输入图的顶点个数：";cin>>n;if (n<=0||n>=26)throw Error("节点输入错误！");char a='A' ;char vexs[26];int m[26][26] ;for (i=0; i<n; i++){for (j=0; j<n; j++){m[i][j]=0;}}for(i=0; i<n; i++){vexs[i]=a;a++;}cout<<"输入边的两个顶点:（输入-1 -1结束）" ;cin>>k;cin>>l;if (k>=n||l>=n)throw Error("节点输入错误！");m[k][l]=1;m[l][k]=1;while (k!=-1||l!=-1){cout<<"输入边的两个顶点:（输入-1 -1结束）" ;cin>>k;cin>>l;if (k>=n||l>=n)throw Error("节点输入错误！");m[k][l]=1;m[l][k]=1;}AdjMatrixUndirGraph<char> g(vexs, n);AdjMatrixUndirGraph<char> g1(vexs, n);for(int u=0; u<n; u++){for(int v=0; v<n; v++){if( m[u][v]==1){ g.InsertArc(u,v);g1.InsertArc(u,v);} }}cout << "原有图:" << endl;g.Display(); // 显示图gcout << endl;system("PAUSE"); // 调用库函数system()int v=0;cout<<"请输入开始遍历的顶点"<<endl;cin>>v;if (v>=n)throw Error("节点输入错误！");cout << "深度优先遍历:";DFS<char>(g, v, Write<char>);// <char>用于确定函数模板参数cout << endl;system("PAUSE");cout << "广度优先遍历:";BFS(g1, v, Write<char>); // 对图g进行广度优先遍历cout << endl;}catch (Error err) // 捕捉并处理异常{err.Show(); // 显示异常信息}system("PAUSE"); // 调用库函数system()return 0; // 返回值0, 返回操作系统}4.测试与运行图的建立与遍历数据测试实验序号输入输出节点数相连的边开始遍历的点深度遍历广度遍历备注1 -1 / / / / 报错2 2 <1,3> / / / 报错3 3 <1,0>4 / / 报错4 2 <0.1> 0 A B A B /5 3 <0,1> <1,2> 0 A B C A B C /6 3 <0,2> <2,1> 2 C A B C A B /7 5 <0,2> <0,1><2,3> <1,4>2 C A B E D C A D B E /8 5 <0,1> <1,2><1,3> <1,4>0 A B C D E A B C D E /9 5 <0,1> <1,2><1,3> <1,4>3 D B A C E D B A C E /10 9 <0,1> <1,2><2,3> <3,7><3,4> <4,5><4,6> <7,8>A B C D EF G H IA B C D EH F G I/5.测试记录及收获给出测试中遇到的问题及解决的方法和过程。

#define MAX 20#define NULL 0#include<stdio.h>#include<stdlib.h>struct ArcNode{ //定义边结点int adjvex;struct ArcNode *nextarc;};struct Vnode{ //定义顶点结点int data;struct ArcNode *firstarc;};struct Vnode AdjList[MAX];int m,n,v,cord;void main()//主函数{void CreatGraph(struct Vnode A[MAX]);void DFS(struct Vnode A[MAX]);CreatGraph(AdjList);DFS(AdjList);}void CreatGraph(struct Vnode A[MAX])//无向图邻接链表的建立{int i,j,k;struct ArcNode *p;printf("输入图的边数和顶点数:");scanf("%d,%d",&m,&n);for(k=0;k<n;k++){A[k].data=k+1;A[k].firstarc=NULL;}for(k=0;k<m;k++){printf("输入和边关联的顶点号:");scanf("%d,%d",&i,&j);p=(struct ArcNode*)malloc(sizeof(struct ArcNode));p->adjvex=j;p->nextarc=A[i-1].firstarc;A[i-1].firstarc=p;p=(struct ArcNode *)malloc(sizeof(struct ArcNode));p->adjvex=i;p->nextarc=A[j-1].firstarc;A[j-1].firstarc=p;}printf("\n");for(k=0;k<n;k++) //输出已建立的邻接链表信息{printf("%d ",A[k].data);p=A[k].firstarc;while(p){printf("%d ",p->adjvex);p=p->nextarc;}printf("\n");}}void DFS(struct Vnode A[MAX]) //深度优先遍历{struct ArcNode *p,*ar[MAX];int x,i,y,top=-1;int visited[MAX];for(i=0;i<n;i++) visited[i]=0;printf("\n输入图遍历的始顶点的编号x:");scanf("%d",&x);printf("%d",x);visited[x-1]=1;p=A[x-1].firstarc;while((p)||(top>=0)){if(!p){p=ar[top];top--;}y=p->adjvex;if(visited[y-1]==0){ visited[y-1]=1;printf("->%d",y);p=p->nextarc;if(p){top++; ar[top]=p;}p=A[y-1].firstarc;}else p=p->nextarc;}printf("\n");}。

C语⾔图的建⽴及BFS,DFS遍历的代码把开发过程中经常⽤到的⼀些内容段做个收藏，下⾯内容段是关于C语⾔图的建⽴及BFS,DFS遍历的内容，希望对各位也有⽤途。

#include <stdio.h>#include <malloc.h>#include <stdlib.h>struct tnode{};struct node{};struct picture{};int main(){char a;p=createpicture();while(1){getchar();printf("现在将对图进⾏遍历，若使⽤⼴度优先遍历，请输⼊a,若使⽤深度优先遍历请输⼊b，清屏请输⼊c,退出请输⼊d:n");scanf("%c",&a);if(a=='a'){printf("深度优先遍历如下：n");traversebfs(p);}if(a=='b'){printf("⼴度优先遍历如下：n");traversedfs(p);}if(a=='c')system("cls");if(a=='d')exit(0);}return 0;}{char a;printf("请输⼊你要建⽴的图中的节点数以及图的类型(a表⽰⽆向图b表⽰有向图):n");scanf("%d %c",&i,&a);p->count=i;p->a=a;printf("请依次输⼊各节点的值(每输完⼀个节点的值按回车结束)：n");for(i=0;i<p->count;i++){scanf("%d",&j);p->nd[i].valu=j;p->nd[i].link=NULL;}for(i=0;i<p->count;i++){printf("输⼊与数据值为%d的节点相邻的节点的数据值(每输完⼀个节点的值按回车结束),若不再含有相邻的值请输⼊-1n",p->nd[i].valu); while(1){scanf("%d",&k);if(k==-1)break;l=search(p,k);if(l!=-1){t->data=l;t->next=p->nd[i].link;p->nd[i].link=t;}elseprintf("⽆此数据值!n");}}return p;}{int i;for(i=0;i<p->count;i++){if(value==p->nd[i].valu) {return i;}}return -1;}{int i;for(i=0;i<p->count;i++){visit[i]=0;}for(i=0;i<p->count;i++){if(visit[i]==0){dfs(p,i,visit);}}}{printf("%dn",q->nd[i].valu); visit[i]=1;w=q->nd[i].link;while(w!=NULL){if(visit[w->data]==0){dfs(q,w->data,visit);}else{w=w->next;}}}{int i;for(i=0;i<p->count;i++){visit[i]=0;}for(i=0;i<p->count;i++){if(visit[i]==0){bfs(p,i,visit);}}}{int f,r;int v;f=r=0;visit[i]=1;printf("%dn",q->nd[i].valu);a[r]=i;while(f!=r){v=a[f];w=q->nd[v].link;while(w!=NULL){if(visit[w->data]==0){visit[w->data]=1;printf("%dn",q->nd[w->data].valu); a[r]=w->data;r++;}w=w->next;}}}。

头文件：#include<stdio.h>#define MaxSize 100typedef int T;typedef int BOOL;typedef struct queue{T data[MaxSize];int Front;int Rear;}Queue;void CreateQueue(Queue *que){que->Front=MaxSize-1;que->Rear = MaxSize-1;}BOOL IsEmpty(Queue que){return que.Front ==que.Rear;}BOOL IsFull(Queue que){return (que.Rear+1)%MaxSize == que.Front; }void Append(Queue *que,T x){if(IsFull(*que)){printf("Overflow");}que->Rear=(que->Rear+1)% MaxSize;que->data[que->Rear]=x;}void Serve(Queue *que,T *x){if(IsEmpty(*que)){printf("Underflow");}que->Front=(que->Front+1)% MaxSize;*x=que->data[que->Front];}程序：#include<stdio.h>#include<malloc.h>#include"队列头文件.h"#define n 5 //图的顶点数#define e 6 //图的边数#define bool int#define true 1#define false 0#define maxvalue 10000//表示无穷大typedef char vextype;//顶点的数据类型typedef float adjtype; //权值类型//数组表示法的类型定义typedef struct graph{vextype vexs[n]; //存放顶点数据adjtype arcs[n][n]; //存放边数据}Graph;//构造邻接矩阵表示的图void CreateGraph(Graph *ga){int i,j,k;float w;printf("请输入图的顶点个数（如5个顶点则输入12345）：");for(i=0;i<n;i++)ga->vexs[i]=getchar();for(i=0;i<n;i++)for(j=0;j<n;j++)ga->arcs[i][j]=maxvalue;printf("请输入权值（如V0与V1之间权值为3，则输入0 1 3）：\n");for(k=0;k<e;k++){scanf("%d%d%f", &i,&j,&w);ga->arcs[i][j]=w;ga->arcs[j][i]=w;}}//深度优先遍历void DFS(Graph g,int i,bool visited[])int j;visited[i]=true;printf("%c ",g.vexs[i]);for(j=0;j<n;j++){if((g.arcs[i][j]<maxvalue)&&(visited[j]==false)){DFS(g,j,visited);}}}void DFSTraverse(Graph g){int i;bool visited[n];for(i=0;i<n;i++){visited[i]=false;}for(i=0;i<n;i++){if(visited[i]==false){DFS(g,i,visited);}}}//广度优先遍历void BFSTraverse(Graph g,Queue *que){int i,j,u;bool visited[n];for(i=0;i<n;i++){visited[i]=false;}for(i=0;i<n;i++){if(visited[i]==false){Append(que,i);visited[i]=true;printf("%c ",g.vexs[i]);while(!IsEmpty(*que)){Serve(que,&u);for(j=0;j<n;j++){if((g.arcs[u][j]<maxvalue)&&(visited[j]==false)){Append(que,j);printf("%c ",g.vexs[j]);visited[j]=true;}}}}}}void main(){Graph ga;Queue que;int i,j;CreateQueue(&que);CreateGraph(&ga);printf("\n输出该图：\n");for(i=0;i<n;i++){for(j=0;j<n;j++)printf("%f ",ga.arcs[i][j]);printf("\n");}printf("\n深度优先遍历：");DFSTraverse(ga);printf("\n广度优先遍历：");BFSTraverse(ga,&que);printf("\n");}。