Trouver composantes connexes dans un graphe

Si j'ai un graphe non-dirigé (implémentée par une liste de sommets), comment puis-je trouver ses composants connectés? Comment puis-je utiliser rapide de l'union?

Les sommets sont représentés sous forme de liste, mais la façon dont les bordures sont représentés?
Le graphe G est une liste de listes de nombres entiers. Il n'y a bord de la forme i à j ssi j est sur la liste G[i] et i sur G[j].
Cette question semble être hors-sujet, car il est à propos de l'informatique, pas de programmation, et appartient à cs.stackexchange.com
j'ai répondu à cette question parce que vous semblez nouveau DONC , mais nowonwards vous devriez aussi poster sur ce que vous avez essayé .
Comment cette question est trop vaste?

InformationsquelleAutor abalcerek | 2014-01-12

algorithm graph

39

Utilisation depth-first search (DFS) pour marquer tous les différents composants connectés visité:
```
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)
```
Le meilleur moyen est d'utiliser cette méthode simple qui est linéaire en temps O(n).

Depuis que vous avez demandé à propos de l'union-find algorithme:
```
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
```
- Est-il une raison d'utiliser dfs sur bfs?
- oui, depuis BFS couvre le graphique en "couches" de départ à partir du nœud X vous avez choisi au début, signifie que si un nœud Y n'est pas accessible à partir de X, puis BFS ne pas le visiter. Alors que DFS dans un tel scénario, pourquoi? parce que quand vous couvrez toutes les accessible nœuds de X et il y a encore quelques non visités nœuds, puis DFS va recommencer à partir de l'un de ces nœuds, ainsi DFS vous donne une forêt, tandis que BFS un seul arbre.
- Je ne suis pas sûr de comprendre. Ce qui nous empêche de l'exécution de la SECTION d'un de ceux inconnu/inconnu nœuds? Il semble y avoir rien dans la définition de la dsv qui nécessite de fonctionner pour toutes les inconnues nœud dans le graphe. Si vous exécutez un BFS ou DFS sur chaque inconnues nœud, vous obtiendrez une forêt de composants connectés.
- rien ne vous empêche de courir BFS à partir de ces nœuds, ce que je voulais dire, c'est que BFS ne peut tout simplement pas le faire sur son propre dans une exécution de l'algorithme tout en DFS peut, veuillez jeter un oeil ici pour voir le droit DFS de mise en œuvre de en.wikipedia.org/wiki/Depth-first_search#Pseudocode avis que l'enjeu contient tous les sommets v dans le graphique.
- Goyal, avis qu'il n'est pas de stopper la condition dans votre récursive dfs qui rend votre mise en œuvre incorrecte.
- Ce qui vous fait penser que la pile contient tous sommets du graphe? Le code traite seulement les nœuds (w) adjacents au nœud source (v), n' tous nœuds G. regarder de plus près à la ligne 3 dans le récursive et la ligne 8 dans le interative mise en œuvre dans le lien que vous avez posté.
- En ce qui concerne votre demande Aseem de l'algorithme est incorrect: vous n'avez pas besoin explicite de la base de cas (ce que vous appelez un "arrêt maladie") pour sortir de la récursivité, parce que pour la boucle (ligne 2 ci-dessus) terminera finalement (depuis un nœud donné a finitely le nombre de nœuds connectés). Une fois que tous les non visités voisins sont dfs'd, le haut niveau dfs appels tout bas.
- J'ai juste mis en œuvre un algorithme en Python: stackoverflow.com/q/42152900/4014959
- Je ne suis pas d'accord avec votre affirmation "que si un nœud Y est pas accessible à partir de X, alors BFS ne pas le visiter. Alors que DFS dans un tel scénario va faire.." Si un nœud n'est pas accessible à partir de X aucun de BFS ou DFS peut vous donner ce nœud, si vous êtes partant de X. Pouvez-vous donner un exemple de ce que vous dites?
InformationsquelleAutor Aseem Goyal
2

Pour chaque edge(u,v) trouver union(u,v) l'aide rapide de l'union-find discbased et de trouver ensemble de chaque sommet à l'aide de find(v). Chaque nouveau jeu est une composante connexe du graphe

InformationsquelleAutor Vikram Bhat

Vous devez vous connecter pour publier un commentaire.