实 验 五 图 的 存 储 与 遍 历 1、 实 验 目 的 掌 握 图 这 种 复 杂 的 非 线 性 结 构 的 邻 接 矩 阵 和 邻 接 表 的 存 储 表 示 ， 以 及 在 此 两种 常 用 存 储 方 式 下 深 度 优 先 遍 历 (dfs)和 广 度 优 先 遍 历 （ BFS） 操 作 的 实 现 。 2、 实 验 预 备 知 识 （ 1） 图 的 存 储 结 构 ： 邻 接 矩 阵 表 示 法 和 邻 接 表 表 示 法 。 邻 接 矩 阵 表 示 法 除了 要 用 一 个 二 维 数 组 存 储 用 于 表 示 顶 点 间 相 邻 关 系 的 邻 接 矩 阵 外 ，还 需 用 一 个 一维 数 组 来 存 储 顶 点 信 息 ， 另 外 还 有 图 的 顶 点 数 和 边 数 。 邻 接 表 表 示 法 类 似 于 树 的孩 子 链 表 表 示 法 。 （ 2） 图 的 遍 历 方 法 有 深 度 优 先 遍 历 （ Depth－ First Traersal） 和 广 度 优 先遍 历 （ Breadth－ First Traversal） ， 简 称 DFS 和 BFS。 DFS 对 图 遍 历 时 尽 可 能先 对 纵 深 方 向 进 行 搜 索 ； BFS 是 类 似 于 树 的 按 层 次 遍 历 。 3、 实 验 内 容 题 目 1 对 以 邻 接 矩 阵 为 存 储 结 构 的 图 进 行 DFS 和 BFS 遍 历 (1) 问 题 描 述 ： 以 邻 接 矩 阵 为 图 的 存 储 结 构 ， 实 现 图 的 DFS 和 BFS 遍 历 。 (2) 基 本 要 求 ： 建 立 一 个 图 的 邻 接 矩 阵 表 示 ， 输 出 顶 点 的 一 种 DFS 和 BFS 序列 。 (3) 测 试 数 据 ： 如 图 4．18 所示 。 (4) 实 现 提示 ： 图 的 DFS 遍 历 可 通过递归调用 或用 栈来 实 现 。 其思想是 ： 只要 当前结 点 未访问 过， 就访问 该结 点 ， 沿着其一 条分支深 入下 去， 每深 入一 个 未访问 过的 结 点 ， 就访问 这 个 结 点 ， 然后从这 个 结 点 继续进 行 DFS 遍 历 。 在 这 一 过程中， 若深 入时 遇到一 个 已访问 过的 结 点 ， 则查找是 否有 与 这 个 结 点 相 邻 的 下 一个 未访问 过的 结 点 。 若有 则继续深 人， 否则将退...
VIP
