Cyclic and acyclic data structures

开发者_运维知识库What is the difference, can you give me examples?

---

If you can start at node X, navigate through the structure without visiting the same node twice, and arrive back at X, then the structure is cyclic. The cycle is the series of nodes visited along such a path.

We usually make an exception for cycles of size 2 (i.e., visit a neighbor and come right back) in undirected structures (where connections between two nodes do not have a particular direction).

If a structure is not cyclic, it must be acyclic.

---

If you can follow pointers in a circle to come back to the original object.

For example:
A->B->A is a cycle
A->B->C->A is a cycle
A->B A->C C->D B->D is no cycle (it's a directed acyclic graph)

This is relevant for refcounted smartpointer which "own" the object they point to. Because then they become Münchhausen and hold each other in memory even if they are unreachable from what would be gc-roots in a garbage collected language.