1、 数据结构课程设计 设计题目：图的建立与输出 系 别： 电子与信息工程学院 专 业： 电子信息工程 班 级： 2009 级（1）班 姓 名： 学 号： 指导教师： 2011 年 06 月 20 日 数据结构课程设计 - 2 - 目录 一、设计题目（任选其一）3 二、运行环境（软、硬件环境）3 三、算法设计的思想3 四、算法的流程图3 五、算法设计分析4 六、源代码4 七、运行结果分析14 八、收获及体会16 数据结构课程设计 - 3 - 一、设计题目（任选其一） 图的建立及输出图的建立及输出 任务：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向 网，学生可以任选两种类型） ，能够
2、输入图的顶点和边的信息，并存储到相应存 储结构中，而后输出图的邻接矩阵。 二、运行环境（软、硬件环境） 硬件环境： CPU：1000MHz 以上 内存：256MB 以上 硬盘：60G 以上 软件环境： 系统平台：Windows 2000 / Windows XP / Windows Vista / Windows 7 运行环境：TC 3.0 / Microsoft Visual C+ 6.0 三、算法设计的思想 1、存储结构；邻接矩阵 邻接表 2、遍历方式：深度优先搜索（DFS） 广度优先搜索(BFS) 也可以对邻接矩阵 和临界表直接输出：其中 DFS 算法通过递归实现，BFS 算法通过队列实
3、现。 3、拓扑排序和最小生成树（Prime 算法） ，具体实现见代码。 四、算法的流程图 数据结构课程设计 - 4 - 五、算法设计分析 首先是建图，图和网的区别在于图没有权值（这里以固定值 1 代替） ，网有 权值，有向和无向在存储上的区别在于对于有向图，输入 aij,只存储 aij,而 对于无向图还要存储 aji。 其次是功能的实现，邻接表遍历和邻接矩阵遍历都很简单，按照它的存储结 构，依次输出每个顶点和它邻接的顶点，时间复杂度分别为 O(n+e)和 O(n2)； 对于 DFS 算法是通过函数递归实现的,所采用的存储结构式是邻接表，找邻 接点所需时间为 O(e)，其中 e 为无向图的边数或有向图的弧数，时间复杂度为 O(n+e)。 对于 BFS 算法是用队列实现的，每个顶点至多进一次队列。遍历图的过程实 质上是通过边或弧找邻接点的过程， 因此广度优先搜索遍历图的时间复杂度和深 度优先搜索遍历相同，两者不同之处仅仅在于对每个顶点访问的顺序不同 对于拓扑排序，建立各项顶点的入度的时间复杂度为 O(e)，建零入度顶点栈 的时间复杂度为 O(n)； 在拓扑排序过程中， 若有向图无环， 则每个顶点进一次栈， 出一次栈，入度减 1 的操作在 while 语句中总共执行 e 次，所以总的时间复杂度 为 O(n+e)。 对于 Prime 算法的最小生成树，假设网中有 n
