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

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

2013-06-25 01:21

摘 要  本课程设计主要解决图的搜索实现，通过图的邻接矩阵实现深度优先搜索和广度优先搜索。图是一种较线形表和树更复杂的数据结构，其应用极为广泛，目前已渗入到语言学，逻辑学，物理，化学以及计算机科学等诸多领域中。在本课程设计中，系统开发平台为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语言标准。 （科教作文网 zw.nseac.com整理）
C语言具有强大的功能，它具有以下特点：
1. C是中级语言
它把高级语言的基本结构和语句与低级语言的实用性结合起来。C 语言可以象汇编语言一样对位、字节和地址进行操作, 而这三者是计算机最基本的工作单元。
2. C是结构式语言
结构式语言的显著特点是代码及数据的分隔化, 即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰, 便于使用、维护以及调试。C
语言是以函数形式提供给用户的, 这些函数可方便的调用, 并具有多种循环、条件语句控制程序流向, 从而使程序完全结构化。
3. C语言功能齐全
C 语言具有各种各样的数据类型, 并引入了指针概念, 可使程序效率更高。另外C 语言也具有强大的图形功能,
支持多种显示器和驱动器。而且计算功能、逻辑判断功能也比较强大, 可以实现决策目的。
4. C语言适用范围大
C 语言还有一个突出的优点就是适合于多种操作系统, 如DOS、UNIX,也适用于多种机型。
 3 相关知识
  
 图的概念：图是一种较线形表和树更复杂的数据结构，是一种数据元素间为多对多关系的数据结构，加上一组基本操作构成的抽象数据类型，图作为一种非线性数据结构，被广泛应用于多个技术领域，诸如系统工程、化学分析、统计力学、遗传学、控制论、计算机的人工智能、编译系统等领域。
 图的基本操作：创建、插入、删除、查找等。
 图的几种存储结构类型：图的邻接矩阵表示法，图的邻接表表示法

（转载自科教范文网http://fw.nseac.com）

 深度优先搜索（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