Файл: Реферат По теме Применение графов в программировании Студент группы ит21 Кульпина А. В.rtf
Добавлен: 06.12.2023
Просмотров: 28
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
4.2 Реализация алгоритмов поиска в ширину и в глубину в программной среде Turbo Pascal
Задача состоит в том, найти путь из вершины A в вершину B. Будем задавать граф матрицей смежности, т.е. квадратной таблицей NxN, в которой на пересечении i-й строки и j-го столбца значение TRUE, если i и j соединены ребром, и FALSE в противном случае.
Поиск в ширину.
Подобно тому как, согласно принципу Гюйгенса, каждая точка волнового фронта является источником вторичной волны, мы, отправляясь из заданной вершины A, посещаем все смежные с ней вершины (т.е. вершины, в которые ведут стрелки из A). Каждая посещенная вершина становится источником новой волны и т.д. При этом необходимо позаботиться о том, чтобы не вернутся в ту вершину, в которой уже были. Для реализации алгоритма понадобятся: матрица m[1..n, 1..n] - матрица смежности графа; вспомогательный массив queue[1..n], в котором будет формироваться очередь, т.е. тип данных первый вошел – первый вышел (FIFO). Размер его достаточен, так как мы не посещаем вершины дважды. С массивом queue связаны две переменные - head и tail. В переменной head будет находиться номер текущей вершины, из которой идет волна, а при помощи переменной tail новые вершины помещаются в "хвост" очереди queue; вспомогательный массив visited[1..n], который нужен для того, чтобы отмечать уже пройденные вершины (visited[i]=TRUE <=> вершина i пройдена); вспомогательный массив prev[1..n] для хранения пройденных вершин. В этом массиве и будет сформирован искомый путь; переменная f, которая примет значение TRUE, когда путь будет найден. Кроме того, мы введем несколько вспомогательных переменных, которые понадобятся при организации циклов.
Program breadth_first_search;
Const n=9;
m:array[1..n, 1..n] of boolean =
(
(False, True, True, False, False, False, False, False,
False),
(True, False, True, False, False, False, True, True,
False),
(True, True, False, True, True, False, False, False,
False),
(False, False, True, False, True, False, False, False,
False),
(False, False, True, True, False, True, False, True,
False),
(False, False, False, False, True, False, True, True, True
),
(False, True, False, False, False, True, False, True, True
),
(False, True, False, False, True, True, True, False,
False),
(False, False, False, False, False, True, True, False, False)
);
Var A, B: integer;
Procedure A_to_B(A, B: integer);
Var
Visited: array[1..n] of boolean;
Prev: array[1..n] of integer;
c: array[1..n] of integer;
head, tail: integer;
f: boolean;
i, v, k: integer;
Begin
head:=1;
tail:=1;
f:=False;
For i:=1 to n do
Begin
Visited[i]:=False;
Prev[i]:=0
End;
C[tail]:=A;
Visited[A]:=True;
While (head<=tail) and not f do
Begin
v:=C[head];
head:=head+1;
For k:=1 to n do
if m[v, k] and not Visited[k] then
Begin
tail:=tail+1;
C[tail]:=k;
Visited[k]:=True;
Prev[k]:=v;
if k=B then
Begin
f:=true;
break
End
End
End;
if f then
Begin
k:=B;
Write(B);
While Prev[k]<>0 do
Begin
Write('<-', Prev[k]);
k:=Prev[k]
end
End
else
Write('Пути из ', A, ' в ', B, ' нет')
end;
Begin
Write('A= '); readln(A);
Write('B= '); readln(B);
A_to_B(A, B)
End.
Поиск в глубину.
Идея поиска в глубину проста: отправляясь от текущей вершины, мы находим новую (еще не пройденную) смежную с ней вершину, которую помечаем как пройденную и объявляем текущей. После этого процесс возобновляется. Если новой смежной вершины нет (тупик), возвращаемся к той вершине, из которой попали в текущую, и делаем следующую попытку. Если попадем в вершину B, печатаем путь. Если все вершины исчерпаны - такого пути нет. Заметим, что построенный таким образом алгоритм способен находить все пути из A в B, но первый найденный необязательно должен быть кратчайшим. Как обычно, алгоритм с возвратами легче всего оформить с помощью рекурсивной процедуры. Для ее реализации нам понадобятся: матрица m[1..n, 1..n] - матрица смежности графа; вспомогательный массив visited[1..n], который мы будем для того, чтобы отмечать уже пройденные вершины (visited[i]=TRUE <=> вершина i пройдена); переменная f, которая примет значение TRUE, когда путь будет найден.
Program depth_first_search;
Const n=9;
m:array[1..n, 1..n] of boolean =
(
(False, True, True, False, False, False, False, False,
False),
(True, False, True, False, False, False, True, True,
False),
(True, True, False, True, True, False, False, False,
False),
(False, False, True, False, True, False, False, False,
False),
(False, False, True, True, False, True, False, True,
False),
(False, False, False, False, True, False, True, True, True
),
(False, True, False, False, False, True, False, True, True
),
(False, True, False, False, True, True, True, False,
False),
(False, False, False, False, False, True, True, False, False)
);
Var A, B: integer;
Procedure A_to_b(A, B: integer);
Var
Visited: array[1..n] of boolean;
f: boolean;
i: integer;
Procedure Depth(p: integer);
var k: integer;
Begin
Visited[p]:=True;
For k:=1 to n do
If not f then
If m[p, k] and not Visited[k] then
If k=B then
Begin
f:=True;
Write(B);
Break
End
else Depth(k);
If f then write('<=', p);
End;
Begin
For i:=1 to n do Visited[i]:=False;
f:=false;
Depth(A);
If not f then write('Пути из ', A, ' в ', B, ' нет')
End;
Begin
write('A= '); readln(A);
write('B= '); readln(B);
A_to_B(A, B)
End.
Заключение
Курсовой проект выполнен на тему «Графы и их представление на ЭВМ». В нём рассмотрены следующие вопросы:
Определение графов: основное определение, смежность, другие определения;
Способы задания графов: изображение графа, способы численного представления графов, представление ориентированных граф;
Виды графов и операции над ними: элементы графов, изоморфизм графов, тривиальные и полые графы, двудольные графы, направленные орграфы и сети, операции над графами;
Представление графов в ЭВМ: требование к представлению графов, реализация алгоритмов поиска в глубину и ширину в программной среде Turbo Pascal;
На основании найденной информации (учебная литература, Internet), я выделил основные пункты, которые наиболее полно и точно дают представление о графах и их представлении на ЭВМ. При выполнении работы были приведены примеры графов, а также различные способы их задания и представлены на основании заданных графов соответствующие им матрицы смежности и инцидентности. Были исследованы свойства операций над графами и к некоторым их них составлены графические изображения. В последней главе необходимо было указать на связь между графами и их представлением на ЭВМ, особенно это важно, на мой взгляд, для специальности математика-программиста.
После проделанной работы можно сделать следующий вывод:
Графы широко используются как в самой математике, так и в ее приложениях. Они применяются при построении различных математических моделей: линий электропередачи, сетей автодорог, линий воздушных сообщений и пр.
Список использованной литературы
-
Дискретная математика для программистов / Ф.А.Новиков. – СПб.: Питер, 2002. – 304 с. -
Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002. – 280 с. – (Серия «Высшее образование»)