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

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

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

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

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

五、实验程序及结果#define INFINITY 10000 /*无穷大*/#define MAX_VERTEX_NUM 40#define MAX 40#include<stdlib.h>#include<stdio.h>#include<conio.h>#include<string.h>typedef struct ArCell{int adj;}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{ char name[20];}infotype;typedef struct{ infotype vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;}MGraph;int LocateVex(MGraph *G,char* v){ int c = -1,i;for(i=0;i<G->vexnum;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("请输入图的顶点数,弧数:");scanf("%d%d",&G->vexnum,&G->arcnum);printf("结点名字:\n");for(i=0;i<G->vexnum;i++){printf("No.%d:",i+1);scanf("%s",G->vexs[i].name);}for(i=0;i<G->vexnum;i++)for(j=0;j<G->vexnum;j++)G->arcs[i][j].adj=INFINITY;printf("请输入一条边依附的两个顶点和权值:\n"); for(k=0;k<G->arcnum;k++){printf("第%d条边:\n",k+1);printf("起始结点:");scanf("%s",v1);printf("结束结点:");scanf("%s",v2);//printf("边的权值:");//scanf("%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->vexnum){ //v合理for(i=0;i<G->vexnum;i++)if(G->arcs[v][i].adj!=INFINITY)return i;}return -1;}void VisitFunc(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->vexnum && w>=0 && w<G->vexnum)//v,w合理{for( k=w+1;k<G->vexnum;k++)if(G->arcs[v][k].adj!=INFINITY)return k;}return -1;}int 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>=0;w=NextAdjVex(G,v,w))if(!visited[w]){DFS(G,w);printf("%d ",G->arcs[v][w]);}}void DFSTraverse(MGraph *G,char *s)//深度优先遍历{int v,k;for(v=0;v<G->vexnum;v++)visited[v]=0;k=LocateVex(G,s);if(k>=0&&k<G->vexnum){for(v=k;v>=0;v--){if(!visited[v])DFS(G,v);}for(v=k+1;v<G->vexnum;v++)if(!visited[v])DFS(G,v);}}typedef struct Qnode{int vexnum;struct Qnode *next;}QNode,*QueuePtr;typedef struct{QueuePtr 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);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 QueueEmpty(LinkQueue *Q) {if(Q->rear==Q->front)return 0;return 1;}int Visited[MAX];void BFSTraverse(MGraph *G,char *str)//广度优先遍历{int w,u,v,k;LinkQueue Q,q;for(v=0;v<G->vexnum;v++) Visited[v]=0;InitQueue(&Q);InitQueue(&q);k=LocateVex(G,str);for(v=k;v>=0;v--)if(!Visited[v]){Visited[v]=1;VisitFunc(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;VisitFunc(G,v);EnQueue(&Q,w);}}}for(v=k+1;v<G->vexnum;v++)if(!Visited[v]){Visited[v]=1;VisitFunc(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;VisitFunc(G,v);EnQueue(&Q,w);}}}}void main(){MGraph *G,b;char v[10];G=CreatUDN(&b);printf("请输入起始结点名称:"); scanf("%s",v);printf("\n深度优先遍历:\n"); DFSTraverse(G,v);printf("\n广度优先遍历:\n"); BFSTraverse(G,v);getch();}六、实验总结实验要求输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。

在设计中其中用邻接表表示的节点的值只能是数字，但用邻接矩阵表示的节点的值可以是字母。

但用邻接表形式要相对简单一些。

深度优先采取的递归思想。

首先，将从起点，沿某条边，顺势遍历下去，直到不能继续遍历下去。

这时，又从起点的另一结点开始，遍历下去。

如此往复，知道将所有结点遍历完。

广度优先得使用队列。

首先，将起点入队，并标为已访问。

进入循环，当队列不为空时，出队，输出，并将与出队的元素相邻的且未访问的结点全部放入队列，标为已访问。