Алгоритм поиска цепи в неориентированном графе Опции

[Kolar]

У меня имеется неориентированный граф, заданный в виде списков смежных вершин. Мне надо узнать, есть ли путь из одной вершины графа в другую. Я пробовал делать рекурсией, но должно быть другое решение.

[Altair]

Предлагаю искать минимальный путь в графе.
Для этого можно например использовать алгоритм Дейкстры...
Но это при условии,что граф взвешен, а если нет, то нужно применять алгоритмы обхода графа (поиск в ширину, посик в глубину), и проверять есть ли путь от одной вершины к другой....

[Kolar]

Да нет же... Мне просто надо определить, соединена ли вершина A с вершиной B или нет.

[Altair]

Что значит нет?
Смотрите -для того что бы проверить -соединенна ли одна вершина с другой, требуется пройти все возможные пути по гафу отвершины A до B - (обход графа), и выбрать тот, где на пути встретилась вершина B.

[virt]

Код

program put;
const maxr=1000;{kol-vo reber}
var a:array[1..2,1..maxr]of integer;
   b:array[1..maxr]of boolean;
   r,i:integer;
   a1,a2:integer;{a1 -- nachalnaya;a2 -- konechnaya}

procedure solve(yk:integer);
var j:integer;
begin
  if yk = a2 then
     begin
        writeln('put est');
        halt;
     end;
  for j:=1 to r do
  begin
     if (a[1,j]=a1) and (not b[j]) then
     begin
        b[j]:=true;
        solve(a[2,j]);
     end;
     if (a[2,j]=a1) and (not b[j]) then
     begin
        b[j]:=true;
        solve(a[1,j]);
     end;
  end;
end;

begin

ВЫРЕЗАННО АДМИНОМ.
Готовые ответы - плохо в этом разделе.
Это теория. Автору темы просто нужно пояснить теорию, если возникнут прблеммы при реализации
мы выслушаем, и поможем..
end.

Сообщение отредактировано: Oleg_Z - 12.02.2005 15:03

[Guest]

Для этого можно например использовать алгоритм Дейкстры...
Но это при условии,что граф взвешен, а если нет,

то приписать каждой дуге единичный вес и считать, что он взвешен.

[Altair]

то приписать каждой дуге единичный вес и считать, что он взвешен.

trminator, ты прав