Étant donné un graphique non orienté, quel est le meilleur algorithme à détecter s'il contient un cycle ou non?Algorithme le plus rapide pour détecter une boucle dans un graphique
Une première ou une première recherche en profondeur tout en gardant la trace des nœuds visités est une méthode, mais c'est O (n^2). Y at-il quelque chose de plus rapide?
L'algorithme BFS et DFS pour le graphe donné G (V, E) a une complexité temporelle de O (| V | + | E |). Donc, comme vous pouvez le voir, c'est une dépendance linéaire de l'entrée. Vous pouvez effectuer quelques heuristiques dans le cas où vous avez un graphe très spécialisé, mais en général ce n'est pas si mal d'utiliser DFS pour ça. Vous pouvez vérifier quelques informations here. Quoi qu'il en soit, vous devez parcourir tout le graphique.
Tester la présence d'un cycle dans un graphe G (V, E) en utilisant Depth First Search est O (| V |, | E |) si le graphe est représenté en utilisant une liste d'adjacence.
Il est nécessaire de parcourir le graphique entier pour montrer qu'il n'y a pas de cycles. Si vous êtes simplement intéressé par la présence/l'absence d'un cycle, vous pouvez évidemment terminer au point où un cycle est découvert.
Voici votre algorithme O(V):
def hasCycles(G, V, E):
if E>=V:
return True
else:
# here E<V
# perform O(E+V) = O(V) algorithm
...
Le ... peut être effectuée avec DFS. Si vous avez E<V et les bords sont stockés de manière significative (sous forme de liste), vous pouvez probablement faire O (E) + journaux qui feraient l'algorithme entier O(min(E,V))+logs.
J'espère que vous aimerez cette réponse, même si c'est un peu tard!
Comme vous le voyez, j'utilise fortement le fait qu'un graphe non orienté sans cycles est un sous graphe d'un arbre et doit donc avoir E
Si vous avez un graphique simple, vous pouvez calculer le nombre cyclomatique:
C = E − N + P
Où C est le nombre de cycles, E est le nombre d'arêtes, N est le nombre de nœuds et P est la nombre de composants. Si vous graphique est connecté, il est:
C = E - N + 1
Merci, je crois que je fait abstraction du fait que l'ensemble de tous les nœuds visités est très faible au début et ne pousse que comme l'algorithme. –