图的搜索实现（邻接矩阵）

摘 要  本课程设计主要解决图的搜索实现，通过图的邻接矩阵实现深度优先搜索和广度优先搜索。图是一种较线形表和树更复杂的数据结构，其应用极为广泛，目前已渗入到语言学，逻辑学，物理，化学以及计算机科学等诸多领域中。在本课程设计中，系统开发平台为Windows xp，程序设计设计语言主要采用C语言，程序运行平台为Windows 2000/XP。程序开始后，通过输入各结点与边的相关数据，可以得出相应的深度优先和广度优先搜索结果。

关键词  程序设计；C语言；图的邻接矩阵；图的深度优先搜索、广度优先搜索
 
1 引  言
图是一种较复杂的数据结构，图的搜索在图书索引，城市道路建设，人工智能等领域中发挥着重要作用。图的搜索有深度优先搜索和广度优先搜索，我们可以通过图的邻接矩阵或邻接表实现图的这两种搜索。
本次程序设计我们通过C语言编写程序实现图的搜索。在编写过程中我们将图定义为邻接矩阵类型，通过深度优先搜索遍历和广度优先搜索遍历分别实现图的搜索。
    我们学习两年的有关C语言和数据结构的相关知识，而课程设计是将我们把所学的理论和生产实践相结合的重要环节， 通过这次课程设计，可以使我们所学的专业技能得到巩固、扩大、深入和系统化；培养综合运用所学知识解决图的搜索的能力，初步掌握数据结构程序设计的方法和步骤；使我们进一步提高编写程序的效率；提高我们独立钻研问题的能力，培养严肃认真，实事求是，刻苦钻研的工作作风。

2 开发工具介绍
C 语言是1972年由美国的Dennis Ritchie设计发明的, 并首次在UNIX操作系统DEC PDP-11 计算机上使用。 它由早期的编程语言 BCPL( Basic Combind Programming Language) 发展演变而来。在1970年, AT&T 贝尔实验室的 Ken Thompson根据BCPL语言设计出较先进的并取名为 B的语言, 最后导了C 语言的问世。 随着微型计算机的日益普及, 出现了许多C语言版本。由于没有统一的标准, 使得这些C 语言之间出现了一些不一致的地方。为了改变这种情况, 美国国家标准研究所(ANSI)为C 语言制定了一套ANSI标准,成为现行的C语言标准。
C语言具有强大的功能，它具有以下特点：
1. C是中级语言
它把高级语言的基本结构和语句与低级语言的实用性结合起来。C 语言可以象汇编语言一样对位、字节和地址进行操作, 而这三者是计算机最基本的工作单元。
2. C是结构式语言
结构式语言的显著特点是代码及数据的分隔化, 即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰, 便于使用、维护以及调试。C
语言是以函数形式提供给用户的, 这些函数可方便的调用, 并具有多种循环、条件语句控制程序流向, 从而使程序完全结构化。
3. C语言功能齐全
C 语言具有各种各样的数据类型, 并引入了指针概念, 可使程序效率更高。另外C 语言也具有强大的图形功能,
支持多种显示器和驱动器。而且计算功能、逻辑判断功能也比较强大, 可以实现决策目的。
4. C语言适用范围大
C 语言还有一个突出的优点就是适合于多种操作系统, 如DOS、UNIX,也适用于多种机型。
 3 相关知识
  
 图的概念：图是一种较线形表和树更复杂的数据结构，是一种数据元素间为多对多关系的数据结构，加上一组基本操作构成的抽象数据类型，图作为一种非线性数据结构，被广泛应用于多个技术领域，诸如系统工程、化学分析、统计力学、遗传学、控制论、计算机的人工智能、编译系统等领域。
 图的基本操作：创建、插入、删除、查找等。
 图的几种存储结构类型：图的邻接矩阵表示法，图的邻接表表示法
 深度优先搜索（DFS）:a、深度优先搜索类似于树的前序遍历，也是一遇到顶点就进行访问。其特点是尽可能先对纵深方向进行搜索，因此很容易用递归算法实现。如果将遍历过程中走过的边连接起来，即可得到深度优先遍历生成树。b、深度优先搜索遍历图的算法：首先访问指定的起始顶点v0，从v0出发，访问v0的一个未被访问过的邻接顶点w1，再从w1出发，访问w1的一个未被访问过的顶点w2，然后从w2出发，访问w2的一个未被访问过的邻接顶点w3。依次类推，直到一个所有邻接顶点都被访问过为止。
 广度优先搜索（BFS）:广度优先搜索类似于树的按层次遍历。首先访问指定的起始点v0，从v0出发，访问v0的所有未被访问过的邻接顶点w1，w2，… wk，然后再依次从w1，w2，… wk出发，访问它们的所有未被访问过的邻接顶点，依次类推，直到图中所有未被访问过的邻接顶点都被访问过为止。广度优先遍历的特点是尽可能进行横向搜索，即最先访问的顶点其邻接点也被先访问。因此，借助一个队列来保存已被访问过的顶点序列。访问一个顶点vi时（出队），同时将vi相邻的其余结点入队。每个顶点只能入队一次。

