Comment vérifier s'il y a un cercle dans un arbre?

Question

Voici un arbre:

  

  

1. Il y aura une racine.

  

2. Chaque nœud de l'arbre a zéro ou plusieurs enfants.

  

3. Il est permis que deux points de nœuds au même enfant. Par exemple, à la fois le noeud A   et le noeud B a C enfant.

  

Toutefois, il est interdit que,

  

Le noeud A est un descendant du noeud B, et   Noeud B est un rejeton de nœud A.

Un cas est interdite

  

Le nœud A a un enfant nœud C et le nœud D,

     

Les deux Noeud C et D a un noeud enfant E,

     

Node E a un enfant de A.

La question est, comment déterminer ce cercle de manière la plus rapide?

UPDATE : Je me rends compte est de trouver un cycle dans un graphe orienté. Je viens juste réussi à penser à une solution similaire à l'algorithme de Tarjan.

Merci pour les commentaires.

Answer 1

Faites un Profondeur de recherche d'abord à travers l'arbre. Si à tout moment vous trouvez un nœud qui est déjà dans votre pile de retours en arrière, il y a un cercle.

Answer 2

cercles peuvent être trouvés en utilisant 2 pointeurs et les faire avancer à différents intervalles. Finalement, les pointeurs correspondront, ce qui indique une boucle, ou la « plus rapide » on atteindra alors fin. La question est généralement posée des listes chaînées cependant, pas d'arbres.