Для дерева T = (V, E) найти прямой путь от вершины v к вершине w.

Question

Я застрял в своем задании алгоритма, который просит найти прямой путь в дереве (V, E) с n вершинами (ациклический непрямой граф) от вершины v до вершины w во временной сложности O (dist (v, w) )). Мне нужно найти препроцесс (который запускается в O (n)) для хранения некоторой информации, чтобы я мог достичь временной сложности O (dist (v, w)).

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

Нет полного решения.

Я уже пытался сохранить возможный путь, но для создания глобального Adj List мне нужно квадратичное время O (n ^ 2). Также Dijkstra работает выше запрошенной сложности времени (и все алгоритмы маршрутизации для сети). Два узла в дереве имеют уникальный путь.

Также пытался использовать динамическое программирование для хранения всех уже обнаруженных путей, но я думаю, что получаю за линейное время. Запустите BFS и сохраните все предыдущие пути, например: (node, node) : next hop

(A, B) : B and (B, A) : A
(B, C) : C (C, B): B (A, C) : B and (C, A): B

Поэтому мне понадобится (1 + 2 + 3 + 4 + 5 + ... + n - 1 + n) = n^2

Answer 1

Если ваша сеть является деревом, то каждая вершина имеет только один «входящий» край.Поэтому вам следует попробовать перейти по ссылкам от W к V (следуя входящим ребрам), а не наоборот.Это даст вам путь в обратном порядке.Сохраните его в списке и инвертируйте для получения результата.

Обратите внимание, что вам может потребоваться создать словарь вершин {child: parent}, чтобы сделать это, если у вас еще нет способа пройти черездерево снизу вверх.Построение этого словаря займет время O (E), затем поиск пути займет время dist (V, W).