算法检查图的2∀-connectness属性

Question

即使删除了任何单个边缘，也将其保持连接，如果将图形连接。令G =（V，e）为连接的无向图。尽可能快地开发算法，以检查G的2∀连接性。

我知道基本想法是构建DFS搜索树，然后检查每个边缘与DFS的圆圈。任何帮助，将不胜感激。

我期望看到的是详细的算法描述（尤其是有时所需变量的初始化），可以省略复杂性分析。

Answer 1

一个简单的算法是：

令$ g =（v，e）$为您要检查2个连接性的图。

对于每个边缘$ e =（x，y）在e $中，请查看是否有从$ x $到$ y $ in $ in $（v，e setminus {e }）$的路径。如果对于某些$ e $，则没有这样的路径，则该图未连接2边缘。如果每个$ e $都有这样的途径，则$ g $是2边连接的。

您还应该注意，此算法不是最快的，但非常容易理解。可以使用例如BFS或Dijkstra的算法来完成路径求线零件。

本文 还显示了一种用于测试2边连接性的简单算法，该算法以线性时间运行。