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

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

Il y aura une racine.

Chaque noeud d'arbre a zéro ou plusieurs enfants.

Il est permis que deux nœuds pointent vers le même enfant. Dites, à la fois le nœud A et le noeud B a un enfant C.

Cependant, il est interdit que,

nœud A est un rejeton de noeud B et noeud B est un descendants du noeud A.

Un cas est interdit

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

Les deux nœuds C et D a un noeud enfant E,

nœud E a un enfant de A.

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

MISE À JOUR: Je réalise qu'il s'agit de trouver un cycle dans un graphe orienté. Tout à l'heure j'ai réussi à trouver une solution similaire à l'algorithme de Tarjan.

Merci pour votre commentaire.

Source

2010-02-17 SiLent SoNG

Ceci est appelé un "cycle" (pas un cercle) dans la théorie des graphes. Vous essayez de vérifier qu'un graphe donné est un "graphe acyclique orienté" ou DAG en abrégé. http://en.wikipedia.org/wiki/Directed_acyclic_graph –

Aussi, cette question a déjà été posée et répondue ici: http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in- a-directed-graph –

La structure de données que vous avez est un graphe orienté, pas un arbre. Un nœud d'arbre ne peut pas avoir plusieurs parents. – interjay

Faites un Depth First Search à travers l'arbre. Si, à un moment quelconque, vous trouvez un nœud déjà dans votre pile de retour arrière, il y a un cercle.

Source

2010-02-17 13:52:32

Il échouera dans ce cas: A-> B, B-> C, A-> C –

désolé, cela aurait dû lire "pile" au lieu de "parent" Correction –

ouais, cela fonctionne, merci de répondre. –

des cercles peuvent être trouvés en utilisant 2 pointeurs et les avancer à différents intervalles. Finalement, les pointeurs vont correspondre, indiquant une boucle, ou le "plus rapide" atteindra alors la fin. La question est généralement posée sur les listes liées, pas sur les arbres.

Source

2010-02-17 13:51:55

Je ne suis pas sûr que ce soit le * moyen le plus rapide * de le faire, mais plutôt la * manière la plus basse de la mémoire *. En outre, cela semble compliqué à faire pour un arbre. –

Le problème sera facile pour une liste chaînée. Mais considérez ce problème - l'arbre aura plusieurs extrémités. Au lieu de cela, une liste liée n'a qu'une seule fin. –

ouais ... c'est pourquoi j'ai dit que la question est habituellement posée sur des listes, pas sur des arbres. vous devrez exécuter ceci pour chaque nœud de l'arbre en utilisant une file d'attente pour vous souvenir des "prochains" nœuds de chaque nœud en tant que nouveaux points de départ. Ce serait moche. –

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

Répondre

Questions connexes