algorithm - 在图中查找连接的组件

Closed. This question needs to be more focused。它当前不接受答案。












想改善这个问题吗？更新问题，使其仅关注editing this post的一个问题。

6年前关闭。



Improve this question




如果我有一个无向图(以顶点列表的形式实现)，如何找到其连接的组件？如何使用快速工会？

最佳答案

使用深度优先搜索(DFS)将所有连接的单个组件标记为已访问:

dfs(node u)
  for each node v connected to u :
    if v is not visited :
      visited[v] = true
      dfs(v)


for each node u:
  if u is not visited :
    visited[u] = true
    connected_component += 1
    dfs(u)

最好的方法是使用线性时间O(n)的简单方法。
由于您询问了联合查找算法:

for each node parent[node] = node

for each node u :
   for each node v connected to u :
       if findset(u)!=findset(v) :
           union(u,v)

**I assume you know about how findset and union works **
for each node if (parent[node] == node)
    connected_component += 1

关于algorithm - 在图中查找连接的组件，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21078445/