强连通图的极小加
我有一组节点和它们之间的一组有向边。边缘没有重量。
我怎样才能找到使图强连接所必须添加的最小数量的边（即从每个结点到所有其他结点都应该有一条路径）？这个问题有名字吗？
共有1个答案
这是一个非常经典的图问题。
- 运行类似于Tarjan-SCC算法的算法来查找所有scc。将每个SCC看作一个新的顶点，根据原点图将这些新顶点之间的边连接起来，得到一个新的图。显然，新图是一个有向无环图(DAG)。
- 在DAG中，找到所有阶为0的顶点，我们定义它们为{X}；找到所有out度为0的顶点，我们定义它们为{Y}。
- 如果DAG只有一个顶点，则答案为0；否则，答案为max(X，Y).
-
我有一个强连通图。我想移除一个边并检查是否仍然保持强连接。因为我将N=图中节点的总数取为10，并且我感兴趣的大多数图都有25条以上的边，所以很难检查一次使用一条，去掉边。 如何解决这个问题？多谢了。
-
考虑一个不连通的有向图的例子，其中顶点和边其中顶点是孤立的。 根据这里的答案：（对强连通图的最小加法），保证这个图所需的最小边数结果是3。 如何找到将这些边添加到哪里，即图中一条边的起始点和终止点？
-
我在读关于BFS和DFS的图算法。当我在分析用DFS寻找图中强连通分量的算法时，我产生了一个疑问。为了寻找强连通分量，book（Coremen）首先在图上运行DFS，以得到顶点的完成时间，然后在图的转置上按照第一个DFS得到的完成时间的递减顺序运行DFS。但是我不能理解为什么第二个DFS必须按照完成时间运行。我的意思是，即使我们直接在图的转置上运行DFS（忽略完成时间），它也会给我们连接的组件吗？
-
我想在无向图中找到一个强连通分量，即如果我从一个节点开始，那么我将回到节点，并且每个边都被精确地访问一次。 对于有向图，可以用Tarjan算法求强连通分量，但是对于无向图，该怎么办。
-
输出应该如下所示： 我甚至不知道为什么会有这样的错误。我将代码从https://www.geeksforgeeks.org/tarjan-algorithm-find-strong-connected-components/改为我的代码，并添加了input机会。我问过这个问题，一个朋友说：“这是addEdge方法中添加w后的两个代码的输出，在您的代码中w添加到所有元素中，而在原始代码中只添加到图V