发布时间：2015-02-04 来源：人大经济论坛

通过图的邻接矩阵实现图的搜索实现(一)_通信工程毕业论文 摘 要  本课程设计主要解决图的搜索实现，通过图的邻接矩阵实现深度优先搜索和广度优先搜索。图是一种较线形表和树更复杂的数据结构，其应用极为广泛，目前已渗入到语言学，逻辑学，物理，化学以及计算机科学等诸多领域中。在本课程设计中，系统开发平台为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