Cycles dans un graphe non orienté

Question

Étant donné un graphe non orienté G \=( V , E ) avec n sommets (| V | = n ), comment trouver s'il contient un cycle en O ( n ) ?

Answer 1

Je pense que la première recherche en profondeur résout le problème. Si une arête non explorée mène à un nœud déjà visité, alors le graphe contient un cycle. Cette condition rend également la recherche O(n), puisque l'on peut explorer au maximum n arêtes sans que cette condition ne devienne vraie ou qu'il ne reste aucune arête non explorée.

Answer 2

En fait, la recherche en profondeur (ou en largeur) n'est pas tout à fait suffisante. Il faut un algorithme beaucoup plus complexe.

Par exemple, supposons qu'il existe un graphe avec des nœuds {a,b,c,d} et des arêtes {(a,b),(b,c),(b,d),(d,c)} où une arête (x,y) est une arête de x à y. (Cela ressemble à quelque chose comme ça, avec toutes les arêtes dirigées vers le bas).

    (a)
     |
     |
    (b)
    / \ 
  (d)  |
   |   |
    \ /
    (c)

Ensuite, la première recherche en profondeur peut visiter le nœud (a), puis (b), puis (c), puis revenir à (b), puis visiter (d), et enfin visiter (c) à nouveau et conclure qu'il y a un cycle - alors qu'il n'y en a pas. Une chose similaire se produit avec la largeur d'abord.

Ce que vous devez faire, c'est garder la trace des nœuds que vous êtes en train de visiter. Dans l'exemple ci-dessus, lorsque l'algorithme atteint (d), il a fini de visiter (c) mais pas (a) ni (b). Donc, revisiter un nœud terminé est bien, mais visiter un nœud non terminé signifie que vous avez un cycle. La façon habituelle de procéder est de colorer chaque nœud en blanc (pas encore visité), en gris (visite des descendants) ou en noir (visite terminée).

voici un pseudo-code !

define visit(node n):
  if n.colour == grey: //if we're still visiting this node or its descendants
    throw exception("Cycle found")

  n.colour = grey //to indicate this node is being visited
  for node child in n.children():
    if child.colour == white: //if the child is unexplored
      visit(child)

  n.colour = black //to show we're done visiting this node
  return

alors l'exécution de visit(root_node) lèvera une exception si et seulement si il y a un cycle (initialement tous les noeuds devraient être blancs).

Answer 3

Un graphe G non orienté et connecté qui n'a pas de cycles est un arbre ! Tout arbre a exactement n - 1 arêtes, donc nous pouvons simplement parcourir la liste des arêtes du graphe et compter les arêtes. Si nous comptons n - 1 arêtes, nous retournons "oui", mais si nous atteignons la nième arête, nous retournons "non". Cela prend O (n) temps car nous regardons au maximum n arêtes.

Mais si le graphe n'est pas connecté, alors nous devrons utiliser DFS. Nous pouvons parcourir les arêtes et si des arêtes non explorées mènent au sommet visité, alors il y a un cycle.

Answer 4

Vous pouvez le résoudre en utilisant DFS. Complexité en temps : O(n)

L'essence de l'algorithme est que si un composant/graphique connecté ne contient PAS de CYCLE, il sera toujours un ARBRE. Voir ici pour la preuve

Supposons que le graphe n'a pas de cycle, c'est-à-dire qu'il s'agit d'un arbre. Et si l'on regarde un arbre, chaque arête part d'un nœud :

1.soit atteint son seul et unique parent, qui se trouve un niveau au-dessus de lui.

2.ou atteint ses enfants, qui sont un niveau en dessous.

Ainsi, si un nœud possède une autre arête qui n'est pas parmi les deux décrites ci-dessus, elle connectera évidemment le nœud à un de ses ancêtres autre que son parent. Cela formera un CYCLE.

Maintenant que les faits sont clairs, tout ce que vous avez à faire est de lancer un DFS pour le graphe (en considérant que votre graphe est connecté, sinon faites-le pour tous les sommets non visités), et SI vous trouvez un voisin du nœud qui est VISITÉ et NON son parent, alors mon ami il y a un CYCLE dans le graphe, et vous êtes FAIT.

Vous pouvez garder la trace du parent en passant simplement le parent comme paramètre lorsque vous faites des DFS pour ses voisins. Et comme vous avez seulement besoin d'examiner n tout au plus, la complexité temporelle sera de O(n).

J'espère que la réponse vous a aidé.

Answer 5

Au fait, si vous savez qu'il est connecté, alors il s'agit simplement d'un arbre (donc pas de cycles) si et seulement si |E|=|V|-1 . Bien sûr, ce n'est pas une petite quantité d'informations :)