Форум программистов, компьютерный форум, киберфорум
Free Pascal
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/30: Рейтинг темы: голосов - 30, средняя оценка - 5.00
8 / 8 / 5
Регистрация: 27.10.2013
Сообщений: 170
1

Графы-Поиск в ширину

22.11.2013, 13:53. Показов 5499. Ответов 4
Метки нет (Все метки)

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

Формат входных данных
Первым на вход поступает число N – количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной.

Формат выходных данных
Выведите сначала L – длину кратчайшего пути (количество ребер, которые нужно пройти), а затем L + 1 число – путь от одной вершины до другой, заданный своими вершинами. Если пути не существует, выведите одно число –1.

Пример:

Входные данные:
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5


Выходные данные:
3
3 2 1 5



Есть наработки с учителем, но все равно не догоняю как все должно работать.

Вот собственного сама программа, но в ней присутствуют ошибки. Не могли бы вы объяснить как это все работать должно.

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
const
   l = 1000;
 
var i,j,n, consp,cur,st,fin : integer;       way,q: array[1..l] of integer;
                                                      was: array[1..l] of integer;
                                                      m: array[1..100] of array[1..100] of integer;
                                                      pred: array[1..l] of integer;
    b,e: integer;
 
 
 
 
procedure add(var i:integer);
begin
 if i < l then i:=i+1  else   i:=1;
end;
 
 
 
 
begin
For i:=1 to l do
  begin
  was[i]:=0;
  q[i]:=0;
  end;
 
readln(n);
 
 For i:=1 to n do
    For j:=1 to n do
       read(m[i,j]);
 
read(st,fin);
 
b:=1;
e:=b+1;
q[b]:=st;
 
while (cur<>fin) do
begin
 cur:=q[b];
 add(b);
 was[cur]:=1;
 
 if (b<>e) and (cur <> fin) then
 begin
 
   For i:=1 to n do
     if ((m[i,cur]=1)  and (was[i]=0))  then
     begin
      add(e);
      q[e]:=i;
      pred[i]:=cur;
     end;
 end;
end;
 
i:=1;
way[1]:=fin;
while (cur <> st) do
begin
 way[i]:=cur;
 inc(i);
 cur:=pred[cur];
end;
 
For i:=1 to i do
  write(way[i]);
 
 
 
readln;
readln;
end.
Что бы не было лишних вопросов, was-запоминаем были ли тут; m - сама матрица смежности; st- от него начинается цикл; fin - final..заканчивается;
Блин вот убейте не помню для чего нужен массив q.


P.S. Заранее буду благодарен.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.11.2013, 13:53
Ответы с готовыми решениями:

Графы. Поиск путей. Алгоритм Йена
Помогите написать программу с алгоритмом Йена поиска путей в графе.

поиск в ширину
мне надо написать программу для курсовая работа. думаю ни кто не напишет программу так бесплатно....

Графы: поиск в ширину, поиск вершины с максимальной степенью
Дан граф. Способ представления и метод обхода равен список смежности;поиск в ширину....

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

4
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
32835 / 21172 / 8148
Регистрация: 22.10.2011
Сообщений: 36,432
Записей в блоге: 8
22.11.2013, 16:28 2
Лучший ответ Сообщение было отмечено volvo как решение

Решение

Пишем вот такие 2 подпрограммы:

Pascal
1
2
3
4
5
6
7
8
9
procedure push(var i:integer; v : integer);
begin
 if i < l then i:=i+1; // else i:=1; Это переполнение очереди, надо бы ошибку обработать
 q[i] := v;
end;
function pop(var i:integer) : integer;
begin
  pop := q[i]; dec(i);
end;
, и само решение будет выглядеть так:

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
   // тут ввод данных
   read(st,fin); // Это у тебя было
 
   b := 0;
   push(b, st);
   was[st] := 1;
 
   while b > 0 do
   begin
     e := pop(b);
     if e = fin then break;
     for i := 1 to n do
       if (m[e, i] = 1) and (was[i] = 0) then
       begin
         push(b, i);
         was[i] := 1;
         pred[i] := e;
       end;
   end;
 
   i:=1;
   cur := fin;
   while (cur <> st) do
   begin
      way[i]:=cur;
      inc(i);
      cur:=pred[cur];
   end;
   way[i]:=st;
 
   For j:= i downto 1 do
      write(way[j]:3);
Строго по алгоритму BFS, заметь...
1
8 / 8 / 5
Регистрация: 27.10.2013
Сообщений: 170
22.11.2013, 19:20  [ТС] 3
А можно как нибудь объяснить этот алгоритм?
0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
32835 / 21172 / 8148
Регистрация: 22.10.2011
Сообщений: 36,432
Записей в блоге: 8
22.11.2013, 19:27 4
http://ru.wikipedia.org/wiki/%... 0%BD%D1%83 там есть и неформальное и формальное описание.
0
18 / 11 / 5
Регистрация: 27.05.2013
Сообщений: 36
22.11.2013, 22:34 5
Mikky Lova, массив q (я так понимаю, это первая буква английского слова queue - очередь) нужен для того, чтобы реализовать алгоритм поиска в ширину. Мы рассматриваем вершину, и добавляем все связанные с ней в очередь. А потом делаем то же самое для следующей вершины в очереди.
0
22.11.2013, 22:34
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.11.2013, 22:34
Помогаю со студенческими работами здесь

Обход в ширину (графы)
Нужно решить следующую задачу на Python: В неориентированном графе требуется найти длину...

Графы, обход вершин в ширину и глубину
Граф задан матрицей смежности. Изобразить граф и два его подграфа, получаемые обходом его вершин...

Графы, нахождение наименьшего пути между вершинами обходом в ширину
Здравствуйте, помогите пожалуйста, нужно по заданной матрице смежности графа определить наименьший...

Графы. Метод, отличающийся от поиска в ширину тем, что вновь достигнутая вершина помещается не в очередь, а в стек
Прошу помочь с Графами по поиску в глубину.... Задача такая: Напишите и используйте в программе...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru