数据结构课程设计-图的遍历和构建

1 摘 要 图 Graph 是一种复杂的非线性结构 图可以分为无向图 有向图 若将 图的每条边都赋上一个权 则称这种带权图网络 在人工智能 工程 数学 物理 化学 计算机科学等领域中 图结构有着广泛的应用 在图结构中 对 结点 图中常称为顶点 的前趋和后继个数都是不加以限制的 即结点之间的 关系是任意的 图中任意两个结点之间都可能相关 图有两种常用的存储表示 方法 邻接矩阵表示法和邻接表表示法 在一个图中 邻接矩阵表示是唯一的 但邻接表表示不唯一 在表示的过程中还可以实现图的遍历 深度优先遍历和 广度优先遍历 及求图中顶点的度 当然对于图的广度优先遍历还利用了队列 的五种基本运算 置空队列 进队 出队 取队头元素 判队空 来实现 这 不仅让我们巩固了之前学的队列的基本操作 还懂得了将算法相互融合和运用 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 图的广度优先遍历 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 第一章第一章 课程设计目的课程设计目的 本学期我们对 数据结构 这门课程进行了学习 这门课程是一门实践性非常强的课 程 为了让大家更好地理解与运用所学知识 提高动手能力 我们进行了此次课程设计 数据结构是计算机软件和计算机应用专业的核心课程之一 在众多的计算机系统软件和应 用软件中都要用到各种数据结构 这次课程设计不但要求学习者掌握 数据结构 中的各 方面知识 还要求学习者具备一定的 C 语言基础和编程能力 具体说来 这次课程设计主 要有两大方面目的 一是让学习者通过学习掌握 数据结构 中的知识 对于 图的存储与遍历 这一课 题来说 所要求掌握的数据结构知识主要有 图的邻接矩阵存储 图的邻接表存储 队列 的基本运算实现 邻接矩阵的算法实现 邻接表的算法实现 图的广度优先遍历算法实现 图的深度优先遍历算法实现 二是通过学习巩固并提高学习者的 C 语言知识 并初步了解 Visual C 的知识 提高 其编程能力与专业水平 第二章第二章 课程设计内容和要求课程设计内容和要求 2 12 1 课程设计内容课程设计内容 该课题要求以邻接矩阵和邻接表的方式存储图 输出邻接矩阵和邻接表 并要求实现 图的深度 广度两种遍历及顶点的度 2 1 12 1 1 图的邻接矩阵的建立与输出图的邻接矩阵的建立与输出 对任意输入顶点数和边数的图 若对无向图进行讨论 根据邻接矩阵的存储结构建立 图的邻接矩阵并输出 要求输出的格式是矩阵形式 这样便于直观的了解 2 1 22 1 2 图的邻接表的建立与输出图的邻接表的建立与输出 对任意给定的图 顶点数和边数可以宏定义 若对无向图进行讨论 根据邻接表的存 储结构建立图的邻接表并输出 4 2 1 32 1 3 图的遍历的实现图的遍历的实现 图的遍历包括图的广度优先遍历与深度优先遍历 对于广度优先遍历应利用队列的五 种基本运算 置空队列 进队 出队 取队头元素 判队空 来实现 首先建立一空队列 从初始点出发进行访问 当被访问时入队 访问完出队 并以队列是否为空作为循环控制 条件 对于深度优先遍历则采用递归算法来实现 当然 若存储图的表示不一样 进行两 种遍历的方式也不一样 2 1 42 1 4 图的顶点的度图的顶点的度 在图中 可以求顶点的度 在无向图用邻接矩阵表示 Vi 顶点的度即是该矩阵第 i 行 或第 j 列中非 0 元素的个数之和 若无向图用邻接表表示 顶点 Vi 的度则是第 i 个边表中 的结点个数 2 22 2 运行环境运行环境 该程序的运行环境为 Windows xp 系统 Microsoft Visual C 6 0 版本 第三章第三章 课程设计分析课程设计分析 3 13 1 图的存储图的存储 图的存储表示方法很多 但常用的是 图的矩阵表示和邻接表表示 至于在遇到问题 具体选择哪一种表示法 主要取决于具体的应用和欲施加的操作 3 1 13 1 1 图的邻接矩阵存储表示图的邻接矩阵存储表示 本课题有邻接矩阵存储表示 邻接矩阵是表示顶点之间相邻关系的矩阵 设 G V E 是具有 n 个顶点的图 则 G 的邻接矩阵是具有如下性质的 n 阶方阵 A i j 1 若 Vi Vj 是 E G 中的边 A i j 0 若 Vi Vj 不是 E G 中的边 用邻接矩阵表示 法表示图 除了存储用于表示顶点间相邻关系的邻接矩阵外 通常还需要用一个顺序表存 储顶点信息 因此 我们就要进行定义数据类型 由于无向图的邻接矩阵是对称的 故采 5 用压缩存储方式 仅存储上三角阵 不包括对角线上的元素 中的元素即可 显然 邻接 矩阵表示法的空间杂度 S n O n 2 开始进行类型定义 用输入的方式来控制图的顶点数和边数 并对邻接矩阵进行初始 化 将 G arcs i j 0 再从键盘上获得顶点信息 建立顶点表 在此同时 G arcs i j 1 G arcs j i 1 最后输出邻接矩阵 用两层 for 循环语句来控制 3 1 23 1 2 图的邻接表存储表示图的邻接表存储表示 另外还有邻接表的存储表示 邻接表是一种链式的存储结构 在邻接表中 对图中每 个顶点建立一个单链表 第 i 个单链表中的结点表示依附于顶点 Vi 的边 每个结点由 2 个 域组成 其中邻接点域 adjvex 指示与顶点 Vi 邻接的点在图中的位置 链域 next 指 示下一条边的结点 所以一开始必须先定义邻接表的边结点类型以及邻接表类型 并对邻接表进行初始化 然后根据所输入的相关信息 包括图的顶点数 边数以及各条边的起点与终点序号 建立 图的邻接表 对于无向图 一条边的两的个顶点 互为邻接点 所以在存储时 应向起点 的单链表表头插入一边结点 即终点 同时将终点的单链表表头插入一边结点 即起点 对于邻接表的输出 采用 for 语句输出各结点 3 23 2 图的遍历图的遍历 和树的遍历类似 图的遍历也是从某个顶点出发 沿着某条搜索路径对图中所有的顶 点各作一次访问 若给定的图是连通图 则从图中任一顶点出发顺着边可以访问到该图的 所有顶点 图的遍历比树的遍历复杂得多 这是因为图中的任一顶点都可能和其余顶点相 邻接 故在访问了某个顶点之后 可能顺着某条回路又回到了顶点 为了避免重复访问同 一个顶点必须记住每个顶点是否被访问过 为此 可设置一个布尔向量 visited n 它的 初始值为 0 一旦访问了顶点 Vi 便将 visited i 1 置为 1 根据搜索路径的方向不同 有两种常用的遍历图的方法 深度优先遍历和广度优先遍 历 6 3 2 13 2 1 图的深度优先遍历图的深度优先遍历 假设给定图 G 的初态是所有顶点未曾被访问 在 G 中任选一顶点 Vi 为初始出发点 则 深度优先遍历可定义如下 首先 访问出发点 Vi 并将其标记为已访问过 然后 依次从 Vi 出发搜索 Vi 的每一个邻接点 Vj 若 Vj 未曾访问过 则以 Vj 为新的出发点继续进行深 度优先遍历 显然这是一个递归的过程 它的特点是尽可能先对纵深方向进行搜索 故称 之为深度优先遍历 在实现深度优先遍历的过程中必须递归调用深度优先搜索函数 具体过程应为 先访问初始点 Vi 并标志其已被访问 此时定义一指向边结点的指针 p 并建立一个 while 循环 以指针所指对象不为空为控制条件 当 Vi 的邻接点未被 访问时 递归调用深度优先遍历函数访问之 然后将 p 指针指向下一个边结点 这样就可 以完成图的深度优先遍历了 对图进行深度优先遍历时 按访问顶点的先后顺序所得到的顶点序列 称为该图的深 度优先遍历序列 简称 DFS 序列 一个图的 DFS 序列不唯一 它与算法 图的存储结构以 及初始出发点有关 在 DFS 算法中 当从 Vi 出发搜索时 是在邻接矩阵的第 i 行中从左至 右选择下一个未曾访问的邻接点作为新的出发点 若这种邻接点多于一个 则选中的是序 号较小的那一个 因为图的邻接矩阵表示是唯一的 故对于指定的初始出发点 有 DFS 算 法所得的 DFS 序列是序列是唯一的 3 2 23 2 2 图的广度优先遍历图的广度优先遍历 广度优先搜索遍历类似于树的按层次遍历的过程 设图 G 中某顶点 Vi 出发 在访问了 Vi 之后访问它们的邻接点 并使 先被访问的顶点的邻接点 先于 后被访问的顶点的邻 接点的邻接点 被访问 直到图中所有已被访问的顶点的邻接点都被访问到 若此时图中 尙有顶点未被访问 则另选图中一个未曾被访问的顶点作起始点 重复上述过程 直到图 中所有顶点都被访问到为止 换句话说 广度优先搜索遍历图的过程是以 Vi 为起始点 由 近及远 依次访问和 Vi 有路径相通且路径长度为 1 2 的顶点 所以要实现算法必须先建立一个元素类型为整型的空队列 并定义队首与队尾指针 同时也要定义一个标志数组以标记结点是否被访问 同样 也是从初始点出发开始访问 访问初始点 标志其已被访问 并将其入队 当队列非空时进行循环处理 当结点被访问 时对其进行标志 并入队列 通过 while 循环 并以是否被访问为控制条件 访问所 7 有结点 完成图的广度优先遍历 和定义图的 DFS 序列类似 我们可将广度优先遍历图所得到的顶点序列 定义为图的广 度优先搜索遍历序列 简称 BFS 序列 一个图的 BFS 序列也是不唯一的 它与算法 图的 存储结构以及初始出发点有关 3 33 3 图的顶点的度图的顶点的度 若无向图用邻接矩阵表示 Vi 顶点的度即是该矩阵第 i 行或第 j 列中非 0 元素的个数 之和 若无向图用邻接表表示 Vi 的度分为出度和入度 出度即是表结点的个数 入度即 是逆邻接表的出度 第四章第四章 算法 数据结构 描述算法 数据结构 描述 4 14 1 图的存储结构的建立 图的存储结构的建立 4 1 14 1 1 定义邻接矩阵的定义类型定义邻接矩阵的定义类型 typedef int datatype typedef struct char vexs max int arcs max max int vexsnum arcsnum 顶点个数及边的个数 graph 4 1 24 1 2 定义邻接表的边结点类型以及邻接表类型定义邻接表的边结点类型以及邻接表类型 typedef char vextype typedef struct node int adjvex 邻接点域 8 struct node next 链域 enode 边表结点 typedef struct vextype vertex 顶点信息 enode link 边表头指针 vnode 顶点表结点 4 1 34 1 3 初始化图的邻接矩阵初始化图的邻接矩阵 for i 0 ivexsnum i G vexs i getchar for i 0 ivexsnum i for j 0 jvexsnum j G arcs i j 0 4 1 44 1 4 初始化图的邻接表初始化图的邻接表 需建立一个邻接表初始化函数对图的邻接表进行初始化 即建立一个所有边结点都为 空的邻接表 for i 0 inext 这样就可 以访问所有结点 完成图的广度优先遍历 广度优先遍历的相关代码在下面的源代码中给出 4 34 3 mainmain 函数函数 在 main 函数中运用了菜单 用主菜单来控制是选择邻接矩阵的存储表示还是邻接表的 存储表示 用子菜单来控制选择深度优先遍历还是广度优先遍历 10 4 44 4 图的大致流程表图的大致流程表 图的存储与遍 历 邻接矩阵表示 法 邻接表表示法 深度优先遍历广度优先遍历深度优先遍历广度优先遍历各顶点的度各顶点的度 第五章第五章 源代码源代码 程序 图的存储与遍历 include include define max 6 typedef int datatype typedef struct char vexs max int arcs max max int vexsnum arcsnum 顶点个数及边的个数 graph void creatgraph graph G 建立邻接矩阵的无向图 int i j k sum 11 printf 请输入顶点个数及边的个数 n scanf d d printf 请读入顶点信息 建立顶点表 n getchar for i 0 ivexsnum i G vexs i getchar for i 0 ivexsnum i for j 0 jvexsnum j G arcs i j 0 邻接矩阵初始化 printf 请输入相邻接的两边的顶点信息 n for k 0 karcsnum k scanf d d G arcs i j 1 G arcs j i 1 读入边 Vi Vj printf 输出的邻接矩阵为 n for i 0 ivexsnum i printf n for j 0 jvexsnum j printf 3d G arcs i j 邻接矩阵的输出 printf n 输出邻接矩阵 Vi 顶点的度为 n for i 0 ivexsnum i sum 0 for j 0 jvexsnum j if G arcs i j 1 sum 12 printf V d 的度为 d n i sum 各顶点的度 define n 4 define m 5 typedef char vextype typedef struct node int adjvex 邻接点域 struct node next 链域 enode 边表结点 typedef struct vextype vertex 顶点信息 enode link 边表头指针 vnode 顶点表结点 vnode a n void creatlist 建立无向图的邻接表 int i j k sum enode s printf 请读入顶点信息 建立顶点表 n getchar for i 0 i n i a i vertex getchar a i link NULL 边表头指针初始化 printf 请输入相邻接的两边的顶点信息 n for k 0 kadjvex j s next a i link a i link s 将 s 插入顶点 Vi 的边表头部 s enode malloc sizeof enode 生成邻接点序号为 i 的边表结点 s s adjvex i s next a j link a j link s 将 s 插入顶点 Vj 的边表头部 printf 输出的邻接表为 n for i 0 i s adjvex s s next 邻接表的输出 printf 输出邻接表 Vi 顶点的度为 n for i 0 inext printf V d 的度为 d n i sum 各顶点的度 int visited1 max 0 定义布尔向量 visited1 为全程量 void dfs1 graph G int i 从 Vi 1 出发深度优先搜索图 G G 用邻接矩阵表示 int j printf node c n G vexs i 访问出发点 Vi 1 visited1 i 1 标记 Vi 1 已被访问 for j 0 jvexsnum j 依次搜索 Vi 1 的邻接点 if G arcs i j 若 Vi 1 的邻接点 Vi 1 未曾访问过 则从 Vi 1 出发进 行深度优先搜索 define maxsize 80 typedef int datatype typedef struct datatype data maxsize int front rear sequeue 顺序队列的类型 sequeue p p 是顺序队列类型的指针 void setnull 置队列 p 为空对 p front maxsize 1 p rear maxsize 1 15 int empty 判别 p 是否为空 if p front p rear return 1 else return 0 int front 取 p 的队头元素 if empty printf the sequeue is empty return 0 else return p data p front 1 maxsize int enqueue int x 将新元素 x 插入队列 p 的队尾 if p rear 1 maxsize p front printf the queue is full return 0 else p rear p rear 1 maxsize p data p rear x return x 16 int dequeue 删除队列 p 的头元素 并返回该元素 if empty printf the sequeue is empty return 0 else p front p front 1 maxsize return p data p front int visited2 max 0 void bfs1 graph G int k 从 Vi 1 出发广度优先搜索图 G G 用邻接矩阵表示 int i j setnull printf node c n G vexs k 访问出发点 Vk 1 visited2 k 1 enqueue k while empty 队非空时执行 i dequeue for j 0 jvexsnum j if G arcs i j 访问 Vi 1 的未曾访问的邻接点 Vj 1 visited2 j 1 enqueue j 访问过的顶点入队 17 int visited3 n 0 void dfs2 int i 从 Vi 1 出发深度优先遍历搜索图 a a 图用邻接表表示 enode p printf node c n a i vertex visited3 i 1 p a i link 取 Vi 1 的边表头指针 while p NULL 依次搜索 Vi 1 的邻接点 if visited3 p adjvex dfs2 p adjvex 从 Vi 1 的未曾访问过的邻接点出发进行深度优先搜索 p p next 找 Vi 1 下一个邻接点 int visited4 n 0 void bfs2 int k 从 Vi 1 出发广度优先搜索图 a a 用邻接表表示 int i enode p setnull printf node c n a k vertex visited4 k 1 enqueue k while empty i dequeue p a i link 取 Vi 1 的边表头指针 while p NULL 依次搜索 Vi 1 的邻接点 18 if visited4 p adjvex 访问 Vi 1 的未曾访问的邻接点 printf node c n a p adjvex vertex visited4 p adjvex 1 enqueue p adjvex 访问过的顶点入队 p p next 找 Vi 1 的下一个邻接点 void main int i j x y z s t graph a int flag 0 p sequeue malloc sizeof sequeue printf 欢迎进入 n while 1 printf 请选择输入 n1 为用邻接矩阵存储图 n2 为用邻接表存储图 n0 为 退出 n scanf d switch x case 1 creatgraph while flag 0 printf 请选择输入 n1 为邻接矩阵深度优先遍历 n2 为邻接矩阵 广度优先遍历 n0 为返回继续选择图的存储 n 19 scanf d switch y case 1 printf 请输入深度优先遍历的顶点 n scanf d dfs1 break case 2 printf 请输入广度优先遍历的顶点 n scanf d bfs1 break case 0 flag 1 break case 2 creatlist while flag 0 printf 请选择输入 n1 为邻接表深度优先遍历 n2 为邻接表广度优先遍历 n0 为返回继续选择图的存储 n scanf d switch z case 1 printf 请输入深度优先遍历的顶点 n scanf d dfs2 s break case 2 printf 请输入广度优先遍历的顶点 n scanf d bfs2 t break case 0 flag 1 break case 0 exit 0 20 第六章第六章 测试结果测试结果 由于学习之初对图的存储结构了解不是很清楚 所以在运行出了错误 首先在运行当 中少了一句算法 在建立邻接表 输入顶点信息时 少了 getchar 语句 因为程序本身 没报错 但是在执行的过程中出现了错误的信息 而且总是在执行邻接表操作时出错 另 外在宏定义时定义了