Skip to content

DFS 树

概念

DFS 树即深度优先生成树。

从一个点开始对有向图做 DFS 后可以得到一棵 DFS 树，树上的边就称为树边。

  • 从一个点指向其子树中的点的边称为前向边。
  • 从一个点指向其祖先的边称为后向边（返祖边）。
  • 若边的两端点位于它们的 LCA 的两个不同子树中，那么这条边是一条横叉边。横叉边满足起点被遍历到的时间晚于终点（否则这条边会变成树边）。

在无向图中，只有树边和返祖边（不区分前向边和后向边）

参考资料：

【R9OI】Tarjan 算法及其应用（https://www.bilibili.com/video/BV1ya411M7Tc）

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.