图的两种图的遍历方法

第五章第五章 图图 5 3 图的遍历图的遍历 和树的遍历类似 在此 我们希望从图中某一顶点出发访遍图中其余顶点 且使每一 个顶点仅被访问一次 这一过程就叫做图的遍历 TraversingGraph 图的遍历算法是求解 图 的连通性问题 拓扑排序和求关键路径等算法的基础 然而 图的遍历要比树的遍历复杂得多 因为图的任一顶点都可能和其余的顶点相邻 接 所以在访问了某个顶点之后 可能沿着某条路径搜索之后 又回到该顶点上 例如例如 图 7 1 b 中的 G2 由于图中存在回路 因此在访问了 v1 v2 v3 v4 之后 沿着边 v4 v1 又 可访问到 v1 为了避免同一顶点被访问多次 在遍历图的过程中 必须记下每个已访问过 的顶点 为此 我们可以设一个辅助数组 visited 0 n 1 它的初始值置为 假 或者 零 一旦访问了顶点 vi 便置 visited i 为 真 或者为被访问时的次序号 通常有两条遍历图的路径 深度优先搜索和广度优先搜索有两条遍历图的路径 深度优先搜索和广度优先搜索 它们对无向图和有向图都 适用 5 3 1 深度优先搜索深度优先搜索 深度优先搜索 Depth First Search 遍历类似于树的先根遍历 是树的先根遍历的推 广 其基本思想如下 假定以图中某个顶点 vi 为出发点 首先访问出发点 然后选择一个 vi 的未访问过的邻接点 vj 以 vj 为新的出发点继续进行深度优先搜索 直至图中所有顶 点都被访问过 显然 这是一个递归的搜索过程 现以图 5 3 1 中 G 为例说明深度优先搜索过程 假定 v0 是出发点 首先访问 v0 因 v0 有两个邻接点 v1 v2 均末被访问过 可以选择 v1 作为新的出发点 访问 v1 之后 再 找 v1 的末访问过的邻接点 同 v1 邻接的有 v0 v3 和 v4 其中 v0 已被访问过 而 v3 v4 尚未被访问过 可以选择 v3 作为新的出发点 重复上述搜索过程 继续依次访问 v7 v4 访问 v4 之后 由于与 v4 相邻的顶点均已被访问过 搜索退回到 v7 由于 v7 v3 和 v1 都是没有末被访问的邻接点 所以搜索过程连续地从 v7 退回到 v3 再退回 v1 最后退回 到 v0 这时再选择 v0 的末被访问过的邻接点 v2 继续往下搜索 依次访问 v2 v5 和 v6 止此图中全部顶点均被访问过 遍历过程见图 5 3 1 b 得到的顶点的访问序列为 v0 v1 v3 v7 v4 v2 v5 v7 第五章第五章 图图 a 无向图 G b G 的深度优先搜索过程 图 5 3 1 深度优先搜索遍历过程示例 因为深度优先搜索遍历是递归定义的 故容易写出其递归算法 下面的算法 5 3 是以 邻接矩阵作为图的存储结构下的深度优先搜索遍历算法 算法 5 4 是以邻接表作为图的存 储结构下的深度优先搜索遍历算法 算法算法 5 35 3 int visited NAX VEX 0 void Dfs m Mgraph G int i 从第 i 个顶点出发深度优先遍历图 G G 以邻接矩阵表示 printf 3c G vexs i visited i 1 for j 0 jarcs i j 1 Dfs m 算法 5 4 int visited VEX NUM 0 void Dfs L ALgraph G int i 从第 i 个顶点出发深度优先遍历图 G G 以邻接表表示 printf 3c G i data visited i 1 p G i firstarc while p NULL if visited p adjvex 0 Dfs L G p adjvex p p nextarc dfs L 分析上述算法得知 遍历图的过程实质上是对每个顶点搜索其邻接点的过程 其耗费的 时间取决于所采用的存储结构 假设图有 n 个顶点 那么 当用邻接矩阵表示图时 搜索 一个顶点的所有邻接点需花费的时间为 O n 则从 n 个顶点出发搜索的时间应为 O n2 所以算法 5 1 的时间复杂度是 O n2 如果使用邻接表来表示图时 需花费时间为 第五章第五章 图图 O n e 其中 e 为无向图中边的数目或有向图中弧的数目 算法 5 4 的时间复杂度为 O n e 5 3 2 广度优先搜索广度优先搜索 连通图的广度优先搜索 Breadth FirstSearch 遍历图类似于树的按层次遍历 其基本 思想是 首先访问图中某指定的起始点 Vi 并将其标记为已访问过 然后由 Vi 出发访问与 它相邻接的所有顶点 Vj Vk 并均标记为已访问过 然后再按照 Vj Vk 的次序 访问每一个顶点的所有未被访问过的邻接顶点 并均标记为已访问过 下一步再从这些顶 点出发访问与它们相邻接的尚未被访问的顶点 如此做下去 直到所有的顶点均被访问过 为止 在广度优先搜索中 若对顶点 V1 的访问先于顶点 V2 的访问 则对 V1 邻接顶点的访问 也先于 V2 邻接顶点的访问 就是说广度优先搜索中对邻接点的寻找具有 先进先出 的特 性 因此 为了保证访问顶点的这种先后关系 需借助一个队列暂存那些刚访问过的顶点 例如例如 下面以图 5 3 1 种 G 为例说明广度优先搜索的过程 假设从起点 v0 出 发 那么首先访问 vo 和行动两个未访问的邻接点 v1 和 v2 然后依次访问 v1 的邻接点 v3 和 v4 以及 v2 的邻接点 v5 和 v6 最后访问 v3 的未曾访问的邻接点 v7 此图中所有顶点均 已被访问过 由此完成了图的遍历 遍历过程见图 5 3 2 得到的顶点访问序列为 v0 v1 v2 v3 v4 v5 v6 v7v0 v1 v2 v3 v4 v5 v6 v7 在广度优先搜索中 若顶点 v 在顶点 u 之前访问 则 v 的邻接点也将在 u 的邻接点之 前访问 由此 可采用对列 qu 来暂存那些刚访问过并且可能还有未访问的邻接点的顶点 图 5 3 2 广度优先搜索遍历过程 算法算法 5 55 5 int visited VEX NUM 0 void Bfs Mgraph G int k int qu 20 f 0 r 0 printf 3c G vexs k visited k 1 r qu r k while r f f i qu f v0 V1 V3 V7 V4 V2 V5V6 第五章第五章 图图 for j p jarcs i j 1 visited j I r