Skiena的算法书中的一个问题：
假设G是连通的无向图 . 删除断开图形的边e称为桥 . 每个桥必须是G的深度优先搜索树中的边缘吗？
到目前为止我的解决方案（需要建议）：
我认为桥是一个边缘，其末端顶点是一个切割节点，因为切割节点删除会断开图形，因此删除该边缘也会断开图形 . DFS搜索树中的边缘是树边缘和后边缘，并且只有树边缘可以是切边（或桥），因为后边缘移除不会断开图形 .
基本上，是的 . 我有一些评论：
我认为桥是一个边缘，其末端顶点是一个切割节点，因为切割节点删除会断开图形，因此删除该边缘也会断开图形 .
这不准确 . 特别是，如果你把它读成（bridge => edge有一个cut节点），那就是这样 . 但是，作为“一座桥是一个终点顶点的边缘......”，它暗示了相反的含义，这是不正确的 . 总而言之，这句话在很大程度上与论证的其余部分无关，我只是省略了它 .
...只有树边可以是切边（或桥），因为后边缘移除不会断开图形 .
是的，就是这样 . 另外，您必须注意DFS探索连接图的所有顶点（或标记所有边） .
1 回答
基本上，是的 . 我有一些评论：
这不准确 . 特别是，如果你把它读成（bridge => edge有一个cut节点），那就是这样 . 但是，作为“一座桥是一个终点顶点的边缘......”，它暗示了相反的含义，这是不正确的 . 总而言之，这句话在很大程度上与论证的其余部分无关，我只是省略了它 .
是的，就是这样 . 另外，您必须注意DFS探索连接图的所有顶点（或标记所有边） .