Моя проблема заключается в том, что мне было поручено разработать эффективный алгоритм, который задавал любой неориентированный взвешенный граф G = (V, E, L) два узла s, t ∈ V и максимальное ребро длина L в качестве входов отвечает, можно ли достичь узла t от узла s или нет. Жесткая часть заключается в том, что мой алгоритм должен работать во времени O (n + m)!Адаптация глубины первого поиска для пути графа
У меня уже есть справедливая идея, я считаю, что мне нужно использовать глубину первого поиска, которая адаптируется с использованием операций O (1), чтобы сохранить время работы. Я чувствую, что мне нужно добавить условные тесты к стандартному поиску первой глубины, который находит путь между двумя узлами для сравнения, если L < = currentEdgeLength, и только добавьте новый узел в путь, если это условие истинно.
Любой вход был бы рад!
Идея звучит правильно. – Gassa
Что касается _adapted с использованием операций O (1), я не понимаю этого, но когда вы храните график в виде списка смежности, простая поисковая реализация по глубине действительно принимает O (m + n). – Gassa