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

Question

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

假设 G 是一个连通的无向图。一条边 e 的删除使图断开连接，称为桥。每个桥 e 都必须是 G 的深度优先搜索树中的一条边吗？

到目前为止我的解决方案（需要建议）：

我认为桥是一条边，其末端顶点是一个切割节点，因为切割节点的删除断开了图形，因此删除该边也会断开图形。DFS 搜索树中的边是树边和后边，只有树边可以被切割边（或桥），因为后边去除不会断开图。

Answer 1

基本上，是的。不过我有几点意见：

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

这并不准确。特别是，如果您将其解读为（bridge => edge 有一个切割节点），那是真的。但被表述为“桥是其末端顶点......的边”，它暗示了相反的含义，这是不正确的。总而言之，这句话在很大程度上与其余的论点无关，我将省略它。

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

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