在删除边之后如何确定图是否仍然是强连通的

Question

强连通有向图是一种有向图，其中对于每两个顶点和，存在从到的有向路径和从到的直接路径。设=（，）是一个强连通有向图，而=（，）∈是图中的一条边。设计一个有效的算法来判断′=（，∖{}），即没有边的图是否是强连通的。解释其正确性并分析其运行时间。

我的做法是运行BFS并计算标签总和，首先在原始图中从开始，然后在没有边的G'中再次运行（同样从开始）。如果第二个总和（在G'中）小于原始总和（在G中），则该图不是强连通的。

附言：这是我考试中的一个问题，我只得了3/13分，我想知道是否应该上诉。

- Nicole

---

什么是标签？它是边的权重吗？如果是这样，那么毫无疑问，你的算法将会给出错误的结果。 - mukesh210

标签是距离根的距离。 - Nicole

你提出的算法明显是错误的。（为什么删除一条边会减少到达一个节点的成本呢？） - Sneftel

它应该不会出现这种情况，但如果确实发生了，那么只有在图不再强连通时才会发生，例如如果现在无法到达该节点，则所有标签的总和将比原始值小->未连接。 - Nicole

如果没有到达节点的方法，那么它的成本将是无限的，而不是更少。在任何情况下，如果您所要做的只是在边被移除后确定图是否未连接，为什么要在移除前对BFS进行麻烦？您已经知道其中一个将被连通。 - Sneftel

Answer 1

正如Sneftel所指出的，距离标签只能增加。如果u不再有通往v的路径，则我猜测v的标签将为无限大，因此标签之和将从有限变为无限。然而，在图形保持强连通性的情况下，总和仍然可以增加，例如：

u<----->v
 \     /|
  \|  /
    w

v的标签值由于通过w的间接路径而增加从1到2。

- David Eisenstat

---

那么，您建议在这样的图中使用哪种算法来检查强连通性？ - Eric

@Thomash的回答很好。 - David Eisenstat

Answer 2

由于图G是强连通的，当且仅当存在一条从u到v的路径（这条路径将替换边e），G'也是强连通的。

您可以使用任何路径查找算法来解决此问题。

- Thomash

---

是的，我知道，但我想知道这是否也有效。(: - Nicole