图的遍历

在树/图上 DFS¶

前置知识：DFS 基础

遍历的复杂度是

DFS 序列是指 DFS 调用过程中访问的节点编号的序列。

我们发现，每个子树都对应 DFS 序列中的连续一段（一段区间）。

DFS 进入某个节点的时候记录一个左括号 ( ，退出某个节点的啥时候记录一个右括号 ) 。

每个节点会出现两次。相邻两个节点的深度相差 1。

对于非连通图，只能访问到起点所在的连通分量。

对于连通图，DFS 序列通常不唯一。

注：树的 DFS 序列也是不唯一的。

在 DFS 过程中，通过记录每个节点从哪个点访问而来，可以建立一个树结构，称为 DFS 树。DFS 树是原图的一个生成树。

DFS 树有很多性质，比如用来求强连通分量

前置知识：BFS 基础

类似 BFS 序列，BFS 序列是指在 BFS 过程中访问的节点编号的序列。

同样，如果原图不连通，只能访问到起点所在的连通分量。

BFS 序列通常也不唯一。

类似的我们也可以定义 BFS 树：在 BFS 过程中，通过记录每个节点从哪个点访问而来，可以建立一个树结构，即为 BFS 树。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用