Циклические и ациклические структуры данных

Question

В чем разница, можете ли вы привести примеры?

Answer 1

Если вы можете начать с узла X, перейдите по структуре, не посещая один и тот же узел дважды и возвращайтесь в X, тогда структура циклична. Цикл - это серия узлов, посещаемых по этому пути.

Обычно мы делаем исключение для циклов размера 2 (т. Е. Посещаем сосед и возвращаемся назад) в неориентированных структурах (где соединения между двумя узлами не имеют определенного направления).

Если структура не циклическая, она должна быть ацикличной.

Answer 2

Если вы можете следовать указателям по кругу, чтобы вернуться к исходному объекту.

Например:
А-> В-> А цикл
А-> В-> С-> А цикл
А-> В А-> С С-> D B- > D не является циклом (это направленный ациклический график)

Это относится к refcounted smartpointer, который «владеет» объектом, на который они указывают. Потому что тогда они становятся Münchhausen и удерживают друг друга в памяти, даже если они недоступны из того, что будет gc-корнями в сборнике мусора.