Buscar componentes conectados en un gráfico [cerrado]
Si tengo un gráfico no dirigido (implementado como una lista de vértices), ¿cómo puedo encontrar sus componentes conectados? ¿Cómo puedo usar quick-union?
38
Author: approxiblue, 2014-01-12
2 answers
Utilice la búsqueda en profundidad (DFS) para marcar todos los componentes conectados individuales como visitados:
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)
La mejor manera es usar este método sencillo que es tiempo lineal O(n).
Desde que preguntaste sobre el algoritmo union-find:
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
36
Author: Aseem Goyal,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-11-24 05:58:01
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-11-24 05:58:01
Para cada edge(u,v)
find union(u,v)
usando quick union-find dataestructure y find set de cada vértice usando find(v)
. Cada nuevo conjunto es un componente conectado en el gráfico
2
Author: Vikram Bhat,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-01-12 18:48:52
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-01-12 18:48:52