|
|
https://blog.csdn.net/weixin_43848437/article/details/105133155
|
|
|
|
|
|
## $DFS$ 树
|
|
|
|
|
|
### 介绍
|
|
|
这是一篇对可以用图的 $DFS$ 树来解题的教程/扩展。
|
|
|
|
|
|
在很长一段时间，我并没有真正理解传统算法是如何找到 **桥** 的。很多题解看起来没有真正解释它是如何工作的，很多只是顺带提到它但后迅速地进入实现部分。某一天有人解释了 $DFS$ 树是什么， 我才终于正确地理解了它。在此之前，我花了很长时间去理解寻找桥的算法，而且我经常要注意一些细节。现在我已经可以用打字的速度去实现它了。
|
|
|
|
|
|
但是更重要的是，我开始明白同样的算法该如何用在与桥或多或少无关的题目上。这件事，就像当你有一个黑盒时，你只可以把它当作一个黑盒去使用。但如果你有一个你十分了解的盒子，你可以把它分解，略加改动并把它用在完全不同的事情上，并且毫无疏漏。
|
|
|
|
|
|
就我而言，$DFS$ 树是我所知的解决图的结构问题最好的算法之一。此外，有时在你使用 $DFS$ 树后，一些可疑的贪心算法的正确性也会变得显而易见。
|
|
|
|
|
|
### $DFS$ 树
|
|
|
考虑一个无向连通图 $G$，对它进行深度优先遍历。它可以用一个递归函数来实现，就像这样：
|
|
|
|
|
|
```cpp{.line-numbers}
|
|
|
function visit(u):
|
|
|
mark u as visited
|
|
|
for each vertex v among the neighbours of u:
|
|
|
if v is not visited:
|
|
|
mark the edge uv
|
|
|
call visit(v)
|
|
|
```
|
|
|
|
|
|
|
|
|
以下是实现过程的动画：
|
|
|
<center><img src='https://img-blog.csdnimg.cn/2020032707535368.png#pic_center'></center>
|
|
|
|
|
|
我们看一下在第 $5$ 行被标记的边。他们构成 $G$ 的以 $1$ 为根的生成树。我们称这些边为 **树边**， 其他的所有边为 **回边**。
|
|
|
|
|
|
这就是我们图的 $DFS$ 树：
|
|
|
|
|
|
<center><img src='https://img-blog.csdnimg.cn/20200327075426626.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODQzNw==,size_16,color_FFFFFF,t_70#pic_center'></center>
|
|
|
|
|
|
**结论 $1$**：在生成树中，图的回边连接的都是一个顶点和它的子孙节点。这就是 $DFS$ 树好用的原因。
|
|
|
|
|
|
**证明**：假设有一条边 $uv$，深度优先遍历已经访问了 $u$ 但还没访问到 $v$。然后：
|
|
|
* 如果深度优先遍历沿着 $uv$ 边由 $u$ 走向 $v$，那么 $uv$ 是一条树边
|
|
|
* 如果深度优先遍历没有沿着 $uv$ 从 $u$ 访问 $v$，然而此时遍历到第四步发现 $v$ 已经被访问过了。说明 $v$ 是在遍历 $u$ 的一个邻居节点时对它进行了访问，这意味着 $v$ 是 $u$ 在 $DFS$ 树中的一个子孙节点。
|
|
|
|
|
|
例如在上面的图中，节点 $4$ 和节点 $8$不可能由一条回边相连因为它们各自都不是另一个的祖先节点，如果由一条边连接 $4$ 和 $8$，遍历会从 $4$ 走向 $8$ 而不是返回 $2$。
|
|
|
|
|
|
这是 $DFS$ 树最显而易见的结论。$DFS$ 树如此有用是因为它简化了图的结构。与其去考虑图中所有种类的边，我们此时只需要考虑一棵树和一些额外的祖先-子孙连边。这样的结构十分适于思考和尝试算法。
|
|
|
|
|
|
### 找桥（或割点）
|
|
|
$DFS$ 树和结论 $1$ 是 $Tarjan$ **找桥算法** 的核心。传统的找桥教程只顺带提到了 $DFS$ 树并从定义奇怪的 $dfn[u]$ 数组和 $low[u]$ 数组开始。把这些全部忘掉。这些是实现的细节，在我看来，它们甚至不是实现找桥算法最直观的方法。在找桥算法中，$dfn[u]$ 只是一个用来确认某一顶点是否是 $DFS$ 树中另一顶点的祖先的令人迷惑的方法。同时，也很难清楚地解释 $low[u]$ 代表着什么。
|
|
|
|
|
|
以下就是在一个无向连通图中找桥的方法。考虑图 $G$ 的 $DFS$ 数。
|
|
|
|
|
|
**结论 $2$**：当且仅当树边 $uv$ 不存在连接其祖先和子孙节点的回边时，它是桥。也就是说，树边 $uv$ 是桥当且仅当此时没有回边跨越它。
|
|
|
|
|
|
**证明**：移出边 $uv$ 将生成树分成了两个互补连接的部分：$uv$ 的子树和剩余的生成树。如果两部分间有回边相连，那么图依旧连通，否则 $uv$ 就是个桥。回边连接这两部分的唯一情况就是它连接了 $uv$ 的祖先和子孙
|
|
|
|
|
|
例如，在上图的 $DFS$ 树中，连接 $6$ 和 $2$ 的不是桥， 因为即使我们移除了它，连接 $3$ 和 $8$ 的回边依旧使图连通。看另一个例子，连接 $2$ 和 $4$ 的边是桥，因为并没有跨越它的回边来使图在移除 $2$-$4$ 边后继续连通。
|
|
|
|
|
|
**结论 $3$**：回边一定不是桥。
|
|
|
|
|
|
这引出了经典的找桥算法。考虑一个图 $G$:
|
|
|
1.建立这张图的 $DFS$ 树。
|
|
|
2.对每一条树边 $uv$，寻找是否有一条回边跨越$uv$，如果没有，它就是桥。
|
|
|
|
|
|
因为 $DFS$ 树的简单结构，第二步十分容易实现。例如，你可以用传统的 $low[u]$ 方法；或者，可以用 **前缀和** 来记录，这就是我推崇的。
|
|
|
|
|
|
我们用$dp[x]$表示: 多少条回边穿过$x - fa[x]$。
|
|
|
|
|
|
|
|
|
自下往上转移$dp$。
|
|
|
$$\large dp[x]=dp[y_i] + (x-> 其祖先节点 的回边的个数) - ( x的后代节点连接x的回边个数 )$$
|
|
|
|
|
|
最后只要$dp[x]$等于$0$，那么$x$与其父亲节点连接的边，一定是桥边。 |
