Курсовая работа: Графы и их представление на ЭВМ
3. Списки смежности.
Представление графа с помощью списочной структуры, отражающей смежность вершин и
состоящей из массива указателей Г : array [1..р] оf N на списки смежных вершин
(элемент списка представлен структурой N : record v: 1..р; п :
N endrecord), называется списком смежности. В случае представления неориентированных
графов списками смежности п(р, q) = О(р + 2q), а в случае ориентированных
графов п(р, q) = О(р + q).
4. Массив дуг.
Представление графа с помощью массива структур Е : array [1..р] of record b,e : 1..p endrecord, отражающего список пар смежных
вершин, называется мас сивом ребер (или, для орграфов, массивом дуг).
Для массива ребер (или дуг) п(р, q) = О( 2q).
5. Обход графа
— это некоторое систематическое перечисление его вершин (и/или ребер). Наибольший
интерес представляют обходы, использующие локальную информацию (списки смежности).
Среди всех обходов наиболее известны поиск в ширину и в глубину. Алгоритмы поиска
в ширину и в глубину лежат в основе многих конкретных алгоритмов на графах.
ТЕОРЕМА Если граф G связен (и конечен), то поиск
в ширину и поиск в глубину обойдут все вершины по одному разу.
Доказательство
1. Единственность
обхода вершины. Обходятся только вершины, попавшие в Т. В Т попадают
только неотмеченные вершины. При попадании в Т вершина отмечается. Следовательно,
любая вершина будет обойдена не более одного раза.
2. Завершаемость алгоритма. Всего в Т может
попасть не более р вершин. На каждом шаге одна вершина удаляется из Т.
Следовательно, алгоритм завершит работу не более чем через р шагов.
3. Обход всех вершин. От противного. Пусть алгоритм
закончил работу, и вер шина w не обойдена. Значит, w не попала в Т. Следовательно,
она не былаотмечена. Отсюда следует, что все вершины, смежные с w, не были обойденыи отмечены.
Аналогично, любые вершины, смежные с неотмеченными, самине отмечены (после завершения
алгоритма). Но G связен, значит, существуетпуть (v,w). Следовательно, вершина v не отмечена. Но она была отмечена
напервом шаге.
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), я выделил основные пункты, которые наиболее полно
и точно дают представление о графах и их представлении на ЭВМ. При выполнении работы
были приведены примеры графов, а также различные способы их задания и представлены
на основании заданных графов соответствующие им матрицы смежности и инцидентности.
Были исследованы свойства операций над графами и к некоторым их них составлены графические
изображения. В последней главе необходимо было указать на связь между графами и
их представлением на ЭВМ, особенно это важно, на мой взгляд, для специальности математика-программиста.
После проделанной
работы можно сделать следующий вывод:
Графы широко используются
как в самой математике, так и в ее приложениях. Они применяются при построении различных
математических моделей: линий электропередачи, сетей автодорог, линий воздушных
сообщений и пр.
Список использованной
литературы
1.
Дискретная
математика для программистов / Ф.А.Новиков. – СПб.: Питер, 2002. – 304 с.
2.
Судоплатов
С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск:
Изд-во НГТУ, 2002. – 280 с. – (Серия «Высшее образование»)
Страницы: 1, 2, 3, 4, 5, 6 |