Навигация
Представление графов в ЭВМ
28460
знаков
7
таблиц
5
изображений
4. Представление графов в ЭВМ
Следует еще раз подчеркнуть, что конструирование структур данных для представления в программе объектов математической модели — это основа искусства практического программирования. Используется четыре различных базовых представления графов. Выбор наилучшего представления определяется требованиями конкретной задачи. Более того, при решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений, общее число которых необозримо. Но все они, так или иначе, основаны на тех базовых идеях, которые описаны в этом разделе.
4.1 Требования к представлению графов
Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления с указанием характеристики п(р, q) — объема памяти для каждого представления. Здесь р - число вершин, а q - число ребер. Указанные представления пригодны для графов и орграфов, а после некоторой модификации также и для псевдографов, мультиграфов и гиперграфов.
1. Матрица смежности. Представление граф с помощью квадратной булевской матрицы, отражающей смежность вершин, называется матрицей смежности,
M : array [1..p, 1..p] of 0..1,
M [i, j] = 1, если вершина vi смежна с вершиной vj
0, если вершины не vi и vj смежны.
Для матрицы смежности п(р, q) = O(p2).
2. Матрица инциденций. Представление графа с помощью матрицы H : array [1..p, 1..q] of 0..1 (для орграфов H : array [1..p, 1..q] of -1..1), отражающей инцидентность вершин и рёбер, называется матрицей инциденций, где для неориентированного графа
H [i, j] = 1, если вершина vi инцидентна ребру ej,
0, в противном случае.
а для ориентированного графа
1, если вершина vi инцидентна ребру ej и является его концом,
H [i, j] = 0, если вершина vi и ребро ej не инцидентны,
-1, если вершина vi инцидентна ребру ej и является его началом
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 с. – (Серия «Высшее образование»)
3. Материал из Википедии — свободной энциклопедии. Элементы теории граф (http://referats/mat_graph);
4. Элементы теории граф (http://book.itep.ru/10/graph1021.htm).
Похожие работы
... , "базовые" алгоритмы: поиск путей, определение компонент связности графа и т.д. 8. Ввод/вывод графов Одной из проблем при создании средств работы с помеченными графами является выбор внешнего файлового формата для хранения графов. До недавнего времени каждая программная система использовала свой собственный, уникальный формат, что приводило к сложностям при организации обмена данными. ...
... write(fileKlics,klika); end; end; end; {конец пеpебоpа возможных мест в стpоке} end; {конец пpохода по стpокам} close(fileklics); end; Выше представлена процедура нахождения клик в графе. Описание переменных: StolbecSravn: номер сравниваемого столбца. StringSravn: номер текущей строки. Num ,i1,i: счетчики. lenStolb: размер множества вершин клики. Stolbec: номер столбца первой ...
... . Вся процедура поиска представлена ниже (данная процедура используется также и для просмотра графа, и в псевдокоде, описанном ниже, отсутствуют операторы, которые не используются для поиска). 1 procedure WS (v); (*поиск в ширину в графе с началом в вершине v; переменные НОВЫЙ, ЗАПИСЬ — глобальные *) 2 begin 3 ОЧЕРЕДЬ := Æ; ОЧЕРЕДЬ <= v; НОВЫЙ [v] := ложь 4 while ОЧЕРЕДЬ &# ...
... файла из которого будет происходить ввод X – грав в последовательном представлении O(N,N1)=N2 N2 – количество вершин в графе X Текст программы. # include # include # include # include # include # include /////////////////////////////////////////////////////////////////////////////////////////////////////// struct Spisok //Связанное представление графа { int index; //Содержвтельная " ...
0 комментариев