|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 08 Jun 2002 10:07:28
To : Alexander Kazak
Subject : Re: Лазанье по деревьям
--------------------------------------------------------------------------------
Alexander Kazak wrote:
> ...
> Люди, подскажите плс чайнику, как решить следующую задачку.
> Как известно, кратчайший путь между двумя вершинами произвольного графа
> находится по алгоритму Дейкстры. Hо, если этот граф есть отбинаренное
> дерево, то путь-то всего один; веса рёбер в этом случае не имеют
> никакого значения. Как бы побыстрее и поэффективнее найти этот путь?
> Hеужели без Дейкстры не обойтись?
> ...
Hе нужен тут никакой Дийкстра. Если в твоем дереве есть выделенная
корневая вершина R (а она у тебя, по-видимому, есть, раз ты называешь
свое дерево бинарным), то в каждой паре соседних вершин одна вершина
является предком (та, что ближе к корню), а другая - потомком (та, что
дальше от корня).
Если в исходной структуре данных, представляющей твое дерево, есть
ссылки от потомков к предкам, то построить путь от вершины A к вершине B
несложно - надо просто строить пути, двигаясь из обоих вершин по ссылкам
к предкам до тех пор пока эти пути не сойдутся в некоторой вершине C
(они могут сойтись в корне, а могут сойтись и раньше). Путь A - ... - C
- ... - B и есть искомый путь.
Если же ссылок от потомков к предка в структуре данных нет, то придется
делать поиск путей к вершинам A и B из корневой вершины R. Если вершины
обладают ключами и дерево упорядочено, то поиск может быть
целенапрваленным. В противном случае придется делать обход дерева. Два
найденных пути будут сходиться в некоторой вершине C и т.д. (см. выше)
Есть и другие варианты. Все во многом зависит от конкретной струкуры
данных, представляющей дерево. Как оно у тебя представлено?
Best regards,
Андрей.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Лазанье по деревьям 
