Possible en double:
Best algorithm for detecting cycles in a directed graphalgorithme efficace pour l'identification de boucle dans un graphe orienté?
Je cherche un algorithme pour trouver des boucles dans un graphe orienté. Mon graphique a des étiquettes seulement dans les noeuds, pas dans les bords, et il peut devenir assez énorme. La sortie de l'algorithme doit être les boucles sous la forme d'un ensemble de listes, chaque liste doit contenir les étiquettes des nœuds impliqués dans une boucle, ainsi, le premier et le dernier élément de la liste doivent être identiques.
Les graphiques que j'utilise auront très probablement un seul composant connecté et aucun composant fortement connecté. Le nombre de cycles devrait être faible (je dois encore vérifier cela).
Tout bon algorithme pour exactement ceci ou quelque chose de similaire est le bienvenu.
Merci beaucoup.
PS: Si quelque chose n'est pas clair ne hésitez pas à me demander plus de détails, par exemple, le graphique est stocké (jusqu'à présent) comme un ensemble d'ensembles d'arêtes, d'un nœud à plusieurs nœuds, généralement un, cela devrait être hors de propos, à mon humble avis.
Oui, mais non. Le problème est qu'un composant fortement connecté peut contenir plusieurs cycles. Il est donc difficile de déterminer le nombre minimal de nœuds à supprimer, de sorte qu'il n'y a pas de cycles dans le résultat. – jmora