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

Question

Skiena 算法书中的一道题:

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

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

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

Answer 1

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

I think that the bridge is an edge whose end vertex is a cut node, because cut node removal disconnects the graph so removing that edge will also disconnect the graph.

这不准确。特别是，如果您将其解读为(桥 => 边缘有一个切割节点)，那是正确的。但表述为“桥是一条边，其端点......”，它暗示了相反的含义，这是不正确的。总而言之，这句话与其余的论点基本无关，我将忽略它。

... only tree edges can be cut edges ( or bridges ) because back edge removal doesn't disconnect the graph.

是的，就是这样。此外，您还必须注意 DFS 探索连通图的所有顶点(或标记所有边)。