求图连通度的算法
我正在解决编程中一个有趣的问题。它是这样的：我们不断地给一个图添加无向边，直到这个图（或子图）是连通的（即我们可以使用某种路径从那个子图中的每个顶点到达任何其他顶点）。图一连接起来我们就停下来。例如,如果我们有顶点1,2,3和4,我们希望子图1,2,3是连通的。假设我们有边（3,4）,然后（2,3）,然后（1,4）,然后（1,3）。我们只需要添加前3条边来连接子图，然后我们停止（边1,3是不需要的）。显然，每次添加一条边时，我都可以运行一个BFS，看看我们是否可以到达所需的顶点，但如果有m条边，那么我们可能需要运行m次BFS，这似乎太慢了。有更好的选择吗？多谢了。
共有1个答案
您应该研究奇妙的“不相交集数据结构”以及相应的union-find算法。它看似神奇,但最坏情况下的时间复杂度和空间复杂度都很小,分别为O（a（n））和O（n）,其中a是反阿克曼函数。
-
我想用最大流算法（Edmond Karp/Ford-Fulkerson算法）找到一个无向图的边连通性（即为了断开一个图而要去除的最小边数）, 我知道我可以通过找到图的每两个节点之间的最小最大流来完成这个任务,但这将导致O(V^2)个流网络, 但我希望使用V个流网络（只运行O(V)次max flow算法）而不是O(V^2)个
-
import scala.reflect.ClassTag import org.apache.spark.graphx._ /** Connected components algorithm. */ object ConnectedComponents { /** * Compute the connected component membership of each vertex
-
参考文献：基于连通图动态分裂的聚类算法.作者：邓健爽 郑启伦 彭宏 邓维维(华南理工大学计算机科学与工程学院，广东广州510640) 我的算法库：https://github.com/linyiqun/lyq-algorithms-lib 算法介绍 从文章的标题可以看出，今天我所介绍的算法又是一个聚类算法，不过他比较特殊，用到了图方面的知识，而且是一种动态的算法，与BIRCH算法一样，他也是一种
-
我在读关于BFS和DFS的图算法。当我在分析用DFS寻找图中强连通分量的算法时，我产生了一个疑问。为了寻找强连通分量，book（Coremen）首先在图上运行DFS，以得到顶点的完成时间，然后在图的转置上按照第一个DFS得到的完成时间的递减顺序运行DFS。但是我不能理解为什么第二个DFS必须按照完成时间运行。我的意思是，即使我们直接在图的转置上运行DFS（忽略完成时间），它也会给我们连接的组件吗？
-
谢了！
-
null 更新：最多1个简单路径。