Как да намеря всички равни пътища в изродено дърво от конкретен начален връх?

Имам някои 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
@Petr, грешката е моя. Този път е правилен.   -  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