С наступающим Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы
PascalABC.NET
Войти
Регистрация
Восстановить пароль
 
Tr1kss
1 / 1 / 0
Регистрация: 19.12.2013
Сообщений: 13
1

Поиск пути в неориентированном графе

12.06.2014, 21:02. Просмотров 244. Ответов 0
Метки нет (Все метки)

{Задача: имеется N населенных пунктов. Некоторые пары
пунктов соединены дорогами требуется определить можно ли из
пункта с номером n1 попасть в пункт с номером n2.Если да, то
указать какой-нибудь путь.Граф задается матрице смежности.
В процедуре поиска пути нужно использовать рекурсию.
Получается сделать обход всех вершин графа, но не получается вывести путь.
Заранее благодарен.
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 Uses CRt;
 Const NMax=10;
 Type Matrix=array[1..NMax,1..Nmax] of word;
  var a:Matrix;
     First,Last,n:integer;
     Visited:array[1..Nmax] of boolean;   
 
 procedure MakeMatrix(var a:Matrix;n:word);//создание матрицы смежности
 var i,j:word;
 begin
   for i:=1 to n do
     for j:=1 to n do
        if i=j then 
          a[i,j]:=0 //путь сам в себя
        else
        if j>i then
        begin
          writeln('есть путь?',i,' ',j);
          readln(a[i,j]);
        end
        else
        a[i,j]:=a[j,i];
 end;
 procedure PrintMatrix(a:Matrix;n:word);//вывод на экран матрицы
 var i,j:byte;
 begin
   for i:=1 to n do
   begin
     for j:=1 to n do
       write(a[i,j]:2);
     writeln;  
   end;   
 end;
 procedure SearchWay(first,last,n:integer);//поиск пути эту процедуру нужно доработать
 var r,i:integer;
     ok:boolean;
     p:array[1..nmax]of integer;
 begin
   write('>>>',first);
   Visited[first]:=true;
   for r:=1 to n do
   if (a[first,r]<>0) and (not Visited[r]) then
   begin
     SearchWay(r,last,n);
   end;
 end;
 //основная программа
 Begin
   write('введите количество вершин: ');
   readln(n);
   MakeMatrix(a,n);
   writeln('матрица смежности');
   PrintMatrix(a,n);
   writeln('введите номер пункта начала');
   readln(First);
   writeln('введите номер пункта конца');
   readln(Last);
   SearchWay(first,last,n);
 End.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.06.2014, 21:02
Ответы с готовыми решениями:

В неориентированном графе требуется найти минимальный путь между двумя вершинами
Путь В неориентированном графе требуется найти минимальный путь между ...

поиск паросочетания в графе
добрый вечер! вот это граф который имеет парные вершины. программа должна...

Поиск максимального потока в графе
Прошу напишите код программы для поиска максимального потока в графе на паскале

Поиск в графе в ширину заданном списками инциденций
Добрый день. Пытаюсь написать функцию поиска в ширину в графе, заданным...

Разработайте программу реализующую поиск в ширину в графе из заданной вершины
Лекции пропустил теперь незнаю как написать=( выручайте.. 1.Разработайте...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.06.2014, 21:02

Поиск пути
Первую трассу проводит, при проведении второй выдаёт выход за границы массива...

Алгоритм А* (поиск пути)
Помогите пожалуйста написать алгоритм А*

Поиск кратчайшего пути (алгоритм Уоршала)
В области имеется N городов, соединены автобусными маршрутами. Стоимость билета...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru