我正在寻找一种快速算法来确定给定的有向图是否包含桥......
不关心这座桥的位置..只关心图表是否包含它。
最佳答案
如果图是有向的，类似于无向图的桥，我们称边为强桥，如果它的移除增加了图的强连通分量的数量。 为了测试有向图是否具有强桥，您需要运行论文中详述的算法: Giuseppe F. Italiano、Luigi Laura、Federico Santaroni:在线性时间内找到牢固的桥梁和牢固的接合点。理论。电脑。科学。 447: 74-84 (2012) http://dx.doi.org/10.1016/j.tcs.2011.11.011
关于algorithm - 检查有向图的桥梁，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7767838/