Помогите пожалуйста решить задачу по теории графов: необходимо найти самый длинный путь в бесконтурном орграфе.
Michael_Rybak
6.11.2006 5:24
Обходим граф поиском в глубину, запоминая ответ для каждой вершины. Примерно так:
var ans: array[1..n] of longint;
function Search(i: longint): longint; var best: longint; begin if ans[i] = -1 then begin (* впервые посещена вершина i; выбираем, куда из нее лучше идти *) ans[i] := 0; для всех вершин j, в которые есть ребро из i: ans[i] := max(ans[i], 1 + Search(j)); end; Search := ans[i]; end;
begin ... for i := 1 to n do ans[i] := -1; //ни одна вершина еще не посещена
longest := 0; for i := 1 to n do longest := max(longest, Search(i));
Writeln(longest); end.
Этот полупсевдокод выводит количество ребер в самом длинном пути, работает за O(V+E). Как построить сам путь - додумаешь. Не получится - разберись с этим, и приходи.
Nuty
11.11.2006 23:33
Большое спасибо за алгоритм,но есть несколько вопросов. С помощью какого представления графа реализуется этот алгоритм? Что значит выбераем "куда из неё лучше идти"?
Michael_Rybak
12.11.2006 1:32
Цитата(Nuty @ 11.11.2006 18:33)
Большое спасибо за алгоритм,но есть несколько вопросов. С помощью какого представления графа реализуется этот алгоритм? Что значит выбераем "куда из неё лучше идти"?
выбераем "куда из неё лучше идти"? - это значит: смотрим на всех соседей; для каждого из них находим рекурсивно самый длинный путь, начинающийся из него; и выбираем соседа, который даст нам лучший результат для текущей вершины (длина ребра к соседу + его ответ).
Люди!!! Помогите!!! Нужен текст проги, которая по матрице смежности орграфа построит матрицу достижимости, контрдостижимости и сильной связности. Учусь на радиотехническом ,а вот с Паскалем вообще никак.Ну очень надо!!!!!!!!!!!!!
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.