4 图树周游

  关于图树周游，其实无非是深搜、广搜、按层遍历（树）等一些基本方法。课程课件中涉及到了一个求连通图$G$关节点的方法：

关于关节点

  关节点，就是割点。对于连通图 $G$，其连通分支 $p(G)=1$。割点指的就是满足 $p(G-{v}) > 1$ 的这些点 $v$。

  对图 $G$ 进行深度优先遍历，能够得到一颗深度优先生成树 $T$，$T$ 中包含了 $G$ 中所有的顶点和部分边。在图 $G$ 中，但是不在生成树 $T$ 中的边称为逆边。

关于为什么不用广度优先遍历

  使用深度优先遍历的好处是，图$G$中不存在这样一条边 $(u,v)$，使得在 $T$ 中 $u$ 和 $v$ 没有祖孙关系（互相不是对方的祖先），也可以说是图 $G$ 中不含相对 $T$ 的交叉边。
  如果是使用广度优先生成树 $T$，$G$ 就可能存在相对 $T$ 的交叉边。

  图 $G$ 中每一个结点 $v$ 都有深度优先数 $\mathrm{DFN}(v)$，表示结点 $v$ 是深度优先遍历图 $G$ 时第几个被遍历到的结点。每个节点 $v$ 还有一个最低深度优先数$L(v)$，它的定义是： $$L(v)=\min \lbrace \mathrm{DFN}(v),\min\lbrace L(w)|w是v的儿子\rbrace, \min\lbrace \mathrm{DFN}(w)|(v,w)是一条逆边 \rbrace \rbrace \tag{4.1}$$

  直观地，$L(v)$ 就是 $v$ 通过一条子孙路径且至多后随一条逆边所可能到达的最低深度优先数。判定割点的规则是，在深度优先生成树 $T$ 中，根节点如果至少有两个儿子就是割点，非根节点 $v$ 如果存在一个儿子 $w$ 满足 $L(w)\geq \mathrm{DFN}(v)$ 就是割点。

  一开始我觉得这种方法很高级，后来的学习过程中知道了这种方法原来是强大的 Tarjan 算法的一个子方法，关于 Tarjan 算法的学习正在进行中。

$\boxed{\mathbb{The\ End.}}$