评价网 > 科教论文 > 工学毕业论文 > 通信工程论文 > 正文

通过图的邻接矩阵实现图的搜索实现(一)-通信工(3)

2013-06-25 01:21 sp;          3  ∞   ∞   3   4   ∞
 3  ∞   ∞   ∞  ∞   3
 ∞  3   ∞   ∞  ∞  ∞
 ∞  4   ∞   ∞  ∞  ∞
 ∞  ∞  3    ∞  ∞  ∞
 图5 .2 测试数据用图邻接矩阵
 
 测试过程中此本次程序设计好后经调试运行后的结果截图：（见图）  
 图5.3 选择有向图
如图5.3：程序开始运行时会要求输入图的类型，此处输入0表示选择有向图
 

 图5.4 输入图的边数和结点数
如图5.4：在程序分别输入结点数6和边数5，再从1至6分别输入结点数，构造图的大小
 

 图5.5 输入图的各结点和权值
如图5.5：在程序中，分别输入相连两结点和连接两结点的边的权
 

                      图5.6深度优先搜索输出结果
如图5.6：深度优先搜索输出过程为1—2—4—5—3—6

 图5 .7选择无向图
 
如图5.7：程序开始运行时会要求输入图的类型，此处输入1表示选择无向图

 图5.8输入图的边数和结点数
如图5.8：在程序分别输入结点数6和边数5，再从1至6分别输入结点数，构造图的大小

 图5.9输入图的各结点和权值
如图5.9：在程序中，分别输入相连两结点和连接两结点的边的权

 图5.10广度优先搜索输出结果
如图5.10：广度优先搜索输出过程为1—2—3—4—5—6

6应用探讨
 通过本次设计的最终程序我们可以看到：通过建立已定义好的图的邻接矩阵类型，然后用子函数写出深度优先搜索遍历及广度优先搜索遍历，再用主函数调用实现。这样我们可以对图进行周游，从而实现图的搜索。而且从运行结果中还可以对两种遍历结果进行比较。虽然本程序生成的结果只是一排按图的顶点的排序，但是我们在实际的软件开发中可以将其运用到其中以实现我们日常的各种搜索软件中。 您可以访问中国科教评价网（www.NsEac.com）查看更多相关的文章。
 
7结束语
 由于平时对编程相关的知识掌握不够深刻，在本次程序设计中遇到了很多麻烦，经常会出现改正一个错误产生更多错误的情况，很多语言运用都出现了错误，最后改用C语言，并在同学帮助下终于、完成了对程序的调试。本次程序设计实践，使我更进一步的掌握了C语言编程的运用，并且在编写程序中进一步学习了运用数据结构与算法实现程序功能，对图的深度搜索，广度搜索，有了很多新的理解，同时认识到了算法在编程中的重要性，不过由于时间紧迫，很多问题到现在还不能理解，课程设计所作的一些要求还没有达到。
 正所谓台上一分钟，台下十年功，只有平时多加刻苦，在我们遇到有关方面的问题时才不会显得那么束手无策。
 
参考文献
[1] 许卓群，杨冬青，唐世渭，张铭.数据结构与算法.北京：高等教育出版社，2005
[2] 陈志泊，王春玲.面向对象的程序设计语言——C++.北京：人民邮电出版社，2005
[3] 潭浩强. C程序设计.北京：清华大学出版社，2004

附录：图的搜索源程序清单
//图的搜索实现
#include <stdio.h>
#define maxvertexnum 100//设置邻接矩阵的最大阶数
#define queuesize 100//设置循环队列的最大空间
typedef struct{
　　int front,rear,count,data[queuesize];
　}cirqueue;//循环队列结构定义
typedef int vertextype;//设置图的顶点信息为整型
typedef int edgetype;//设置边上权值为整型
typedef struct{
　　vertextype vexs[maxvertexnum];//图的顶点信息表
　　edgetype edges[maxvertexnum][maxvertexnum];//图的邻接矩阵
　　int n,e;//图的顶点数和边数
　}mgraph;//图的邻接矩阵表示结构定义 （科教范文网 fw.nseac.com编辑发布）
typedef enum{FALSE,TRUE}boolean;
boolean visited[maxvertexnum];//顶点访问标记向量

main()//主函数
　{//建立用邻接矩阵表示的图，并进行深度优先搜索和广度优先搜索
　　mgraph *g;
　　g=(mgraph*)malloc(sizeof(mgraph));//申请图g的邻接矩阵表示空间
　　createmgraph(g);//建立图g
　　printf("the dfs is:");//对图g进行深度优先搜索
　　dfstraverse(g);
　　printf("the bfs is:");//对图g进行广度优先搜索
　　bfstraverse(g);
　}

createmgraph(mgraph *g)
　{//建立图g的邻接矩阵表示
　　int i,j,k,w;
　　int flag;
　　printf("\ncreat:\n");
　　printf("digragh--0\n");
　　printf("undigragh--1\n");
　　scanf("%d",&flag);
　　printf("input n,e\n");
　　scanf("%d%d",&g->n,&g->e);//输入图*g的顶点数和边数
　　printf("input nodes:\n");
　　for(i=0;i<g->n;i++)//输入n个顶点的信息
　　　　scanf("%d",&(g->vexs[i]));
　　for(i=0;i<g->n;i++)//将邻接矩阵数组初始化
　　　for(j=0;j<g->n;j++)
　　　　g->edges[i][j]=0;
　　for(k=0;k<g->e;k++){//读入n有向边对应的三元组(i,j,w),若构造有向图，
　　　　　　　　　　　　//i为有向边的弧尾，j是有向边的弧头，