王鑫宇实验报告（实验六）

《王鑫宇实验报告（实验六）》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、犹阳工程学院学生实验报告（课程名称：数据结构与算法）实验题目：图班级物联网131学号2013417115姓名王鑫宇地点F608指导教师祝世东崔妍实验日期：2014年6月4日一、实验目的1.掌握图的基本存储方法。2.掌握有关图的操作算法并用高级语言实现。3.熟练掌握图的两种搜索路径的遍历方法。4.掌握图的有关应用。二、实验环境TurboC或是VisualC++三、实验内容与要求实验5.1建立无向图的邻接矩阵存储并输出对一个已知无向图的邻接矩阵存储表示，并进行输出。在此基础上稍加改动就可以实现冇向图、无

2、向图和冇向网的邻接矩阵表示。实验5.2建立图的邻接矩阵存储并在此基础上实现图的深度优先遍历和广度优先遍历图的广度优先遍历用非递归方法很容易理解，非递归方法需耍辅助队列Q以及出队、入队函数。选做题目:1、求无向图的度2、分别求出冇向图入度和出度四、实验过程及结果分析#include#include〈stdlib.h>#definemax100typedefstruet{charvexs[max];intedges[max][max];intvexnum,arcnum;}mgraph,

3、g;voidgreatmtaph(nigraph*g){inti,j,k;chara;printf(z，输入顶点数和边数:〃)；fflush(stdin);seanf(〃％d,%d〃，&g->vexnum,&g->arcnum);printf(，z输入顶点信息:〃);for(i=0;ivcxnum;i++){fflush(stdin);scanf(〃%c〃,&a);g->vexs[i]=a;}for(i=0;ivexnum;i++)for(j=0;jvexnum;j++)g-

4、>edges[i][j]=0;printfC输入边(弧)两端顶点：〃)；for(k=0;karcnum;k++){fflush(stdin);scanf(〃％d,%d〃，&i,&j);g->edges[i][j]=l;g->edges[j][i]=l;}}intvisited[max];voiddfsm(mgraph*g,inti)//深度{intj;printf(〃%c〃,g->vexs[i]);visited[i]=l;for(j=0;jvexnum;j++)if(g->edge

5、s[i][j]==l&&!visited[j])dfsm(g,j);}voiddfs(mgraph*g){inti;for(i=0;ivcxnum;i++)for(i=0;ivexnum;i++)if(!visited[i])dfsm(g,i);}voidbfs(mgraph*g,intk)//广度{inti,j,f=0,r二0;intcq[max];for(i=0;ivcxnum;i++)visited[i]=0;for(i=0;ivexnum;i++)cq[订二T

6、;printf("%c〃,g->vexs[k]);visitcd[k]=l;cq[r]=k;while(cq[f]!=T){i=cq[f];f二f+1;for(j=0;jvexnum;j++)if(!visited[j]&&g->edges[i][j]==l){printf(〃%c〃,g->vexs[j]);visited]j]二T;r=r+l;cq[r]=j;}}}voidgraph(mgraph*g){inti,j,k=0;for(i=0;ivexnum;i++){for(j=0

7、;jvcxnum;j++)if(g->edges[i][j]!=0)k=k+l;}printf(，z图的度为:%d〃,&k);intmain(){inti,j,k；mgraph*g;g=(mgraph*)malloc(sizeof(mgraph));greatmtaph(g);printfC图的邻接矩阵为:〃);for(i=0;ivexnum;i++){for(j=0;jvexnum;j++)printf(〃％10cT,g->edges[i][j]);printf(〃

8、〃)；}printf(〃深度优先遍历:")；dfs(g);printf(〃rT);printf(z，广度优先遍历的节点：“)；scanf(〃%d〃,&k);printf(z，广度优先遍历：")；bfs(g,k);system("pause〃);return0;五、成绩评定优•I1及格不及格出勤内容格式创新效果总评指导教师：年月日