ГРАФЫ.
На алгоритмах теории графов основаны оптимальные решения многочисленных задач.
В данном разделе приведены лишь начальные алгоритмы: поиска в ширину, глубину и Дейкстры.
7. 1 ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ.
Граф – математическая структура, применяемая в программировании при исследовании СВЯЗЕЙ МЕЖДУ ОБЪЕКТАМИ. Графы удобно рисовать, “изображать графически” – отсюда и их название.
Объект - это вершина. Ребра и дуги – связи между объектами.
ПРИМЕР задачи, решаемой с помощью графов:
На олимпиаду прибыло N человек. Некоторые из них знакомы между собой. Можно ли опосредованно перезнакомить их всех между собой?
(Незнакомые люди могут познакомиться только через общего знакомого).
ОПРЕДЕЛЕНИЕ:
Граф - абстрактное представление любой системы объектов, которая описана парой (V,E), где V – конечное множество т.н. узлов или вершин (объектов), а Е – множество ребер (дуг), соединяющих все или некоторые из вершин. На рисунках вершины обозначаются номерами, а ребра и дуги - простыми или направленными линиями.
СЛОВАРЬ ТЕРМИНОВ:
Каждая дуга соединяет две вершины, которые называются ее началом и концом. Дуга направлена от начала к концу. Если у дуги начало и конец совпадают, то она называется петлей.
Полный граф – граф без петель, в котором любые две различные вершины соединены ровно одной дугой (если любая пара U,W –ребро). В полном графе число ребер равно (N*N-N)/2, где N – число вершин.
Если выкинуть из графа несколько дуг, то его называют частичным графом.
Если выкинуть некоторые вершины и дуги, оставшиеся без начала и конца, то получим подграф (подмножество вершин графа и все соединяющие их ребра).
Если выкинем еще несколько дуг, то получим частичный подграф.
|
|
 | |||||
 |  | ||||
 | |||||
 | |||||
 | |||||
