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

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

2013-06-25 01:21 .     endif
 9.   endfor
 10． if Q为空 then  return； endif
 11． DelHead(u,Q);
 12. endloop
 13.end BFS

 

 

 

4．2 程序运行流程图
程序开始运行后，其流程图如下所示：

如图4.1，程序开始运行后，选择0或1分别构造有向图和无向图，然后根据程序的提示分别输入图的结点数，边数和它们之间的对应关系，最后输出深度优先搜索和广度优先搜索的结果。
图4.1程序运行流程图

4．3 代码分析
4．3．1 主要函数的功能：
（1）createmgraph(mgraph *g) 建立图g的邻接矩阵表示
（2）mgraph *g：申请图g的邻接矩阵表示空间
（3）createmgraph(g)：建立图g
（4）dfsm(mgraph *g,int i)：对以邻接矩阵表示的图，以序号为i的顶点为出发点进行深度优先搜索
（5）bfsm(mgraph *g,int k)对以邻接矩阵表示的图，以序号为k的顶点作为出发点进行广度优先搜索
（6）printf("visit vertex:%d ",g->vexs[i])：访问序号为i的顶点
（7）printf("visit vertex:%d ",g->vexs[k])：访问序号为k的顶点
（8）printf("the dfs is:") dfstraverse(g); 输出对图g进行深度优先搜索的结果
（9）printf("the bfs is:"); bfstraverse(g)；输出对图g进行广度优先搜索的结果

4．3．2 本程序的数据结构：　
dfstraverse(mgraph *g)
　{//对以邻接矩阵表示的图，进行深度优先搜索
　　int i;
　　for(i=0;i<g->n;i++)//将图的所有顶点设置为未访问过
　　　　visited[i]=FALSE;
　　for(i=0;i<g->n;i++)//对图*g进行深度优先搜索
　　　if(!visited[i])
　　　　dfsm(g,i);
　　printf("\n");
　}//end of dfstraverse

bfstraverse(mgraph *g)
　{//对以邻接矩阵表示的图，进行广度优先搜索

（科教作文网http://zw.NSEaC.com编辑发布）

　　int i;
　　for(i=0;i<g->n;i++)//将所有顶点设置为未访问过
　　　　visited[i]=FALSE;
　　for(i=0;i<g->n;i++)//对邻接矩阵表示的图进行广度优先搜索
　　　if(!visited[i])
　　　　bfsm(g,i);
　　printf("\n");
　}//end of bfstraverse

4．3．3 本程序的关键代码：
#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;//图的邻接矩阵表示结构定义

 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;
dfsm(mgraph *g,int i)
　//对以邻接矩阵表示的图，以序号为i的顶点为出发点进行深度优先搜索
dfstraverse(mgraph *g)
　//对以邻接矩阵表示的图，进行深度优先搜索
bfsm(mgraph *g,int k)
　//对以邻接矩阵表示的图，以序号为k的顶点作为出发点进行广度优先搜索
bfstraverse(mgraph *g) （科教作文网http://zw.ΝsΕAc.com发布）
　//对以邻接矩阵表示的图，进行广度优先搜索

 

 对关键代码的说明：开始是建立图的邻接矩阵，对图的结构类型的定义，在子程序中，完成对深度优先搜索和广度优先搜索的建立，在以邻接矩阵表示的图中，分别进行深度优先搜索和广度优先搜索，并在主函数中调用它们。

5调试与运行结果 
5．1 调试方法及调试过程
   调试方法： TurboC集成环境有很强的动态调试能力，在程序设计过程中，有如下几种主要调试手段：（1）运行（Run： Run，ctrl-F9) （2）设置断点 （break／watch： toggle breakpoint， Ctrl-F8） (3)变量查看及修改 （Debug：Evaluate， CtrL-F4）（4）查看函数调用情况（Debug： Call stack， Ctrl-F3）（5）查找函数（Debug: Find function）（6）更新屏幕内容（Debug： Refresh disp1ay）（7）设置观察对象（break/watch：Add watch，ctrl-F7）等。
 调试过程：程序第一次运行时，出现了头文件无法辨析和C1202的错误，在把注释，此问题得以解决，不过由于本程序大部分采用结构化程序设计方法，程序是DOS界面，并且数据都保存在内存中，因此稳定性不是很高。除了应严格按照数据的定义外，数值类数据不能输入过大，在测试过程中曾由于输入数据过大，发生了溢出错误，修改数据后此问题得以解决。在主函数的结尾还要加上getch()，否则会因为操作系统版本原因导致无法在TC环境中查看运行结果。
5．2 程序运行结果：
 本次测试数据用图及其邻接矩阵如图5.1所示：
 
 图5.1测试数据用图
 
 
 
 ∞　3   3    ∞  ∞  ∞
            &nb