查找图形连接的组件 [英] Find connected components in a graph

问题描述

我很新的编程，对不起，这样的一个基本问题。我想写算法，需要实现为顶点列表无向图，并返回连接组件。谁能告诉我我该怎么使用快速愈合。什么是解决这个问题的最好方法是什么？

I am quite new to programing, sorry for such a basic question. I want to write algorithm which takes an undirected graph implemented as a list of vertices and returns connected components. Can somebody show me how can I use quick union. What's the best way to resolve this problem?

推荐答案

它非常简单，使用DFS：作为访问将标志着所有单独的连接组件

its very easy , use dfs : it will mark all individual connected components as visited

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）。
既然你问到工会查找算法，

The best way is to use this straightforward method which is linear time O(n) .
Since you asked about union-find algorithm ,

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

这篇关于查找图形连接的组件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！