Обнаружение петель в связанном графике - PullRequest
0 голосов
/ 22 ноября 2018

Большинство примеров, которые я нашел, относятся только к одиночным связанным спискам.Мне нужно решение для нескольких связанных списков.

Изображение проще (допустимо):

enter image description here

Недействительно:

enter image description here

Какой алгоритм сможет вернуть начало цикла (B) и не столкнется с E?Хорошей отправной точкой было бы также знать, есть ли вообще петля.Такие вещи, как , это или подсчет ребер не работает (потому что не одиночные ссылки ...).

Спасибо.

1 Ответ

0 голосов
/ 06 декабря 2018

Просто проверьте, существует ли маршрут от «конца узла соединения (B)» до «начала узла соединения (C)», если да, будет создан новый цикл.Не совсем отвечает, но достаточно хорошо ...

...