一、DFS Forest
从这张经典图说起：
在给定的有向图 \(G = (V, E)\) 内，遍历这张图，其中边分为 \(4\) 种：
-
树边（tree edge）：黑色的边，每一次从 \(u\) 访问到一个未访问的节点 \(v\)，则称 \((u, v)\) 为 树边。
-
返祖边（back edge）：红色的边，每一次从 \(u\) 回溯到一个 \(u\) 的已经访问的祖先 \(v\)，则称 \((u, v)\) 为 返祖边。
-
横叉边（cross edge）：蓝色的边，每一次 \(u\) 访问到一个已经访问过的节点 \(v\)，但 \(v\) 不是 \(u\) 的祖先，则称 \((u, v)\) 为 横叉边。
-
前向边（forward edge）：绿色的边，每一次 \(u\) 访问到一个还没有访问过的节点 \(v\)，并且 \(u\) 是 \(v\) 的祖先，则称 \((u, v)\) 为 前向边。
其中第一个被访问的节点 \(rt\) 被称为 DFS Forest 的 根。