<分区>
如果我有一个无向图(作为顶点列表实现),我如何找到它的连通分量?如何使用快速联合?
<分区>
如果我有一个无向图(作为顶点列表实现),我如何找到它的连通分量?如何使用快速联合?
最佳答案
使用深度优先搜索 (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/