1、1/28 数据结构 课程设计报告 设计题目： 图的基本操作与实现 专 业 班 级 学 生 学 号 指导教师 起止时间 年 学期 2/28 目目 录录 1.问题描述：问题描述：实现图的一些基本操作 . 2 2.基本要求：基本要求： . 2 (2)求每个顶点的度,输出结果； 3 3.测试数据：测试数据： . 3 4.算法思想：算法思想： . 3 (1)(1)自选存储结构创建一个图：自选存储结构创建一个图： . 3 (2)(2)求每个顶点的度：求每个顶点的度： . 3 (3)(3)图的深度优先遍历：图的深度优先遍历： . 4 (4)(4)图的广度优先遍历：图的广度优先遍历： . 4 (5)判断有向图
2、的强连通性：判断有向图的强连通性： 4 (6)用邻接矩阵的信息生成邻接表：用邻接矩阵的信息生成邻接表： 4 6.数据结构：数据结构： . 5 7.7.功能模块图功能模块图 7 8.8.源程序：源程序： 7 9.9.心得体会：心得体会： 27 1.问题描述问题描述：实现图的一些基本操作 2.基本要求：基本要求： 3/28 (1)自选存储结构,输入含 n 个顶点（用字符表示顶点）和 e 条边的图 G； (2)求每个顶点的度,输出结果； (3)指定任意顶点 x 为初始顶点,对图 G 作 DFS 遍历,输出 DFS 顶点序列(提示: 使用一个栈实现 DFS)； (4)指定任意顶点 x 为初始顶点,对图
3、 G 作 BFS 遍历,输出 BFS 顶点序列(提示: 使用一个队列实现 BFS)； (5)输入顶点x,查找图G:若存在含x的顶点,则删除该结点及与之相关连的边, 并作 DFS 遍历(执行操作 3)；否则输出信 息“无 x”； (6)判断图 G 是否是连通图，输出信息“YES”/“NO” ； (7)如果选用的存储结构是邻接矩阵,则用邻接矩阵的信息生成图 G 的邻接表, 即复制图 G,然再执行操作(2)；反之亦然。 3.测试数据测试数据： 有向图的顶点数 n 和有向图的边数 e 由用户从键盘敲入 4.算法思想算法思想： (1)(1)自选存储结构自选存储结构创建一个图：创建一个图：通过用户从键盘敲
4、入的两个数值分别确定图的 顶点数和边数， 选择邻接矩阵存储结构将图的结点信息存储在一个顺序表中， 图的 边信息存储在一个二维数组中。 (2)(2)求每个顶点的度：求每个顶点的度： 1.邻接矩阵存储结构下求每个顶点的度： 利用图的邻接矩阵， 每个顶点所在行 和所在列的边的权值如果存在则该顶点的度+1， 依次算出每个顶点的度， 并且记录 在一个数组中输出。 2.邻接表存储结构下求每个顶点的度： 定义一个邻接边指针循环指向顶点的邻 接边单链表头结点，当结点不空时，该顶点的出度+1,邻接边弧头结点的入度+1， 依次求出每个顶点的出度和入度之和就为该顶点的度。 4/28 (3)(3)图的深度优先遍历：图
5、的深度优先遍历：采取邻接矩阵结构，指定任意顶点 x 为初始顶点 1.访问结点 v 并标记结点 v 已访问； 2.查找结点 v 的第一个邻接结点 w； 3.若结点 v 的邻接结点 w 存在，则继续执行，否则算法结束； 4.若结点 w 尚未被访问，则递归访问结点 w； 5.查找结点 v 的 w 邻接结点的下一个邻接结点 w,转到步骤 3。 (4)(4)图的广度优先遍历：图的广度优先遍历：采取邻接矩阵结构，指定任意顶点 x 为初始顶点，利 用顺序循环队列以保持访问过的结点的顺序 1.首先访问初始结点 v 并标记结点 v 为已访问； 2.结点 v 入队列； 3.当队列非空时则继续执行，否则算法结束；
6、4.出队列取得队头结点 u； 5.查找 u 的第一个邻接结点 w； 6.若 u 的邻接结点 w 不存在则转到步骤 3，否则循环执行下列步骤： 6.1 若结点 w 尚未被访问，则访问结点 w 并标记结点 w 为已访问； 6.2 结点 w 入队列； 6.3 查找结点 u 的 w 邻接结点的下一个邻接结点 w，转到步骤 6 。 (5)判断有向图的强连通性：判断有向图的强连通性：采取邻接表结构，在图中寻找一个包含所有顶点 且首尾相连的环，若这样的环存在，则该图为强连通图，否则不为强连通图。 (6)用邻接矩阵的信息生成用邻接矩阵的信息生成邻接表邻接表：定义一个邻接表的边信息结构体，将邻接 矩阵的边信息转换成邻接表的边信息存储到邻接边的单链表中。 5.模块划分模块划分： mian():主函数模块。在主函数模块中调用以下函数： (1) v voidoid CreatGraph(AdjMGraphCreatGraph(AdjMGraph *G,DataType v,int *G,DataType v,
