Алгоритм поиска цепи в неориентированном графе |
1. Заголовок или название темы должно быть информативным !
2. Все тексты фрагментов программ должны помещаться в теги [code] ... [/code] или [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ" и используйте ПОИСК !
4. НЕ используйте форум для личного общения!
5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!
Алгоритм поиска цепи в неориентированном графе |
Kolar |
Сообщение
#1
|
Группа: Пользователи Сообщений: 4 Пол: Мужской Репутация: 0 |
У меня имеется неориентированный граф, заданный в виде списков смежных вершин. Мне надо узнать, есть ли путь из одной вершины графа в другую. Я пробовал делать рекурсией, но должно быть другое решение.
|
Altair |
Сообщение
#2
|
Ищущий истину Группа: Пользователи Сообщений: 4 825 Пол: Мужской Реальное имя: Олег Репутация: 45 |
Предлагаю искать минимальный путь в графе.
Для этого можно например использовать алгоритм Дейкстры... Но это при условии,что граф взвешен, а если нет, то нужно применять алгоритмы обхода графа (поиск в ширину, посик в глубину), и проверять есть ли путь от одной вершины к другой.... -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
Kolar |
Сообщение
#3
|
Группа: Пользователи Сообщений: 4 Пол: Мужской Репутация: 0 |
Да нет же... Мне просто надо определить, соединена ли вершина A с вершиной B или нет.
|
Altair |
Сообщение
#4
|
Ищущий истину Группа: Пользователи Сообщений: 4 825 Пол: Мужской Реальное имя: Олег Репутация: 45 |
Что значит нет?
Смотрите -для того что бы проверить -соединенна ли одна вершина с другой, требуется пройти все возможные пути по гафу отвершины A до B - (обход графа), и выбрать тот, где на пути встретилась вершина B. -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
virt |
Сообщение
#5
|
Знаток Группа: Пользователи Сообщений: 419 Пол: Мужской Репутация: 6 |
Код 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 - -------------------- |
Guest |
Сообщение
#6
|
Гость |
Цитата Для этого можно например использовать алгоритм Дейкстры... Но это при условии,что граф взвешен, а если нет, то приписать каждой дуге единичный вес и считать, что он взвешен. |
Altair |
Сообщение
#7
|
Ищущий истину Группа: Пользователи Сообщений: 4 825 Пол: Мужской Реальное имя: Олег Репутация: 45 |
Цитата то приписать каждой дуге единичный вес и считать, что он взвешен. trminator, ты прав -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
Текстовая версия | 16.05.2024 9:04 |