ГРАФ ПОДГРАФ ЧАСТИЧНЫЙ ГРАФ
Ребро (I,J) обозначает связь вершин I и J, которые называются смежными, а ребро – инцидентным им.
Дуга - ребро в ориентированном графе, обозначающее направление связи вершин.
Все дуги, входящие в вершину, образуют входящую звезду, выходящие – исходящую звезду, а все вместе - звезду вершины.
Степень вершины - это число инцидентных ей ребер (сумма количества дуг во входящей и выходящей звездах). Сумма степеней всех вершин в графе должна делиться на 2, иначе количество дуг получилось бы дробным.
Граф считается ориентированным, если задано множество упорядоченных ребер.
В разреженном (неориентированном) графе число ребер намного меньше.
Маршрут между Z и W – это последовательность вершин (и ребер), соединяющих Z и W.
Цепь – маршрут без повторения ребер.
Граф связен, если для любой пары вершин есть соединяющая цепь.
Компонента связности – максимальный связный подграф.
Цикл – замкнутый маршрут (конец маршрута совпадает с его началом).
Простой цикл – замкнутая цепь (конец цепи совпадает с началом).
Дерево - произвольный неориентированный граф без циклов.
Путь в ориентированном графе последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Простой путь - это путь, в котором каждая дуга используется не более одного раза.
Элементарный путь – это путь, в котором каждая вершина используется не более одного раза.
|
|
7.2 СПОСОБЫОПИСАНИЯ ГРАФОВ:
7.2.1 матрица смежности.
Данный способ удобен для небольших графов и графов с весами в небольших типах данных. Недостаток данного способа – требуется очень много памяти для хранения матрицы (например, матрица 10000*10000 типа longint занимает очень много памяти!).
Для создания матрицы смежности для графа с N вершинами затрачивается минимум N*N байт.
Матрица смежности - это двумерный массив А размерности N*N.
A[i,j] = [ 1, если вершины i и j смежны
[ 0, если вершины i и j не смежны
Рассмотрим экономный способ отображения матрицы смежности.
Представим каждую I-тую строку матрицы смежности множеством (Bуtе) номеров ее позиций, содержащих “1” (номера вершин, смежных с I-той вершиной).
const
N=5;
type
Mno=set of 1..N;
var
J,K: byte;
A:array[1..N] of Mno; {Массив из N множеств}
begin
for J:=1 to N do
A[j]:=[]; {Исходные пустые множества}
WriteLn(‘Ввод для каждой J вершины номера K смежных с нею’);
WriteLn(‘вершин (только те, которые больше J), заканчивая’);
WriteLn (‘перечень номеров вводом нуля и нажатием Еnter’);
for J:=1 to N-1 do
begin
Write(J,’-я вершина связна с ’);
repeat
Read (K); {К- номер вершины, смежной с J}
if K<>0 then
if K<J then
WriteLn (‘Нужен номер больший J’)
else
A[J]:=A[J]+[K]; A[K]:=A[K]+[J]
until K=0
end;
for K:=1 To N do
begin
WriteLn;
{Контрольный вывод матрицы}
for K:=1 to N do
if K in A[J] then
Write (‘1 ‘)
else
Write (‘0 ‘);
end;
ReadLn;
ReadLn;
end.
7.2.2 ПЕРЕЧЕНЬ РЕБЕР
Для хранения перечня N ребер необходим массив R размерности N*2. Каждая строка массива описывает одно ребро.
R[i]=[start,finish]- начальная и конечная вершины.
7.2.3 СПИСОК СМЕЖНЫХ ВЕРШИН
|
|
Данный способ удобен для хранения графов с весами, в котором каждому ребру приписан некоторый вещественный «вес» (расстояние между вершинами, стоимость проезда и т.п.), т.е. задана весовая функция. В этом случае удобно хранить вес ребра (u,v) вместе с вершиной V в списке вершин, смежных с U.
Недостаток способа – для нахождения ребра из U в V нужно просматривать весь F(V).
Описание данных и процедура создания списковой структуры для представления графа:
Const max_graf=100;
Type list=^elem;
Elem=record
Num: integer;
Next: list;
End;
Var
Graf: array[1..max_graf] of elem;
Procedure CreateGraf(n:integer);
{n- число вершин графа}
Var a: integer;
Sosed,sosed1:list;
Begin
For i:=1 to n do {для каждой вершины}
Begin
New(sosed); {выделили память для нового элемента}
Graf[i].next:=sosed; {ссылка на новый элемент}
Writeln (‘для нового элемента ’,i,’введите номер очередного соседа или 0’);
Repeat
Readln(a);
Sosed^.num:=a; {указатель на очередного сеседа}
If a<>0 then
Begin
New(sosed1);
Sosed^.next:=sosed1;
Sosed:=sosed1;
End;
Until a=0 {больше соседей нет}
End;
End;
Массив F[1…N] (N – число вершин) массив списков. Для каждой из N вершин список содержит смежные ей вершины в произвольном порядке (указатели «на»)
Для ориентированного и неориентированного графа количество требуемой памяти равно V+2*E (число вершин + число ребер).
7.3 ПОНЯТИЕ ДОСТИЖИМОСТИ.
Если существует путь из вершины V в вершину U, то говорят, что U достижима из V.
Матрицу достижимости R определим следующим образом:
[1, если u достижима из v
R[v,u] =[ 0, в противном случае.
Множество R(v) – это множество таких вершин графа G, каждая из которых может быть достигнута из вершины V.
Пусть Г(v) – множество таких вершин графа G, которые достижимы из V с использованием путей длины 1.
Г2(v)- множество вершин, достижимых из V с использованием путей длины 2 и так далее. Тогда: R(v)={v} + Г(v) +Г2(v) +…. + ГN(v) Для графа на рисунке 2:
R(1) = {1} + {2,5} + {6} + {4} + {7} = {1,2,4,5,6,7}
2 1
3
5
рис. 2 6 4
7 8
Процедура Reach формирует матрицу достижимости:
procedure Reach; {матрица R - глобальная переменная}
var S,T: set of 1...N;
i,j,l: integer;
begin
Fillchar (R,Sizeof (R),O);
For i:=1 to N do
begin {ищем вершины, достижимые из вершины с номером i }
T:=[i];
Repeat
S:=T;
For l:=1 to N do
If l in S then
For J:=1 to N do
If A[l,j] =1 Then T:=T+[j];
Until S=t; { если Т не изменилось, то найдены все вершины графы, достижимые из вершины с номером I}
For J:=1 To N do
If J in T then R[i,j]:=1;
end;
end;
7.4 ПОИСКИ КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ.
К поиску кратчайших путей в графе относятся следующие задачи: найти наименьший по протяженности (стоимости, «пересадочности» и т.д.) путь в графе от вершины I к вершине J.
Рассмотрим некоторые оптимальные алгоритмы поиска.
7.4.1 ПОИСК В ГЛУБИНУ
Название основано на поиске «вглубь», пока это возможно (есть непройденные исходящие ребра), и возвращаться и искать другой путь, когда таких ребер нет.
Алгоритм метода:
Просмотр вершин графа начинается с некоторой фиксированной вершины V. Выбирается вершина U, смежная с V. Процесс повторяется с вершины U. Если на очередном шаге мы работаем с вершиной q и нет вершин, смежных c q и не просмотренных ранее (новых), то возвращаемся из вершины q к вершине, из которой мы попали в q. Если это вершина V, то просмотр закончен. Для фиксации признака, просмотрена вершина графа или нет, требуется структура данных типа:
Nnew: array[1..N] of Boolean
Пример:
Пусть граф описан матрицей смежности А. Просмотр начинается с первой вершины.
На рисунке 3А показан исходный граф, а на рисунке 3Б указана та очередность, в которой вершины графа просматривались в процессе поиска в глубину: 
Рис.3А Рис.3Б
Реализация рекурсивного алгоритма:
{Массивы Nnew и A - глобальные}
procedure Pg (V: integer); {поиск в глубину}
Var j: integer;
Begin
Nnew [v]:=false; {нет пути из вершины V}
Write(V:3);
For j:=1 To N Do {для всех вершин от 1 до N – проверка наличия пути }
If (A[v,j]<>0) And Nnew[j] Then Pg(j) {идти от вершины, из которой есть путь}
End;
Фрагмент вызывающего алгоритма:
Fillchar (Nnew, SizeOf (Nnew), True);
For i:=1 To N Do
If Nnew[i] Then Pg(i);
Реализация данного алгоритма без рекурсий:
uses crt;
const max=10;
var is:array[1..max]of boolean; {Была ли вершина}
i,j,n:word;
a:array[1..max,1..max]of byte; {Матрица смежности}
procedure pg(i:word);
var m:array[1..max]of word;j,k:word; {Массив предыдущих}
begin
m[i]:=0;
j:=i;
while j<>0 do {Если не обошли всю компоненту…}
begin
is[j]:=false; {Были}
write(j,',');
for k:=1 to n do
if is[k] and (a[j,k]<>0) then break; {Ищем соседа}
if is[k] and (a[j,k]<>0) then {Сосед есть…}
begin
m[k]:=j; {Ставим ему предшественника}
j:=k; {Переходим в него}
end
else
j:=m[j]; {Возвращаемся назад}
end;
end;
begin
fillchar(is,sizeof(is),true);
clrscr;
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
write('a[',i,',',j,']=');
readln(a[i,j]);
end;
readkey;
clrscr;
for i:=1 to n do
if is[i] then
begin
pg(i);
gotoxy(wherex-1,wherey);
write(' ');
writeln;
end;
readkey;
end.
7.4.2 ПОИСК В ШИРИНУ.
Название метода объясняется тем, что поиск ведется вширь – сначала просматриваются все соседние вершины, затем соседи соседей и т.д.
Алгоритм метода:
Пусть задан граф и зафиксирована начальная вершина. Алгоритм перечисляет все вершины, достижимые из начальной в порядке возрастания расстояния (числа ребер) от начальной вершины. В процессе поиска из графа выделяется часть, называемая «деревом поиска в ширину» с корнем в начальной вершине. Для каждой из них путь из корня в дереве поиска будет одним из кратчайших путей (из начальной вершины) в графе.
Алгоритм применим и к ориентированным, и к неориентированным графам.
Рис. 4 Рис. 4А
На рисунке 4А в скобках указана очередность их просмотра.
Процедура реализации метода:
Procedure PW (v: integer);
Var Og:array[1..N] of 0..N: {очередь}
Yk1, Yk2: integer; {указатели очереди, Yk1-запись, Yk2 – чтение}
J: integer;
Begin
Fillchar(Og, Sizeof(Og),O); Yk1:=0; Yk2:=0[s1]; {начальная инициализация}
Inc(Yk1); Og[Yk1]:= v; Nnew [v]:=false;
{в очередь – вершину v }
While Yk2<Yk1 Do { пока очередь не пуста}
Begin
Inc (Yk2); v:=Og[Yk2]; write(v:3);
{берем элемент из очереди}
For J:=1 To N Do {просмотр всех вершин, связанных с v}
If (A[v,j] <>0) And Nnew [j] Then
Begin {если вершина ранее не просмотрена}
Inc (Yk1); Og[Yk1]:=J; Nnew [ J]:=false;
{заносим ее в очередь}
End;
End;
End;
Время работы алгоритма:
Время работы алгоритма равно квадрату числа вершин.
7.4.3 ВОЛНОВОЙ АЛГОРИТМ
(кратчайшее расстояние от начальной вершины до любой вершины)
1 ВАРИАНТ
Задача
Лабиринт.
Попав в лабиринт, состоящий из одинаковых квадратных комнат, каждая из которых имеет от 1 до 4 дверей в соседние комнаты, путник долго блуждал по нему, пока не нашёл клад. Во время поиска он составил описание своего маршрута, обозначая каждый переход из комнаты в комнату буквами: С(север), В(восток), Ю(юг), З(запад).
Опишите алгоритм, определяющий по заданной записи самый короткий путь назад.
Решение:
Подходящей структурой данных для представления информации о лабиринте является квадратная таблица L, каждая клетка которой соответствует комнате. Размеры таблицы можно установить заведомо большими лабиринта, для чего достаточно подсчитать количество букв в исходной записи переходов. Значение L(i,j) следует устанавливать так, чтобы по нему можно было определить возможные переходы в соседние комнаты, например, в виде четырёхразрядного двоичного числа, где первый разряд равен 1, если из комнаты (i,j) возможен переход на север, второй разряд соответствует переходу на юг, третий - на запад, а четвёртый - на восток. Вход в лабиринт находится в некоторой клетке (i0,j0).
Алгоритм проведём в два этапа. На первом этапе занесём в нашу таблицу всю информацию о лабиринте, которая содержится в записи переходов путника. На втором этапе найдём кратчайший путь, ведущий из конечной клетки маршрута в начальную. Для этого применим так называемый волновой алгоритм, состоящий из прямого и обратного ходов. Во время прямого хода просматриваются комнаты, достижимые от входа за 1 шаг, за 2 шага и т.д. Во время обратного хода строится кротчайший путь, ведущий назад.
Первый этап
Установим 0 во все значения L(i,j).
Установим текущее положение в лабиринте i:=i0, j:=j0.
НЦ пока есть символы в записи
читаем очередной символ S
ЕСЛИ S="C", то
устанавливаем 1 в первый разряд L(i,j),
устанавливаем 1 во второй разряд L(i+1, j) (считаем, что переход через дверь возможен в обе стороны),
меняем текущее положение i:=i+1;
ЕСЛИ S="Ю", то
устанавливаем 1 во второй разряд L(i,j),
устанавливаем 1 в первый разряд L(i-1,j),
меняем текущее положение i:=i-1;
ЕСЛИ S="3", то
устанавливаем 1 в третий разряд L(i,j),
устанавливаем 1 во четвёртый разряд L(i,j+1),
меняем текущее положение j:=j+1;
ЕСЛИ S="В", то
устанавливаем 1 в четвёртый разряд L(i,j),
устанавливаем 1 во третий разряд L(i,j-1),
меняем текущее положение j:=j-1;
КЦ
Запоминаем ik:=i и jk:=j - координаты комнаты с кладом.
Второй этап