DFS 树的理解

这是一篇对可以用图的 DFS 树来解的题的教程/扩展。

在很长一段时间,我并没有真正理解传统算法是如何找到桥的。很多题解看起来没有真正解释它是如何工作的,很多只是顺带提到它但后迅速地进入实现部分。某一天有人解释了 DFS 树是什么, 我才终于正确地理解了它。在此之前,我花了很长时间去理解寻找桥的算法,而且我经常要注意一些细节。现在我已经可以用打字的速度去实现它了。

但是更重要的是,我开始明白同样的算法该如何用在与桥或多或少无关的题目上。这件事,就像当你有一个黑盒时,你只可以把它当作一个黑盒去使用。但如果你有一个你十分了解的盒子,你可以把它分解,略加改动并把啊用在完全不同的事情上,并且毫无疏漏。

就我而言,DFS 树是我所知的解决图的结构问题最好的算法之一。此外,有时在你使用 DFS 树后,一些可疑的贪心算法的正确性也会变得显而易见。


考虑一个无向连通图 G,对它进行深度优先遍历。它可以用一个递归函数来实现,就像这样:

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)

以下是实现过程的动画:
DFS 树的理解

我们看一下在第 \(5\) 行被标记的边。他们构成 G 的以 \(1\) 为根的生成树。我们称这些边为树边, 其他的所有边为回边

这就是我们图的 DFS 树:
DFS 树的理解
结论:在生成树种,图的回边连接的都是一个顶点和它的子孙节点。这就是 DFS 树好用的原因

证明:假设有一条边 \(u\rightarrow v\),深度优先遍历已经访问了 \(u\) 但还没访问到 \(v\)。然后

  • 如果深度优先遍历沿着 \(u\rightarrow v\) 边由 \(u\) 走向 \(v\),那么 \(u\rightarrow v\) 是一条树边。
  • 如果深度优先遍历没有沿着 \(u\rightarrow v\)\(u\) 访问 \(v\),然而此时遍历到第四步发现 \(v\) 已经被访问过了。说明 \(v\) 是在遍历 \(u\) 的一个邻居节点时对它进行了访问,这意味着 \(v\)\(u\) 在 DFS 树中的一个子孙节点。

例如在上面的图中,节点 \(4\) 和节点 \(8\) 不可能由一条回边相连因为它们各自都不是另一个的祖先节点,如果由一条边连接 \(4\)\(8\),遍历会从 \(4\) 走向 \(8\) 而不是返回 \(2\)

这是 DFS 树最显而易见的结论。DFS 树如此有用因为它简化了图的结构。与其去考虑图中所有种类的边, 我们此时只需要考虑一棵树和一些额外的祖先-子孙连边。这样的结构十分适于思考和尝试算法。

DFS 树的理解

原文:https://www.cnblogs.com/Sam2007/p/15169628.html

上一篇:form表单提交失败


下一篇:10、二进制安装K8s之部署CoreDNS 和Dashboard