Trouver tous les sous-graphes déconnectés dans un graphique
https://stackoverflow.com/questions/1348783
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai un graphique qui contient un nombre inconnu de sous-graphes déconnectés. Qu'est-ce qu'un bon algorithme (ou bibliothèque Java) pour les trouver?
La solution
Je pense que ce que vous cherchez est convenu d'appeler un . Il est à vous si vous traversez le graphique à travers un BFS ou DFS.
En gros, vous prenez un nœud sans étiquette (AKA non coloré) et d'attribuer une nouvelle étiquette à elle. Vous assigner la même étiquette à tous les noeuds adjacents à celui-là, et ainsi de suite pour tous les noeuds qui sont accessibles à partir de ce noeud.
En l'absence de nœuds plus accessibles peuvent être étiquetés, vous recommencez en choisissant un autre nœud sans étiquette. Notez que le fait que ce nouveau nœud est sans étiquette implique qu'il ne soit pas accessible à partir de notre nœud plus tôt et est donc dans un autre composant déconnecté.
Quand il n'y a pas de nœuds plus non marqués, le nombre d'étiquettes distinctes que vous deviez utiliser est le nombre de composants du graphe. L'étiquette pour chaque noeud indique quel noeud fait partie de quel composant.
Autres conseils
Pas une implémentation Java mais peut-être il sera utile pour quelqu'un, voici comment le faire en Python:
import networkx as nx
g = nx.Graph()
# add nodes/edges to graph
d = list(nx.connected_component_subgraphs(g))
# d contains disconnected subgraphs
# d[0] contains the biggest subgraph
Il y a beaucoup de facettes de cette question qui ne sont pas complètement expliqué, donc je vais donner une réponse quelque peu exhaustive. Ma tendance à afficher des murs-de-texte nonobstant. :. / Notez également que je suis supposer que ce soit une question de question de devoirs ou d'auto-éducation, donc je ne vais pas donner une réponse straight-up
Les deux algorithmes de base pour la détection de la connectivité d'un graphique est profondeur Première recherche et < a href = "http://en.wikipedia.org/wiki/Breadth-first_search" rel = "noreferrer"> Largeur de recherche d'abord . Ce sont vraiment les 2 points de départ que vous souhaitez regarder. Les deux vous arriver à la solution, mais de différentes manières, et il est difficile de faire valoir ce qui est « meilleur » sans tenir compte de certains aspects jolis en profondeur du problème. Mais nous allons passer.
Comme je l'ai mentionné précédemment, vous avez omis quelques détails importants, et je vais aborder quelques possibilités ici.
Votre graphe orienté ou non orienté? et considérez-vous comme la connectivité dans le sens « fort » (auquel cas, voir la réponse de Oggy), ou la connectivité dans le sens « faible »? En fonction de votre réponse, vous devrez approcher votre algorithme de manière subtilement différente. Notez que, pour un graphe non orienté, la connectivité faible et forte sont équivalentes, donc c'est agréable. Mais vous devez garder la structure du graphique à l'esprit quel que soit, en mettant en œuvre ou de trouver un algorithme.
En outre, il y a la question de ce que vous entendez par « trouver les sous-graphes » (paraphrase). Habituellement, la connectivité graphique est un problème de décision - tout simplement « il y a un graphe connexe » ou « il y a deux ou plusieurs sous-graphes (aka, il est déconnecté) ». Avoir un algorithme pour qui nécessite le moins de bookwork, ce qui est agréable. :) La prochaine étape serait le nombre de graphiques, littéralement le nombre d'entre eux, et que bookwork est pas si mal. Penultimately, vous voudrez peut-être une liste de noeuds dans chaque sous-graphe. Enfin, vous pouvez littéralement copier les sous-graphes, les arêtes et tous (donc le type de retour serait une liste de graphiques, je suppose, avec un invariant implicite que chaque graphe est connexe). Aucun de ces différents types-résultat nécessiterait un algorithme différent, mais sera certainement besoin d'une approche différente du livre d'artiste.
Tout cela peut sembler un montant ridicule de trop pour ce qui est une question assez basique, mais je pensais que je venais de mettre en lumière tous les aspects impliqués dans même une simple question de graphe. Comme une sorte de cliffhanger, notez rien de tout cela touche même pas encore à l'exécution ou l'utilisation de la mémoire! :) - Agor
JGraphT est une bibliothèque graphique open source sous licence belle sous la licence LGPL. Je l'ai utilisé dans le passé pour traiter des graphiques et des cycles de détection dans les graphiques. Il est également assez facile à utiliser, et vous pouvez utiliser JGraph pour visualiser les graphiques.
Je suppose que vous voulez trouver tous les composants connectés (fortement)? Pour cela, vous pouvez utiliser algorithme de Tarjan (une variante de DFS)
Qu'en est-il une largeur d'abord la recherche pour trouver tous les noeuds connectés? Une fois que vous avez la liste des noeuds connectés, vous soustraire cette liste de la liste de tous les nœuds. Vous vous retrouvez avec une liste de noeuds déconnectés
Je suis tombé sur un problème similaire où je voulais que tous les sous-graphes faiblement reliés d'un graphe orienté. Je blogué sur ce . J'ai utilisé l'API JUNG et comparer deux approches. Ma première approche pourrait être utilisée comme modèle pour résoudre votre problème.
