Бесконтурные орграфы., Индекс цепной сложности. Опции

[Nuty]

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

Сообщение отредактировано: Nuty - 5.11.2006 21:21

[Michael_Rybak]

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

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]

Большое спасибо за алгоритм,но есть несколько вопросов. С помощью какого представления графа реализуется этот алгоритм? Что значит выбераем "куда из неё лучше идти"?

[Michael_Rybak]

Большое спасибо за алгоритм,но есть несколько вопросов. С помощью какого представления графа реализуется этот алгоритм? Что значит выбераем "куда из неё лучше идти"?

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

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