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

Question

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

Answer 1

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

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

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

Answer 2

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

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

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