1

Тема: Длиннейший путь

Как можно решить эту задачу?
Дан неориентированный связный граф без циклов. Надо найти в нем самый длинный путь из i в j (вершину).
Мне кажется тут надо использовать, чтобы найти самую глубокую вершину. А как все это обобщить и реализовать пока не знаю!

2

Re: Длиннейший путь

Быть может, все несколько проще? Судя по всему, путь в таком графе между двумя вершинами единственный, т.к. такой граф - дерево.

Т.е. нужно просто найти этот путь, а это можно сделать при помощи одного из обходов графа (в глубину или ширину).

Джеймс Гослинг с нами!

3

Re: Длиннейший путь

Если же граф ориентированный, то задача решается очевидной динамикой.

4 Отредактировано KADR (2009-07-14 22:43:37)

Re: Длиннейший путь

Диаметр дерева находится так(без доказательства):
Выбираем любую вершину, пускаем от нее поиск в ширину. Затем выбираем вершину, которая находится на наибольшем удалении от стартовой вершины. Утверждается, что она будет одним из концов диаметра. Чтобы найти второй конец диаметра - запустим поиск в ширину от первого и выберем самую удаленную вершину от него.

Сложность выходит О(Н).