algorithm - 是否有一条边可以在不断开图形的情况下删除？

Question

在我开始之前，是的，这是一个家庭作业。如果我在过去的 14 小时内没有尽我所能解决这个问题但一无所获，我就不会在这里发帖。

问题如下:我想检查是否可以在 O(V) 时间内从连接的无向图中删除一条边而不断开它，而不仅仅是线性的。

到目前为止我达到了什么:

可以在不断开图形的情况下删除循环边，所以我只是检查图形是否有循环。我有两种方法可以使用，一种是DFS，然后检查我是否有后缘；另一种是通过计算 Vs 和 Es 并检查是否 |E| = |V| - 1，如果这是真的那么图就是一棵树并且没有节点我们可以在不断开连接的情况下删除。

前面的两种方法都解决了问题，但是都需要O(|E|+|V|)，书上说还有一种更快的方法(那可能是一种贪婪的方法)。

我能得到任何提示吗？

编辑:更具体地说，这是我的问题；给定一个连通图 G=(V,E)，我可以删除 E 中的一些边 e 并使生成的图仍然连通吗？

Answer 1

图形的任何递归遍历，在节点被访问时标记节点并在遇到已标记的节点时短路返回 true 都可以解决问题。如果没有可以删除的边，这需要 O(|V|) 来遍历整个图，如果它提前停止返回 true，则需要更少的时间。

编辑

是的，整个图的递归遍历需要 O(|V|+|E|) 时间，但是如果没有循环我们只遍历整个图——在这种情况下 |E| = |V|-1 并且只需要 O(|V|) 时间。如果有环，我们最多遍历|V|就找到了边(并访问最多 |V|+1 个节点)，这同样需要 O(|V|) 时间。

此外，很明显，当从一个节点(第一个节点除外)遍历时，您不会考虑您用来到达该节点的边，因为这会使您立即看到一个已经访问过的节点。