Версия для печати темы

Автор: Nuty 5.11.2006 22:58

Помогите пожалуйста решить задачу по теории графов: необходимо найти самый длинный путь в бесконтурном орграфе.

Автор: 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

выбераем "куда из неё лучше идти"? - это значит: смотрим на всех соседей; для каждого из них находим рекурсивно самый длинный путь, начинающийся из него; и выбираем соседа, который даст нам лучший результат для текущей вершины (длина ребра к соседу + его ответ).

Представление графа - любое. Например, список ребер, исходящих из каждой вершины. Вот тут я описал то представление, которым пользуюсь в большинстве случаев: http://forum.pascal.net.ru/index.php?s=&showtopic=13418&view=findpost&p=78597

Автор: radist 13.11.2006 0:07

Люди!!! Помогите!!! Нужен текст проги, которая по матрице смежности орграфа построит матрицу достижимости, контрдостижимости и сильной связности. Учусь на радиотехническом ,а вот с Паскалем вообще никак.Ну очень надо!!!!!!!!!!!!!