图中的每个桥都是DFS搜索树中的边缘吗？

Question

Skiena的算法书中的一个问题:

假设G是连通的无向图.删除断开图形的边e称为桥.每个桥必须是G的深度优先搜索树中的边缘吗？

到目前为止我的解决方案(需要建议):

我认为桥是一个边缘,其末端顶点是一个切割节点,因为切割节点删除会断开图形,因此删除该边缘也会断开图形.DFS搜索树中的边缘是树边缘和后边缘,并且只有树边缘可以是切边(或桥),因为后边缘移除不会断开图形.

Answer 1

基本上，是的。不过我有一些评论：

我认为桥是一条边，其末端顶点是切割节点，因为切割节点删除会断开图的连接，因此删除该边也会断开图的连接。

这并不准确。特别是，如果你将其读作（桥 => 边有一个切割节点），那就是真的。但表述为“桥是一条边，其末端顶点......”，它暗示了相反的含义，这是不正确的。总而言之，这句话与论证的其余部分基本上无关，我只是省略它。

...只有树边可以被切割边（或桥），因为后边删除不会断开图形。

是的，就是这样。另外，您必须注意，DFS 会探索连通图的所有顶点（或标记所有边）。