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

《数据结构图的遍历实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、M40#defineMAX40#include#include#include#includetypedefstructArCell{intadj;}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{charname[20];}infotype;typedefstruct教育资料.{infotypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;in

3、tvexnum,arcnum;}MGraph;intLocateVex(MGraph*G,char*v){intc=-1,i;for(i=0;ivexnum;i++)if(strcmp(v,G->vexs[i].name)==0){c=i;break;}returnc;}MGraph*CreatUDN(MGraph*G)//初始化图，接受用户输入{inti,j,k,w;charv1[20],v2[20];printf("请输入图的顶点数,弧数:");scanf("%d%d",&G->vexnum,&G->arcn

4、um);printf("结点名字:");for(i=0;ivexnum;i++){printf("No.%d:",i+1);scanf("%s",G->vexs[i].name);}for(i=0;ivexnum;i++)for(j=0;jvexnum;j++)G->arcs[i][j].adj=INFINITY;printf("请输入一条边依附的两个顶点和权值:");for(k=0;karcnum;k++){printf("第%d条边:",k+1);printf("起始结点:

5、");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];}}returnG;}intFirstAdjVex(MGraph*G,intv){inti;if(v<=0&&vvexnum){//v合理for(i

6、=0;ivexnum;i++)if(G->arcs[v][i].adj!=INFINITY)returni;教育资料.}return-1;}voidVisitFunc(MGraph*G,intv){printf("%s",G->vexs[v].name);}intNextAdjVex(MGraph*G,intv,intw){intk;if(v>=0&&vvexnum&&w>=0&&wvexnum)//v,w合理{for(k=w+1;kvexnum;k++)if(G->arcs[v][k].

7、adj!=INFINITY)returnk;}return-1;}intvisited[MAX];voidDFS(MGraph*G,intv)//从第v个顶点出发递归地深度优先遍历图G{intw;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]);}}voidDFSTraverse(MGraph*G,c

8、har*s)//深度优先遍历{intv,k;for(v=0;vvexnum;v++)visited[v]=0;k=LocateVex(G,s);if(k>=0&&kvexnum){for(v=k;v>=0;v--){if(!visited[v])DFS(G,v);}for(v=k+1;vvex