Как найти все равные пути в вырожденном дереве из определенной начальной вершины?

У меня есть degenerate tree (выглядит как массив или двусвязный список). Например, вот это дерево:

введите здесь описание изображения

Каждое ребро имеет некоторый вес. Я хочу найти все равные пути, которые начинаются в каждой вершине.

Пусть ребра имеют следующие веса (это просто пример):

a-b = 3

b-c = 1

c-d = 1

d-e = 1

Затем:

  1. Вершина A не имеет равного пути (нет вершины с левой стороны).
  2. Вершина B имеет одну равную пару. Путь B-A равен пути B-E (3 == 3).
  3. Вершина C имеет одну равную пару. Путь B-C равен пути C-D (1 == 1).
  4. Вершина D имеет одну равную пару. Путь C-D равен пути D-E (1 == 1).
  5. Вершина E не имеет равного пути (нет вершины с правой стороны).

Я реализую простой алгоритм, который работает в O(n^2). Но это слишком медленно для меня.


c++ graph sum algorithm doubly-linked-list
person David    schedule 19.05.2015    source источник
comment
Почему в вашем примере вершина C не имеет таких путей? Разве C-B не равно C-D?   -  person Petr    schedule 19.05.2015
comment
@ Петр, это моя ошибка. Этот путь правильный.   -  person David    schedule 19.05.2015
comment
@David Является ли ограничением, что когда у вас есть узел, стоимость пути от узла к родителю должна равняться стоимости пути от узла n до некоторого потомка n'?   -  person Vivin Paliath    schedule 19.05.2015
comment
@VivinPaliath, да, ты прав. Мы выбрали некоторую вершину V. Затем перебираем все вершины-предки и потомки и пытаемся найти такие две вершины V1 и V2, что путь от V1 до V равен пути от V до V2.   -  person David    schedule 19.05.2015
comment
Итак, просто для дальнейшего пояснения, если в приведенном выше примере все веса были равны 1, то C-A будет равняться C-E (2 == 2)? т.е. это не обязательно должен быть родитель, просто какой-то предок?   -  person Matt Messersmith    schedule 19.05.2015
comment
Итак, вам нужны все кортежи (v1, v, v2), где v1 и v2 являются произвольными предком и потомком, такие что c(v1, v) = c(v, v2)? В ваших примерах я вижу, что v1 всегда является родителем. Что, если бы стоимость пути от a до b была равна 1 вместо трех? Тогда вы бы считали C-A и C-E частью решения? Похоже, вам придется, исходя из вашего определения.   -  person Vivin Paliath    schedule 19.05.2015
comment
@ mwm314, ты прав. Если бы в приведенном выше примере все веса были равны 1, то C-A был бы равен C-E (2 == 2)   -  person David    schedule 19.05.2015
comment
@VivinPaliath, да, мне просто нужны все кортежи (v1, v, v2), где c(v1, v) = c(v, v2). Если a-b равно 1, то C-A и C-E - хорошее решение.   -  person David    schedule 19.05.2015
comment
Пожалуйста, не задавайте один и тот же вопрос дважды. Тем более, что вам уже ответили.   -  person amit    schedule 19.05.2015
comment
@amit, кажется, этот ответ неправильный, или я его не понимаю.   -  person David    schedule 19.05.2015
comment
@David Затем прокомментируйте, отредактируйте свой вопрос и добавьте к нему награду, чтобы привлечь больше внимания. Не задавайте один и тот же вопрос дважды.   -  person amit    schedule 19.05.2015