Файл: Реферат По теме Применение графов в программировании Студент группы ит21 Кульпина А. В.rtf
Добавлен: 06.12.2023
Просмотров: 140
Скачиваний: 5
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
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);VarVisited: 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;Beginhead:=1;tail:=1;f:=False;For i:=1 to n doBeginVisited[i]:=False;Prev[i]:=0End;C[tail]:=A;Visited[A]:=True;While (head<=tail) and not f doBegin
v:=C[head];head:=head+1;For k:=1 to n doif m[v, k] and not Visited[k] thenBegintail:=tail+1;C[tail]:=k;Visited[k]:=True;Prev[k]:=v;if k=B thenBeginf:=true;breakEndEndEnd;if f thenBegink:=B;Write(B);While Prev[k]<>0 doBeginWrite('<-', Prev[k]);k:=Prev[k]endEndelseWrite('Пути из ', A, ' в ', B, ' нет')end;BeginWrite('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);VarVisited: array[1..n] of boolean;f: boolean;i: integer;Procedure Depth(p: integer);var k: integer;BeginVisited[p]:=True;For k:=1 to n doIf not f thenIf m[p, k] and not Visited[k] thenIf k=B thenBeginf:=True;Write(B);BreakEndelse Depth(k);If f then write('<=', p);End;BeginFor i:=1 to n do Visited[i]:=False;f:=false;Depth(A);If not f then write('Пути из ', A, ' в ', B, ' нет')End;Beginwrite('A= '); readln(A);write('B= '); readln(B);A_to_B(A, B)End.ЗаключениеКурсовой проект выполнен на тему «Графы и их представление на ЭВМ». В нём рассмотрены следующие вопросы:Определение графов: основное определение, смежность, другие определения;Способы задания графов: изображение графа, способы численного представления графов, представление ориентированных граф;
Виды графов и операции над ними: элементы графов, изоморфизм графов, тривиальные и полые графы, двудольные графы, направленные орграфы и сети, операции над графами;Представление графов в ЭВМ: требование к представлению графов, реализация алгоритмов поиска в глубину и ширину в программной среде Turbo Pascal;На основании найденной информации (учебная литература, Internet), я выделил основные пункты, которые наиболее полно и точно дают представление о графах и их представлении на ЭВМ. При выполнении работы были приведены примеры графов, а также различные способы их задания и представлены на основании заданных графов соответствующие им матрицы смежности и инцидентности. Были исследованы свойства операций над графами и к некоторым их них составлены графические изображения. В последней главе необходимо было указать на связь между графами и их представлением на ЭВМ, особенно это важно, на мой взгляд, для специальности математика-программиста.После проделанной работы можно сделать следующий вывод:Графы широко используются как в самой математике, так и в ее приложениях. Они применяются при построении различных математических моделей: линий электропередачи, сетей автодорог, линий воздушных сообщений и пр.Список использованной литературы
v:=C[head];head:=head+1;For k:=1 to n doif m[v, k] and not Visited[k] thenBegintail:=tail+1;C[tail]:=k;Visited[k]:=True;Prev[k]:=v;if k=B thenBeginf:=true;breakEndEndEnd;if f thenBegink:=B;Write(B);While Prev[k]<>0 doBeginWrite('<-', Prev[k]);k:=Prev[k]endEndelseWrite('Пути из ', A, ' в ', B, ' нет')end;BeginWrite('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);VarVisited: array[1..n] of boolean;f: boolean;i: integer;Procedure Depth(p: integer);var k: integer;BeginVisited[p]:=True;For k:=1 to n doIf not f thenIf m[p, k] and not Visited[k] thenIf k=B thenBeginf:=True;Write(B);BreakEndelse Depth(k);If f then write('<=', p);End;BeginFor i:=1 to n do Visited[i]:=False;f:=false;Depth(A);If not f then write('Пути из ', A, ' в ', B, ' нет')End;Beginwrite('A= '); readln(A);write('B= '); readln(B);A_to_B(A, B)End.ЗаключениеКурсовой проект выполнен на тему «Графы и их представление на ЭВМ». В нём рассмотрены следующие вопросы:Определение графов: основное определение, смежность, другие определения;Способы задания графов: изображение графа, способы численного представления графов, представление ориентированных граф;
Виды графов и операции над ними: элементы графов, изоморфизм графов, тривиальные и полые графы, двудольные графы, направленные орграфы и сети, операции над графами;Представление графов в ЭВМ: требование к представлению графов, реализация алгоритмов поиска в глубину и ширину в программной среде Turbo Pascal;На основании найденной информации (учебная литература, Internet), я выделил основные пункты, которые наиболее полно и точно дают представление о графах и их представлении на ЭВМ. При выполнении работы были приведены примеры графов, а также различные способы их задания и представлены на основании заданных графов соответствующие им матрицы смежности и инцидентности. Были исследованы свойства операций над графами и к некоторым их них составлены графические изображения. В последней главе необходимо было указать на связь между графами и их представлением на ЭВМ, особенно это важно, на мой взгляд, для специальности математика-программиста.После проделанной работы можно сделать следующий вывод:Графы широко используются как в самой математике, так и в ее приложениях. Они применяются при построении различных математических моделей: линий электропередачи, сетей автодорог, линий воздушных сообщений и пр.Список использованной литературы
-
Дискретная математика для программистов / Ф.А.Новиков. – СПб.: Питер, 2002. – 304 с. -
Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002. – 280 с. – (Серия «Высшее образование»)