算法图算法

遍历序的概念与性质

字数统计: 999字   |   阅读时长: 3分
,

摘要: 图的几种遍历序及其应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

对于一棵树，我们知道从根节点出发有 DFS 和 BFS 两类方法可以把树种的节点遍历一遍。如果是二叉树的话，基于 DFS 的遍历方法就是前序、中序、后序遍历；基于 BFS 的遍历方法就是层序遍历。对于一般的树，DFS 和 BFS 这两种遍历过程与图的遍历是一样的。

考虑图的遍历，DFS 的过程中，各个节点有一个进栈出栈的过程，按照节点进栈出栈的顺序我们可以在遍历过程中得到节点的序列，称为节点的 DFS 序；类似地，BFS 的过程中，各个节点有一个进队出队的过程，按照进队出队的顺序我们也可以在遍历过程中得到相关的序列，称为 BFS 序。

下面我们梳理一下常见的遍历序的概念、性质和应用。

$1 DFS 遍历序

(1) DFS 序

定义

图的 DFS 遍历过程中节点进栈和出栈的顺序称为 DFS 序。如果是树的话，节点进栈和出栈的顺序还可以理解为节点进入该节点对应的子树和离开子树的顺序。

性质

  • 满足每个节点都会在dfs序上出现恰好两次。
  • 任意子树的 dfs 序都是连续的。

记节点 x 在 dfs 序中的两次出现的位置为 L[x], R[x]，则区间 [L[x], R[x]] 就是以 x 为根的子树的 dfs 序。于是一些树相关的问题中，可以通过 dfs 序把子树统计转化为序列上的区间统计。

(2) DFN 序

定义

图的 DFS 遍历过程中按照节点第一次被访问的顺序排列 称为 DFN 序，dfn[i] := i 节点第一次被访问的顺序排名 也称为节点 i 的时间戳。

性质

  • dfn 序可以认为是 dfs 序的一半、是 dfs 序的子序列。
  • 任取一个子树，根节点的 dfn 序是最小的，并且同一棵子树中的 dfn 序连续，见后面的例子。

(3) 欧拉序

定义

DFS 过程中经过节点的顺序。对于节点 x，来自其上游的递归而访问到 x，以及来自其下游的回溯而访问到 x，均记录一次欧拉序。

性质

  • 若节点的度(入度+出度)为 degree[i], 则节点 i 在欧拉序中出现 degree[i] 次，根节点额外一次。

(4) 例子

我们以下图这棵树为例子，给出其 DFS 序、DFN 序、欧拉序，对比前面的定义来看，便于理解。

1
2
3
DFN序：1,2,3,4,5,6,7,8,9
DFS序：1,2,3,4,5,3,6,7,6,2,8,9,8,1
欧拉序：1,2,3,4,3,5,3,2,6,7,6,2,1,8,9,8,1

$2 BFS 遍历序

对于图来说，讲遍历序的时候一般指的是 DFS 遍历序，不太讲 BFS 遍历序，因为 BFS 的过程与拓扑排序是一样的，当我们需要 BFS 序的时候，一般会直接讲拓扑排序。

$3 经典问题

遍历序的应用主要在于将树或图结构上的问题转化为序列上的问题，下面是两个例子：

由 DFS 序和 BFS 序重建树也是一个经典问题，参考文章 给定树的遍历序-重建一棵可能的树。

$4 后续

有一些图上的高端算法中用到了遍历序，例如下面这几个，比较难，有时间的可以看看。

Share