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) {//对以邻接矩阵表示的图，进行广度优先搜索 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) //对以邻接矩阵表示的图，进行广度优先搜索
对关键代码的说明：开始是建立图的邻接矩阵，对图的结构类型的定义，在子程序中，完成对深度优先搜索和广度优先搜索的建立，在以邻接矩阵表示的图中，分别进行深度优先搜索和广度优先搜索，并在主函数中调用它们。
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
首页 上一页 1 2 3 4 下一页 尾页 2/4/4
