遍历连接的组件

我想遍历包含顶点的无向图的每个连接组件。即我想调用每个向量V 一些函数f（V _我）... V _ķ其中V _我是含有连接到每个节点中的第i个连接分量的数据的矢量图形。遍历连接的组件

这样做最快的算法是什么？

我的第一个想法是：

存放在一个堆所有未访问顶点，然后反复地顶点离堆，使用DFS找到它的连接分量V _我，调用F（V _我）并从堆中删除组件中的所有顶点。
查找union-find不相交集合的变体，它不仅支持高效设置联合，而且还可以高效地遍历集合并查找其成员。（这可能吗？）

来源

2016-10-04 Angela Richardson

当然DFS是一个办法做到这一点，但它可能取决于如果你想优化这个用于一次性计算，或计算，将经常发生。有了更多的诀窍，你不需要每次重新发现连接的组件。 – AndyG

为什么你需要一堆？使用简单的哈希集，DFS/BFS都可以工作，并且是您可以做到的最优化。 –

我们可以假设您将图存储为邻接列表吗？我们可以假设顶点从0到N-1编号，其中N是顶点的总数？ – pkacprzak

运行经典connected components algorithm。通常，这操纵一个disjoint-sets data structure。
创建一个哈希表映射节点到链接的节点列表。
遍历每个节点

a。在不相交集数据结构中找到代表节点

b。如有必要，为散列表中的代表性节点创建链接列表

c。节点添加到与代表性节点

相关的链表这有效地花费线性时间（即Θ（| E | + | V |），预期（根据广泛接受的理解是不相交的集合是有效的线性时间）

现在你有一个哈希表，其条目数是连接组件的数量，每个值都是连接组件中所有节点的链表，现在你可以线性地迭代任何你想要

来源

2016-10-04 13:26:30

是的DFS是一个很好的选择为此。但请记住，如果运行递归DFS，给定范围10^7个节点可能会遇到内存问题。因为在麦汁情况下，所有节点将使链，您将需要巨大的规模在堆栈，造成计算器（：d）

尝试这样做：用阶为O

DFS使用堆栈（非递归DFS）（ V + E），或
使用简单的BFS（最好的选择考虑到简单，在这里节点的数量）顺序（V + E）

BFS通常用于最短路径问题，但它可以在许多使用其他应用程序，如这一个。这将从队列数据结构的堆中占用空间，通常的递归DFS占用堆栈中的空间。

来源

2016-10-04 13:55:36

如果您将图存储为邻接列表，并且顶点由从1到n-1的整数表示，那么不需要联合查找或散列表。

我们假设g[v]是与v相邻的顶点列表（向量）。此外，让cc为列表（矢量向量）的列表，其中cc[i]表示连接组件中的顶点。为了实施目的，当且仅当我们检查DFS例程中的v时，我们要使用visited[v] = true。然后伪代码看起来像这样：

dfs(v, current_cc): 
    visited[v] = true 
    current_cc.append(v) 
    for u in g[v]: 
     if not visited[u]: 
     dfs(u, current_cc) 

for v = 0 to n-1: 
    visited[i] = false 

for v = 0 to n-1: 
    if not visited[v]: 
     current_cc = [] 
     dfs(v, current_cc) 
     cc.append(current_cc) 

//From now, cc[i] is a list of vertices in the i-th connected component, 
//so we can easily iterate and call whatever we want on them.

来源

2016-10-04 14:02:21 pkacprzak

遍历连接的组件

回答

相关问题