4 程序的设计与实现
4．1 程序相关算法伪代码[3]
 图的深度优先搜索算法伪代码：
 DFS（v）//访问由v到达的所有顶点
 1.  Visited(v)=1;
 2.  for邻接于v的每个顶点w  do
 3．   if Visited(w)=0 then
 4.      DFS(w);
 5.    endif
 6.  endfor  
 7．end DFS
 
图的广度优先搜索算法伪代码：
 BFS(v) //宽度优先搜索G，从顶点v开始执行
     // 所有已搜索的顶点i都标记为Visited(i)=1.
     //Visited的初始分量值全为0
 1. Visited(v)=1; u＝v;
 2. Q=[];//将Q初始化为空队列
 3. loop
 4.   for 邻接于u的所有顶点w  do
 5.     if Visited(w)=0 then
 6.       AddQ(w,Q); //将w放于队列Q之尾
 7.       Visited(w)=1;
 8.     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)
　{//对以邻接矩阵表示的图，进行广度优先搜索
　　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：eva luate， 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    ∞  ∞  ∞
                       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应用探讨
 通过本次设计的最终程序我们可以看到：通过建立已定义好的图的邻接矩阵类型，然后用子函数写出深度优先搜索遍历及广度优先搜索遍历，再用主函数调用实现。这样我们可以对图进行周游，从而实现图的搜索。而且从运行结果中还可以对两种遍历结果进行比较。虽然本程序生成的结果只是一排按图的顶点的排序，但是我们在实际的软件开发中可以将其运用到其中以实现我们日常的各种搜索软件中。
 
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;//图的邻接矩阵表示结构定义
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是有向边的弧头，
                        //w是有向边的权值（建立一般的有向图时，可输入1）
　　　　printf("input i,j,w:\n");
　　　　scanf("%d%d%d",&i,&j,&w);
　　　　g->edges[i][j]=w;
　　　　if (flag)//构造无向图
　　　　　　g->edges[j][i]=w;
　　　}
　}

dfsm(mgraph *g,int i)
　{//对以邻接矩阵表示的图，以序号为i的顶点为出发点进行深度优先搜索
　　int j;
　　printf("visit vertex:%d ",g->vexs[i]);//访问序号为i的顶点
　　visited[i]=TRUE;//将序号为i的顶点设置访问过标记
　　for(j=0;j<g->n;j++)//扫描邻接矩阵的第i行，做以下操作
　　　if ((g->edges[i][j]!=0)&&(!visited[j]))
　　　　　//寻找序号为i的顶点的未访问过的邻接点(设序号为k),
　　　　dfsm(g,j);//以序号为k的顶点为出发点进行深度优先搜索
　}//end of dfsm

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

bfsm(mgraph *g,int k)
　{//对以邻接矩阵表示的图，以序号为k的顶点作为出发点进行广度优先搜索
　　int i,j;
　　cirqueue *q;
　　q=(cirqueue *)malloc(sizeof(cirqueue));//申请循环队列空间*q
　　q->rear=q->front=q->count;//将循环队列*q设置为空队列
　　printf("visit vertex:%d ",g->vexs[k]);//访问序号为k的顶点
　　visited[k]=TRUE;//将序号为k是结点设置为已访问过
　　q->data[q->rear]=k;q->rear=(q->rear+1)%queuesize;q->count++;//将序号为k的顶点入队
　　while(q->count){//若队列不为空，则做以下操作
　　　　i=q->data[q->front];q->front=(q->front+1)%queuesize;q->count--;
　　　　　//将队首元素(序号为i的顶点)出队
　　for(j=0;j<g->n;j++)//寻找序号为i顶点的邻接点，并做如下处理
　　　if((g->edges[i][j]!=0)&&(!visited[j])){//若序号为i的顶点有未访问过邻接点
　　　　　printf("visit vertex:%d ",g->vexs[j]);//访问序号为j的顶点
　　　　　visited[j]=TRUE;//设置序号为j的顶点访问过标记
　　　　　q->data[q->rear]=j;q->rear=(q->rear+1)%queuesize;q->count++;
　　　　　　//将序号为j的顶点入队
　　　　}//end of if
　　　}//end of for
　}//end of bfsm

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