数据结构图的遍历实验报告

1、实验项目名称：图的遍历一、实验目的应用所学的知识分析问题、解决问题，学会用建立图并对其进行 遍历，提高实际编程能力及程序调试能力。二、实验内容问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输 入图中节点的个数和边的个数，能够打印由用邻接表或邻接矩阵表示 的图的储存结构。三、实验仪器与设备计算机，Code:Blocks 。四、实验原理用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索, 并输由遍历的结果。五、实验程序及结果#define INFINITY 10000 /* 无穷大 */#define MAX_VERTEX_NUM 40#define MAX 40#include&l

2、t;stdlib.h>#include<stdio.h>#include<conio.h>#include<string.h>typedef struct ArCellint adj;ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char name20;infotype;typedef struct教育资料 infotype vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;MGraph;int LocateVex(MGrap

3、h *G,char* v) int c = -1,i;for(i=0;i<G->vexnum;i+)if(strcmp(v,G->)=0) c=i; break;return c;MGraph * CreatUDN(MGraph *G)/初始化图，接受用户输入 int i,j,k,w;char v120,v220;printf("请输入图的顶点数，弧数:")；scanf("%d%d",&G->vexnum,&G->arcnum);printf("结点名字:n");for

4、(i=0;i<G->vexnum;i+)printf("No.%d:",i+1);scanf("%s”,G->);for(i=0;i<G->vexnum;i+)for(j=0;j<G->vexnum;j+)G->arcsij.adj=INFINITY;printf("请输入一条边依附的两个顶点和权值：n");for(k=0;k<G->arcnum;k+)printf("第陈边:n",k+1);printf("起始结点:");s

5、canf("%s",v1);printf(" 结束结点:");scanf("%s",v2);/printf(" 边的权值:");/scanf("%d",&w);i=LocateVex(G,v1); j=LocateVex(G,v2);if(i>=0&&j>=0)/G->arcsij.adj=w;G->arcs皿i=G->arcsij;return G;int FirstAdjVex(MGraph *G,int v)int i;if(v<

6、=0 && v<G->vexnum) /v 合理for(i=0;i<G->vexnum;i+)if(G->arcsvi.adj!=INFINITY)return i;return -1; void VisitFunc(MGraph *G,int v)printf("%s ”,G->);int NextAdjVex(MGraph *G,int v,int w)int k;if(v>=0 && v<G->vexnum && w>=0 && w&l

7、t;G->vexnum)v,w 合理for( k=w+1;k<G->vexnum;k+) if(G->arcsvk.adj!=INFINITY) return k;return -1;int visitedMAX;void DFS(MGraph *G,int v)/ 从第v个顶点出发递归地深度优先遍历图Gint w;visitedv=1;VisitFunc(G,v);/ 访问第v个结点for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,w);printf("%d ”,G-

8、>arcsvw);void DFSTraverse(MGraph *G,char *s)/深度优先遍历int v,k;for(v=0;v<G->vexnum;v+)visitedv=0;k=LocateVex(G,s);if(k>=0&&k<G->vexnum)for(v=k;v>=0;v-)if(!visitedv)DFS(G,v);for(v=k+1;v<G->vexnum;v+)if(!visitedv)DFS(G,v);typedef struct Qnodeint vexnum;struct Qnode *next

9、;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;int InitQueue(LinkQueue *Q)Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode);if(!Q->front)exit(0);Q->front->next=NULL;return 1;void EnQueue(LinkQueue *Q,int a )QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(0)

10、;p->vexnum=a;p->next=NULL;Q->rear->next=p;Q->rear=p;int DeQueue(LinkQueue *Q,int *v) QueuePtr p;if(Q->front=Q->rear)printf("结点不存在!n");exit(0);p=Q->front->next;*v=p->vexnum;Q->front->next=p->next;if(Q->rear=p)Q->front=Q->rear;return *v;int Que

11、ueEmpty(LinkQueue *Q)if(Q->rear=Q->front)return 0;return 1;int VisitedMAX;void BFSTraverse(MGraph *G,char *str)/ 广度优先遍历 int w,u,v,k;LinkQueue Q,q;for(v=0;v<G->vexnum;v+) Visitedv=0;InitQueue(&Q);InitQueue(&q);k=LocateVex(G,str);for(v=k;v>=0;v-)if(!Visitedv)Visitedv=1;VisitFunc

12、(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(!Visitedw)Visitedw=1;VisitFunc(G,v);EnQueue(&Q,w);for(v=k+1;v<G->vexnum;v+)if(!Visitedv)Visitedv=1;VisitFunc(G,v);EnQueue(&Q,v);/v 入队while(!QueueEmpty(

13、&Q)DeQueue(&Q,&u);/ 出队for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w) if(!Visitedw)Visitedw=1;VisitFunc(G,v);EnQueue(&Q,w);void main()MGraph *G,b;char v10;G=CreatUDN(&b);printf("请输入起始结点名称：");scanf("%s",v);printf("n深度优先遍历:n");DFSTraverse(G,v);printf("n广度优先遍历:n");BFSTraverse(G,v);getch()；六、实验总结实验要求输入图中节点的个数和边的个数，能够打印由用邻接表 或邻接矩阵表示的图的储存结构。在设计中其中用邻接表表示的节点 的值只能是数字，但用邻接矩阵表示的节点的值可以是字母。但用邻 接表形式要相对简单一些。深度优先采取的递归思想。首先，将从起点，沿某条边，顺势遍 历