图的遍历(深度优先遍历和广度优先遍历-)

数据结构与算法 第二十讲 北方民族大学计算机科学与工程学院王伦津研究员 图的遍历 20 图的遍历深度优先遍历和广度优先遍历 掌握图的深度优先和广度优先遍历的性质和方法 以及基于邻接矩阵和邻接表存储结构的递归和非递归的算法实现 目录 20 1概述20 2深度优先遍历20 3深度优先遍历的性质20 4广度优先遍历20 5广度优先遍历的性质 20 图的遍历 从这节起 我们介绍图的一些重要操作的实现 包括遍历 拓扑排序 关键路径等 另有一些重要操作 如最短路径问题 最小生成树问题 由于主要难点在于算法 所以我们安排在后面的算法设计章节中介绍 图的遍历与树的遍历一样具有十分重要的作用 图的许多其他操作 算法 都与遍历相关 20 1概述 图的遍历的含意是 从图中某结点出发 按某既定方式访问图中各个可访问到的结点 使每个可访问到的结点恰被访问一次 图的遍历方式有两种 深度优先与广度优先方式 分别对应于树的先根遍历与层序遍历 树中不存在回路 但图中可能有回路 因此 当沿回路进行扫描时 一个结点可能被扫描到多次 可能导致死循环 为了避免这种情形 在遍历中 应为每个结点设立一个访问标志 每扫描到一个结点 要检查它的访问标志 若标志为 未访问 则按正常方式对其进行处理 如访问或转到它的邻接点等 否则放过它 扫描下一个结点 访问标志的设置有两种方法 在描述图结的记录中增设一个访问标志位 这种方法的优点是 访问 访问标志 的方法与访问结点的方法一致 如果访问标志需要与图结构同生命期 则这种方法比较合适 但是 若访问标志要重复使用 就必须先重新初始化访问标志 如果图结点的存储不利于顺序访问 这往往也是个遍历问题 另设一个 访问数组 令它的每个元素对应于一个图结点访问标志 这种方法的访问标志很容易多次初始化 从图中某一结点出发 一趟只能遍历到它所在的极大连通分量中的结点 要想遍历到图中各结点 需进行多趟遍历 每趟遍历一个极大连通分量 该过程可描述为 for 图中每个结点v if v尚未被访问过 从v出发遍历该图 下面只考虑从一点出发遍历 因此有可能会出现遍历不到的点 即那些初始点无路径可达的点 是遍历不到的 20 2深度优先遍历 一 遍历规则从图中某结点v0出发 深度优先遍历 DFS DepthFirstSearch 图的规则为 访问v0 对v0的各个出点v01 v02 v0m 每次从它们中按一定方式 也可任选 选取一个未被访问过的结点 从该结点出发按深度优先遍历方式遍历 显然 因为我们没有规定对出点的遍历次序 所以 图的深度优先遍历结果一般不唯一 例如 对图20 1给出的有向图与无向图 一些遍历结果 结点访问次序 为 左图 从1出发 1 2 4 5 或1 5 2 4从2出发 2 1 5 4 或2 4 1 5右图 从a出发 a b c d 或a b d c 图20 1一个有向图 左 和无向图 1 一般算法下面考虑深度优先遍历的递归实现的一般方法 存储结构无关 图的深度优先遍历与二叉树的前序遍历相似 不同之处有 二叉树每个结点至多有两个可达邻接点 左右儿子 而图的可达邻接点数目不定 对二叉树 沿可达邻接点搜索时不会发生回绕 但对图 若不加特别控制 就有可能回绕 下面是图的深度优先遍历递归算法的一般性描述 如果要另设一个数组作为访问标志 则该数组要在递归过程 函数 之外初始化为 未访问 二 递归实现方法 longDFS 图g 结点v0 图深度优先遍历递归算法 从结点v0出发 深度优先遍历图g 返回访问到的结点总数intnNodes 寄存访问到的结点数目访问v0 为v0置已访问标志 nNodes 1 求出v0的第1个可达邻接点v while v存在 if v未被访问过 nNodes nNodes DFS g v 求出v0的下个可达邻接点v returnnNodes 12345101001210010300001410000500000 所示图的邻接矩阵g 1121304151 图20 1有向图 访问标识数组visited 输出数组resu 例如从1点深度优先遍历 先把1设置访问标志 并置入输出数组resu 然后从邻接矩阵的第一行 扫描各列 找到最近的邻接点2 将其设置访问标志 并进入输出数组 接着从邻接矩阵的2行扫描 找到第一个构成边的点是1 检查访问标识数组 发现1已经访问过 跳过 找第二个构成边的点4 设置访问标识 进入输出数组 再从邻接矩阵的第4行扫描 寻找构成边的点 除1外在无其他点 返回2行 继续寻找 也无新点 返回1 找到5 将5置访问标志 进入输出数组 1行再无其他新点 遍历结束 返回遍历元素个数为4 2 邻接矩阵实现这里我们为了突出主题 简化问题 假定图是用一般的邻接矩阵存储 邻接矩阵用简单的二维数组表示 静态 用0和1分别表示无边和有边 图结点用自然数编号 longDFS1 intg CNST NumNodes longn longv0 char visited long resu long top 深度优先遍历图 递归 图g为邻接矩阵 结点编号为0 n 返回实际遍历到的结点数目 visited是访问标志数组 调用本函数前 应为其分配空间并初始化为全0 未访问 resu为一维数组 用于存放所遍历到的结点的编号 调用本函数前 应为其分配空间 longnNodes i nNodes 1 resu top v0 将访问到的结点依次存于resu visited v0 1 为v0置已访问标志for i 0 i是边if visited i 若结点i未被访问过nNodes nNodes DFS1 g n i visited resu 从i起深度优先遍历图 returnnNodes A如果不想让visited或top做为函数参数 也可以在函数中将其定义为static型量 但是 这样的程序是不可再入的 即函数再次被调用时 static型的量也不重新初始化 造成错误 上面函数中的参数visited和top实质上是中间变量 只是为了避免在递归调用时重新初始化而放在参数表中 造成使用的不方便 为此 做个包装程序 longDFS1 intg CNST NumNodes longn longv0 long resu char visited longtop 0 visited newchar n for longi 0 i n i visited i 0 longnum DFS1 g n v0 visited resu top deletevisited returnnum 对应的邻接表 图20 2有向图 1121304151 访问标识数组visited 输出数组resu 邻接表边 P Nodes 终点2作为下次的始点 由于1点已访问过 跳过 找到4 记标识 送输出 4有作为新的始点重复上述过程 3 邻接表深度优先遍历的实现templatelongDFS2 TGraphNodeAL nodes longn longv0 char visited long resu long resu top v0 将访问到的结点依次存于resu visited v0 1 置v0为 已访问 标志p nodes v0 firstOutEdge 求出v0的第一个出点pwhile p NULL if visited p endNo 若p未访问 则从p出发深度优先遍历nNodes nNodes DFS2 nodes n p endNo visited resu top p p next 令p指向v0的下个出点 returnnNodes 与邻接矩阵的情况类似 也可以对该程序 包装 以隐蔽visited和top 三 非递归实现方法1 一般方法下面考虑深度优先遍历的非递归实现的一般方法 存储结构无关 图的深度优先遍历的非递归实现 仍然与二叉树的前序遍历非递归实现相似 不同之处有 二叉树每个结点至多有两个可达邻接点 左右儿子 而图的可达邻接点数目不定 因此 当结点重新出现在栈顶时 不能一定出栈 而是要根据它的各出点是否都已被访问过来决定 是则出栈 对二叉树 沿可达邻接点搜索时不会发生回绕 但对图 若不加特别控制 就有可能回绕 longDFS NR 图g 结点v0 图深度优先遍历非递归算法 从结点v0出发 深度优先遍历图g 返回访问到的结点总数intnNodes 寄存访问到的结点数目访问v0 为v0置已访问标志 v0进栈S nNodes 1 求出v0的第1个可达邻接点v 深度优先遍历非递归算法的一般性描述 while 栈S不空 v 栈S顶部元素 求v的下个未访问过的出点i 访问i 为i置已访问标志 i进栈S nNodes if v已无未被访问过的出点 出栈 returnnNodes 上面的伪码描述与具体的数据结构无关 下面的程序分别给出了针对邻接矩阵与邻接表的算法模型 2 邻接矩阵实现longDFS1 NR intg CNST NumNodes longn longv0 long resu 深度优先遍历图 非递归 图g为邻接矩阵 结点编号为0 n 返回实际遍历到的结点数目 resu为一维数组 用于存放所遍历到的结点的编号 调用本函数前 应为其分配空间longnNodes i v longtop char visited long s visited newchar n for i 0 i n i visited i 0 s newlong n 1 top 0 nNodes 0 resu nNodes v0 将访问到的结点依次存于resu visited v0 1 为v0置已访问标志 top s top v0 while top 0 v s top for i 0 i是边if visited i 若结点i未被访问过 resu nNodes i 将访问到的结点依次存于resu visited i 1 为i置已访问标志top s top i i进栈break if i n top 若v已无未访问到的出点 则将其退栈 whilereturnnNodes 下面给出初始结点为1时 得进出栈的过程 1进栈 1出栈 2进栈 5进栈 5出栈 2出栈 1进栈 4进栈 4出栈 1出栈 遍历结果为1 5 2 4 20 3深度优先遍历的性质 深度优先遍历有许多重要而有趣的性质 利用它们可以获得有关图的更多的信息 我们这里作一简单介绍 一 深度优先生成树与单源路径在深度优先遍历中 如果将每次 前进 纵深 路过的 将被访问的 结点和边都记录下来 就得到一个子图 该子图为以出发点为根的树 称为深度优先生成树 如果从图的多个结点出发才能遍历到所有结点 则图的深度优先遍历树有多棵 从而构成森林 称为深度优先生成森林 显然 由图得到深度优先生成树 相当于对图 层次 化 使图中每个结点都有一个层次号 此外 从v0出发深度优先遍历树 同时也产生v0到各结点的路径 例如 图20 2 a 的出发点为1的深度优先生成树如图20 2 b a 有向图 b 深度优先生成树 图20 2 深度优先遍历性质说明 二 时间戳在遍历中 对每个结点v 定义从第一次 发现 即第一次遇到 开始遍历 它的时刻为它的发现时间 记为S v 定义遍历完v的时刻为v的完成时间 记为E v 这两种时间都称v的时间戳 一般情况下 用遍历中 路过 包括回退 的结点数表示时间 图20 2 b 中 结点旁边的数字 a b 表示对应结点的开始时间和完成时间分别为a和b 针对 a 的从1出发的深度优先遍历 时间戳的差E v S v 可用在推算深度优先遍历的进行情况 做为遍历的启发信息 指导遍历算法尽快发现目标 三 遍历括号某结点v的深度优先遍历括号定义为 vX1X2 Xmv 这里 Xi为v的出点中 可从v出发直接访问到的各结点的遍历括号 i 1 m m 0 例如 图20 2 b 的结点1的遍历括号为 按时间戳有 1 2 44 2 5 33 66 5 1 遍历括号实质上是广义表 它完全描述了深度优先遍历的过程及深度优先遍历生成树的结构 可做为深度优先遍历生成树的串行化表达式 20 4广度优先遍历 一 图的广度优先分层图的广度优先分层与图的广度优先遍历密切相关 另外 在许多其他问题中 也涉及到图的广度优先分层 图的广度优先分层就是要识别出图中每个结点属于的层次 即给每个结点编一个层次号 但是 图本身是非层次结构 所以 一般也无层次而言 然而 我们若只从某些关系 角度考虑问题 则就可对图分层了 分层时 应先确定一个或几个参考点 将它们的层号指定为起始层 第1层 下面给出以结点v0为参考点的图的广度优先分层的定义 非过程化 这里用Level v 表示结点v的广度优先分层的层号 n令Level v0 1n对任意的v v0 若存在v0到v的通路 则令Level v 1 MINu Level u 是图的边 否则令Level v 可能在不同的路径中会有多个边到达 取其最短者 即层号低的那个 例20 3对图20 1 广度优先分层情况为 右图 从1出发分层 层号为1的结点 1层号为2的结点 2 5层号为3的结点 4层号为 的结点 3右图 从2出发分层 层号为1的结点 2层号为2的结点 1 4层号为3的结点 5层号为 的结点 3右图 从a出发分层 层号为1的结点 a层号为2的结点 b d层号为3的结点 c 二 图的广度优先遍历方法从结点v0出发 广度优先遍历 Breadth WidthFirstSearch 图的方法是 按从v0出发 对图的广度优先分层的层次号的大小次序访问结点 即先访问第一层上结点 然后访问第二层上结点 等等 同层上结点可按邻接点次序或任意 例如 图20 1中的两个图的一些广度优先遍历次序如下 左图 从1出发广度优先遍历结果 1 2 5 4左图 从2出发广度优先遍历 2 1 4 5右图 从a出发广度优先遍历 a b d c从另一角度看 从v出发广度优先遍历 是先访问v 然后 对任意结点u 在访问了u之后 对u的各可达点的访问 按距u的距离 边数 大小次序进行 显然 若图的结点是无序的 即邻接点无次序关系 则广度优先遍历次序也不是唯一的 但层次关系不颠倒 三 算法实现1 一般方法对于深度优先遍历 用递归方法描述是件自然的事 但广度优先遍历不然 使用递归描述反而会使问题复杂化 所以我们这里只讲非递归描述法广度优先遍历是一种分层处理 对这种分层处理 使用队列是自然的 我们设立一个队列 任何时刻 均保证它满足下列条件 队中元素是已访问过的结点的可达邻接点 队中元素是尚未被访问过的 队中元素按它们所处的层次的先后排列 这样 我们就可不断地每次从队中取出一个元素并访问之 然后再将该元素的尚未被访问过的邻接点进队 直至队空 图的广度优先算法伪码描述如下 longBFS 图g 结点v0 在图g中从v0出发按广度优先遍历方式遍历g 返回遍历到的结点数目longnNodes 0 初始化队Q if v0存在 v0入Q 置v0为已访问标志 while Q不空 队Q头元素出队并送v 访问v nNodes 对已访问元素计数 求出v的第一个可达邻接点w while w存在 if w尚未被访问过 w入Q 置w为已访问标志 求v的下个可达邻接点w returnnNodes A请思考 1 如果上面的程序中不使用队列 而所用栈 那么是否正确 为什么 2 为什么结点一入队就置已访问标志 上面的算法描述是一般性的 并未涉及到具体的存贮结构 2 邻接矩阵实现设图用邻接矩阵表示 则它的广度优先遍历算法如下 longBFS1 NR intg CNST NumNodes longn longv0 long nos 广度优先遍历 邻接矩阵 从v0出发遍历用邻接矩阵表示的图g 共n个结点 将访问到的结点的编号存入nos 其必须在外面分配n个long型空间 返回遍历到的结点数目longnNodes 0 longv w i char visited TQueueSquQ n 1 visited newchar n for i 0 i 0 v0 n Q QPush v0 visited v0 1 while Q IsEmpty v Q QPop nos nNodes v 访问结点vnNodes for w 0 w n w 找v的各未访问的出点if g v w 0 if visited w Q QPush w v的各未访问的出点进栈visited w 1 whiledelete visited returnnNodes 12345101001210010300001410000500000 所示图的邻接矩阵g 1121304151 图20 1有向图 访问标识数组visited 输出数组nos 3 邻接表实现针对邻接表的算法为 templatelongBFS2 NR TGraphNodeAL nodes longn longv0 long nos 广度优先遍历 邻接表 从v0出发遍历用邻接表表示的图g 共n个结点 将访问到的结点的编号存入nos 其必须在外面分配n个long型空间 返回遍历到的结点数目longnNodes 0 TGraphEdge p char visited TQue