Structures de données cycliques et acycliques

Question

Quelle est la différence, pouvez-vous me donner des exemples?

Answer 1

Si vous pouvez commencer au nœud X, naviguer dans la structure sans visiter deux fois le même nœud, et revenir à X, alors la structure est cyclique. Le cycle est la série de nœuds visités le long d'un tel chemin.

Nous faisons généralement une exception pour les cycles de taille 2 (c'est-à-dire, rendre visite à un voisin et revenir immédiatement) dans des structures non dirigées (où les connexions entre deux nœuds n'ont pas de direction particulière).

Si une structure n'est pas cyclique, elle doit être acyclique.

Answer 2

Si vous pouvez suivre des pointeurs dans un cercle pour revenir à l'objet d'origine.

Par exemple:
A-> B-> A est un cycle
A-> B-> C-> A est un cycle
A-> B A-> C C-> D B- > D n'est pas un cycle (c'est un graphique acyclique orienté)

Ceci est pertinent pour les smartpointer refcounted qui "possèdent" l'objet vers lequel ils pointent. Parce qu'ils deviennent alors Münchhausen et se tiennent mutuellement en mémoire même s'ils sont inaccessibles à partir de ce qui serait gc-roots dans une langue collectée par les ordures.