数据结构与算法实验报告-图

《数据结构与算法实验报告-图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、沈阳工程学院学生实验报告（课程名称：数据结构与算法）实验题目：图班级网络本112班学号2011414217姓名樊鹏鹏地点F606指导教师吕海华、祝世东实验日期:2012年11月18日一、实验目的1．掌握图的基本存储方法。2．掌握有关图的操作算法并用高级语言实现。3．熟练掌握图的两种搜索路径的遍历方法。4．掌握图的有关应用。二、实验环境TurboC或是VisualC++三、实验内容与要求实验1建立无向图的邻接矩阵或邻接表存储并输出本题给出了一个无向图的邻接矩阵存储表示，在此基础上稍加改动就可以实现有向图、无向图和有向网的邻接矩阵表示。实验2建立图的邻接矩阵或邻接表存储并在此基础上实

2、现图的深度优先遍历和广度优先遍历图的广度优先遍历用非递归方法很容易理解，非递归方法需要辅助队列Q以及出队、入队函数。四、实验过程及结果分析1、无向图的邻接矩阵的创建和遍历#include#include#defineMAX_NUM20#defineOK1#defineERROR-1#defineMaxVertexNum20//最大顶点数，应由用户定义#defineOK1#defineERROR-1typedefcharVertexType;//顶点类型应由用户定义typedefintEdgeType;//边上的权值类型应由用户定义//定义图的

3、种类类型，yxt有向图，yxw有向网，wxt无向图，wxw无向网typedefenum{yxt,yxw,wxt,wxw}GraphKind;18typedefstruct{VertexTypevexs[MaxVertexNum];//顶点表//邻接矩阵，可看作边表,如果是无权图，1：相邻，0：不相邻EdgeTypeedges[MaxVertexNum][MaxVertexNum];intn;inte;//图中当前的顶点数和边数GraphKindgkind;//图的种类标示}MGraph;inti=0,j=0,k=0;charv1,v2;//弧的两个结点//函数声明intcreat

4、Wxw(MGraph*G);intcreatYxt(MGraph*G);intcreatYxw(MGraph*G);intcreatWxt(MGraph*G);//输出函数intprintGraph(MGraph*G){printf("*********************");inti,j;for(i=0;in;i++){for(j=0;jn;j++)printf("%4d",G->edges[i][j]);printf("");}printf("*********************");returnOK;}//==============

5、==========创建无向网=========================intcreatWxw(MGraph*G){intw;//权值printf("输入图的结点数：");scanf("%d",&G->n);18printf("输入图的边数：");scanf("%d",&G->e);getchar();//接收scanf的回车符//输入结点printf("输入结点，用大写字母标示(要求第一个顶点是A)，如：A：");for(i=0;in;i++){scanf("%c",&G->vexs[i]);}getchar();//接收scanf的回车符//初始化

6、邻接矩阵for(i=0;in;i++)for(j=0;jn;j++)G->edges[i][j]=0;//输入边连接的两个结点printf("输入弧和权值：");for(k=0;ke;k++){//i,j作为矩阵的行和列scanf("%c%c%d",&v1,&v2,&w);getchar();i=v1-'A';j=v2-'A';G->edges[i][j]=w;G->edges[j][i]=w;}returnOK;}//========================创建无向图=========================intcreatWxt(M

7、Graph*G){printf("输入图的结点数：");scanf("%d",&G->n);printf("输入图的边数：");scanf("%d",&G->e);getchar();//接收scanf的回车符//输入结点18printf("输入结点，用大写字母标示(要求第一个顶点是A)，如：A：");for(i=0;in;i++){scanf("%c",&G->vexs[i]);}getchar();//接收scanf的回车符//初始化邻接矩阵for(i=0