Полная версия: Алгоритм поиска цепи в неориентированном графе
У меня имеется неориентированный граф, заданный в виде списков смежных вершин. Мне надо узнать, есть ли путь из одной вершины графа в другую. Я пробовал делать рекурсией, но должно быть другое решение.
Предлагаю искать минимальный путь в графе.
Для этого можно например использовать алгоритм Дейкстры...
Но это при условии,что граф взвешен, а если нет, то нужно применять алгоритмы обхода графа (поиск в ширину, посик в глубину), и проверять есть ли путь от одной вершины к другой....
Для этого можно например использовать алгоритм Дейкстры...
Но это при условии,что граф взвешен, а если нет, то нужно применять алгоритмы обхода графа (поиск в ширину, посик в глубину), и проверять есть ли путь от одной вершины к другой....
Да нет же... Мне просто надо определить, соединена ли вершина A с вершиной B или нет.
Что значит нет?
Смотрите -для того что бы проверить -соединенна ли одна вершина с другой, требуется пройти все возможные пути по гафу отвершины A до B - (обход графа), и выбрать тот, где на пути встретилась вершина B.
Смотрите -для того что бы проверить -соединенна ли одна вершина с другой, требуется пройти все возможные пути по гафу отвершины A до B - (обход графа), и выбрать тот, где на пути встретилась вершина B.
Код
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.
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.
Цитата
Для этого можно например использовать алгоритм Дейкстры...
Но это при условии,что граф взвешен, а если нет,
Но это при условии,что граф взвешен, а если нет,
то приписать каждой дуге единичный вес и считать, что он взвешен.
Цитата
то приписать каждой дуге единичный вес и считать, что он взвешен.
trminator, ты прав
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.