• 周六. 7月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

DFS 树的理解

admin

11月 28, 2021

这是一篇对可以用图的 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)

以下是实现过程的动画:
在这里插入图片描述

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

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

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

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

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

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

原文:https://blog.csdn.net/weixin_43848437/article/details/105133155

知识共享许可协议

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。

限于本人水平,如果文章有表述不当之处,还请不吝赐教。

发表评论

您的电子邮箱地址不会被公开。