1、 1 摘 要 图（Graph）是一种复杂的非线性结构。图可以分为无向图、有向图。若将 图的每条边都赋上一个权，则称这种带权图网络。在人工智能、工程、数学、物 理、化学、计算机科学等领域中，图结构有着广泛的应用。在图结构中，对结点 （图中常称为顶点）的前趋和后继个数都是不加以限制的，即结点之间的关系是 任意的。图中任意两个结点之间都可能相关。图有两种常用的存储表示方法：邻 接矩阵表示法和邻接表表示法。在一个图中，邻接矩阵表示是唯一的，但邻接表 表示不唯一。在表示的过程中还可以实现图的遍历（深度优先遍历和广度优先遍 历）及求图中顶点的度。当然对于图的广度优先遍历还利用了队列的五种基本运 算（置空队
2、列、进队、出队、取队头元素、判队空）来实现。这不仅让我们巩固 了之前学的队列的基本操作，还懂得了将算法相互融合和运用。 2 目 录 第一章 课程设计目的 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 图的广度优先
3、遍历 . 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 3 第一章第一章 课程设计目的课程设计目的 本学
4、期我们对 数据结构 这门课程进行了学习。 这门课程是一门实践性非常强的课程， 为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计。数据结 构是计算机软件和计算机应用专业的核心课程之一， 在众多的计算机系统软件和应用软件中 都要用到各种数据结构。这次课程设计不但要求学习者掌握数据结构中的各方面知识， 还要求学习者具备一定的 C 语言基础和编程能力。 具体说来， 这次课程设计主要有两大方面 目的： 一是让学习者通过学习掌握数据结构中的知识。对于图的存储与遍历这一课题 来说，所要求掌握的数据结构知识主要有：图的邻接矩阵存储、图的邻接表存储、队列的基 本运算实现、邻接矩阵的算法实
5、现、邻接表的算法实现、图的广度优先遍历算法实现、图的 深度优先遍历算法实现。 二是通过学习巩固并提高学习者的 C 语言知识，并初步了解 Visual C+的知识，提高 其编程能力与专业水平。 第二章第二章 课程设计内容和要求课程设计内容和要求 2.12.1 课程设计内容课程设计内容 该课题要求以邻接矩阵和邻接表的方式存储图，输出邻接矩阵和邻接表，并要求实现 图的深度、广度两种遍历及顶点的度。 2.1.12.1.1 图的邻接矩阵的建立与输出图的邻接矩阵的建立与输出 对任意输入顶点数和边数的图，若对无向图进行讨论，根据邻接矩阵的存储结构建立 图的邻接矩阵并输出。要求输出的格式是矩阵形式，这样便于直
6、观的了解。 2.1.22.1.2 图的邻接表的建立与输出图的邻接表的建立与输出 对任意给定的图（顶点数和边数可以宏定义） ，若对无向图进行讨论，根据邻接表的存 储结构建立图的邻接表并输出。 4 2.1.32.1.3 图的遍历的实现图的遍历的实现 图的遍历包括图的广度优先遍历与深度优先遍历。 对于广度优先遍历应利用队列的五种 基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从 初始点出发进行访问， 当被访问时入队， 访问完出队。 并以队列是否为空作为循环控制条件。 对于深度优先遍历则采用递归算法来实现。当然，若存储图的表示不一样，进行两种遍历的 方式也不一样。 2.1.4 2.1.4 图的顶点的度图的顶点的度 在图中，可以求顶点的度。在无向图用邻接矩阵表示，Vi 顶点的度即是该矩阵第 i 行或 第 j 列中非 0 元素的个数之和。若无向图用邻接表表示，顶点 Vi 的度则是第 i 个边表中的 结点个数。 2.2 2.2 运行环境运行环境 该程序的运行环境为 Windows xp 系统，Microsoft Visual C+6.
