#list #algorithm #linked-list #circular-list
#Список #алгоритм #связанный список #циклический список
Вопрос:
разветвленный список — это своего рода связанный список, в котором существует узел (по крайней мере), который имеет два «next», next1 и next2. т. Е. Каждый узел состоит из 3 атрибутов — value , next1 и next2. для каждого узла, кроме хотя бы одного, next2 может быть None . Я ищу алгоритм, который принимает разветвленный список в качестве входных данных, он возвращает True, если в списке есть круг, а в противном случае возвращает False. p.s. мы можем предположить, что список начинается и заканчивается как обычный связанный список (только с одним следующим) и узлом (узлами), который имеет 2 ‘next, является одним из внутренних узлов.
Комментарии:
1. Привет, добро пожаловать в SO! Чтобы улучшить ваш вопрос, он должен показать некоторые усилия — что вы пытались решить эту проблему до сих пор? Кроме того, имейте в виду, что SO — это форум по программированию: вы пытаетесь решить проблему программирования или выполняете домашнее задание для класса алгоритмов?
2. Проверьте топологическую сортировку
3. Я пытаюсь найти возможный алгоритм для написания кода. Проблема в том, что я не знаю, как начать думать о проблеме, каковы возможные ситуации и так далее. При необходимости я могу также прикрепить код python класса ForkedList .
Ответ №1:
Рассматривайте «разветвленное дерево» как ориентированный граф и ищите схемы на графике, например, алгоритм Джонсона
Комментарии:
1. Большое вам спасибо, это мне очень помогло!
Ответ №2:
Рассматривайте «разветвленное дерево» как набор зависимостей от элемента к непосредственно связанным следующим элементам. Топологическая сортировка элементов завершится ошибкой при обнаружении каких-либо округлостей.