发布时间 : 星期一 文章数据结构课程设计-图的遍历和构建更新完毕开始阅读2964e7a0f524ccbff1218486
摘 要
图（Graph）是一种复杂的非线性结构。图可以分为无向图、有向图。若将图的每条边都赋上一个权，则称这种带权图网络。在人工智能、工程、数学、物理、化学、计算机科学等领域中，图结构有着广泛的应用。在图结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加以限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。图有两种常用的存储表示方法：邻接矩阵表示法和邻接表表示法。在一个图中，邻接矩阵表示是唯一的，但邻接表表示不唯一。在表示的过程中还可以实现图的遍历（深度优先遍历和广度优先遍历）及求图中顶点的度。当然对于图的广度优先遍历还利用了队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。这不仅让我们巩固了之前学的队列的基本操作，还懂得了将算法相互融合和运用。
1
目 录
第一章 课程设计目的 ..................................................................................................................... 3 第二章 课程设计内容和要求 ......................................................................................................... 3
2.1课程设计内容 .................................................................................................................... 3
2.1.1图的邻接矩阵的建立与输出 ................................................................................ 3 2.1.2图的邻接表的建立与输出 .................................................................................... 3 2.1.3图的遍历的实现 .................................................................................................... 4 2.1.4 图的顶点的度 ....................................................................................................... 4 2.2 运行环境 ........................................................................................................................... 4 第三章 课程设计分析 ..................................................................................................................... 4
3.1图的存储 ............................................................................................................................ 4
3.1.1 图的邻接矩阵存储表示 ..................................................................................... 4 3.1.2 图的邻接表存储表示 ........................................................................................... 5 3.2 图的遍历 ........................................................................................................................... 5
3.2.1 图的深度优先遍历 ............................................................................................... 5 3.2.2 图的广度优先遍历 ............................................................................................... 6 3.3图的顶点的度 .................................................................................................................... 7 第四章 算法（数据结构）描述 ..................................................................................................... 7
4.1 图的存储结构的建立。 ................................................................................................... 7
4.1.1 定义邻接矩阵的定义类型 ................................................................................... 7 4.1.2定义邻接表的边结点类型以及邻接表类型 ........................................................ 7 4.1.3初始化图的邻接矩阵 ............................................................................................ 8 4.1.4 初始化图的邻接表 ............................................................................................... 8 4.2 图的遍历 ........................................................................................................................... 8
4.2.1 深度优先遍历图 ................................................................................................... 8 4.2.2 广度优先遍历图 ................................................................................................... 9 4.3 main函数 .......................................................................................................................... 9 4.4 图的大致流程表 ............................................................................................................. 10 第五章 源代码 ............................................................................................................................... 10 第六章 测试结果 ........................................................................................................................... 20 第七章 思想总结 ........................................................................................................................... 21 第八章 参考文献 ........................................................................................................................... 22
2
第一章 课程设计目的
本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计。数据结构是计算机软件和计算机应用专业的核心课程之一，在众多的计算机系统软件和应用软件中都要用到各种数据结构。这次课程设计不但要求学习者掌握《数据结构》中的各方面知识，还要求学习者具备一定的C语言基础和编程能力。具体说来，这次课程设计主要有两大方面目的：
一是让学习者通过学习掌握《数据结构》中的知识。对于《图的存储与遍历》这一课题来说，所要求掌握的数据结构知识主要有：图的邻接矩阵存储、图的邻接表存储、队列的基本运算实现、邻接矩阵的算法实现、邻接表的算法实现、图的广度优先遍历算法实现、图的深度优先遍历算法实现。
二是通过学习巩固并提高学习者的C语言知识，并初步了解Visual C++的知识，提高其编程能力与专业水平。
第二章 课程设计内容和要求
2.1课程设计内容
该课题要求以邻接矩阵和邻接表的方式存储图，输出邻接矩阵和邻接表，并要求实现
图的深度、广度两种遍历及顶点的度。
2.1.1图的邻接矩阵的建立与输出
对任意输入顶点数和边数的图，若对无向图进行讨论，根据邻接矩阵的存储结构建立
图的邻接矩阵并输出。要求输出的格式是矩阵形式，这样便于直观的了解。
2.1.2图的邻接表的建立与输出
对任意给定的图（顶点数和边数可以宏定义），若对无向图进行讨论，根据邻接表的存储结构建立图的邻接表并输出。
3
2.1.3图的遍历的实现
图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归算法来实现。当然，若存储图的表示不一样，进行两种遍历的方式也不一样。
2.1.4 图的顶点的度
在图中，可以求顶点的度。在无向图用邻接矩阵表示，Vi顶点的度即是该矩阵第i行或
第j列中非0元素的个数之和。若无向图用邻接表表示，顶点Vi的度则是第i个边表中的结点个数。
2.2 运行环境
该程序的运行环境为Windows xp系统，Microsoft Visual C++6.0版本。
第三章 课程设计分析
3.1图的存储
图的存储表示方法很多，但常用的是：图的矩阵表示和邻接表表示。至于在遇到问题具体选择哪一种表示法，主要取决于具体的应用和欲施加的操作。
3.1.1 图的邻接矩阵存储表示
本课题有邻接矩阵存储表示，邻接矩阵是表示顶点之间相邻关系的矩阵。设G=（V，E） 是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：A[i,j]=1：若（Vi，Vj）是E（G）中的边；A[i,j]=0：若（Vi，Vj）不是E(G)中的边。用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表存储顶点信息。因此，我们就要进行定义数据类型。由于无向图的邻接矩阵是对称的，故采用压缩存储方式，仅存储上三角阵（不包括对角线上的元素）中的元素即可。显然，邻接矩阵表示法的空间杂
4