Comment vérifier s'il y a un cercle dans un arbre?
-
21-09-2019 - |
Question
Voici un arbre:
Il y aura une racine.
Chaque nœud de l'arbre a zéro ou plusieurs enfants.
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.
La solution
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.
Autres conseils
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.