强连通图
我有一个强连通图。我想移除一个边并检查是否仍然保持强连接。因为我将N=图中节点的总数取为10，并且我感兴趣的大多数图都有25条以上的边，所以很难检查一次使用一条，去掉边。
如何解决这个问题？多谢了。
共有1个答案
如果你移除的边是(u->v)，如果你能找到一条从u到v的路径，图将保持连通。你可以使用任何路径查找算法来检查这一点。
另一种选择是每次从头运行连通性检查算法；你怎么做其实并不重要，因为图很小。
对于一个较大的图，有专门针对这个问题设计的数据结构。它被称为“动态连接”:https://en.wikipedia.org/wiki/dynamic_connectivity
-
输出应该如下所示： 我甚至不知道为什么会有这样的错误。我将代码从https://www.geeksforgeeks.org/tarjan-algorithm-find-strong-connected-components/改为我的代码，并添加了input机会。我问过这个问题，一个朋友说：“这是addEdge方法中添加w后的两个代码的输出，在您的代码中w添加到所有元素中，而在原始代码中只添加到图V
-
在本章的剩余部分，我们将把注意力转向一些非常大的图。我们将用来研究一些附加算法的图，由互联网上的主机之间的连接和网页之间的链接产生的图。 我们将从网页开始。 像 Google 和 Bing 这样的搜索引擎利用了网页上的页面形成非常大的有向图。 为了将万维网变换为图，我们将把一个页面视为一个顶点，并将页面上的超链接作为将一个顶点连接到另一个顶点的边缘。 Figure 30 展示了从 Luther C
-
我有一组节点和它们之间的一组有向边。边缘没有重量。 我怎样才能找到使图强连接所必须添加的最小数量的边（即从每个结点到所有其他结点都应该有一条路径）？这个问题有名字吗？
-
考虑一个不连通的有向图的例子，其中顶点和边其中顶点是孤立的。 根据这里的答案：（对强连通图的最小加法），保证这个图所需的最小边数结果是3。 如何找到将这些边添加到哪里，即图中一条边的起始点和终止点？
-
如果您不知道SCC算法是如何工作的，请阅读本文：https://www.hackerearth.com/practice/algorithms/graphs/strong-connected-components/tutorial/（这是我能找到的最好的文章）。 在找到每个节点的完成时间后，将原图反转，从时间最高的节点开始运行DFS。如果我们从原始图中最小的节点开始运行DFS呢？为什么不管用？
-
我在读关于BFS和DFS的图算法。当我在分析用DFS寻找图中强连通分量的算法时，我产生了一个疑问。为了寻找强连通分量，book（Coremen）首先在图上运行DFS，以得到顶点的完成时间，然后在图的转置上按照第一个DFS得到的完成时间的递减顺序运行DFS。但是我不能理解为什么第二个DFS必须按照完成时间运行。我的意思是，即使我们直接在图的转置上运行DFS（忽略完成时间），它也会给我们连接的组件吗？