LINEBURG


<< Пред. стр.

страница 8
(всего 10)

ОГЛАВЛЕНИЕ

След. стр. >>

те, у которых не хватит припасов на восхождение и обратный путь,
возвращаются назад. Скорость движения одинакова на любом отрезке пути,
привал – один в день пути. Составить программу и тесты.


§7. ГРАФЫ
На алгоритмах теории графов основаны оптимальные решения
многочисленных задач.
В данном разделе приведены лишь начальные алгоритмы: поиска в
ширину, глубину и Дейкстры.


7.1 ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ
Граф – математическая структура, применяемая в программировании
при исследовании СВЯЗЕЙ МЕЖДУ ОБЪЕКТАМИ. Графы удобно рисовать,
“изображать графически” – отсюда и их название.
Объект - это вершина. Ребра и дуги – связи между объектами.

ПРИМЕР задачи, решаемой с помощью графов:
На олимпиаду прибыло N человек. Некоторые из них знакомы между
собой. Можно ли опосредованно перезнакомить их всех между собой?
(Незнакомые люди могут познакомиться только через общего
знакомого).
ОПРЕДЕЛЕНИЕ:
Граф - абстрактное представление любой системы объектов, которая описана
парой (V,E), где V – конечное множество т.н. узлов или вершин (объектов), а Е –
множество ребер (дуг), соединяющих все или некоторые из вершин. На рисунках
вершины обозначаются номерами, а ребра и дуги - простыми или направленными
линиями.
65
СЛОВАРЬ ТЕРМИНОВ
Каждая дуга соединяет две вершины, которые называются ее началом
и концом. Дуга направлена от начала к концу. Если у дуги начало и конец
совпадают, то она называется петлей.
Полный граф – граф без петель, в котором любые две различные
вершины соединены ровно одной дугой (если любая пара U,W –ребро). В
полном графе число ребер равно (N*N-N)/2, где N – число вершин.
Если выкинуть из графа несколько дуг, то его называют частичным
графом.
Если выкинуть некоторые вершины и дуги, оставшиеся без начала и
конца, то получим подграф (подмножество вершин графа и все соединяющие
их ребра).
Если выкинем еще несколько дуг, то получим частичный подграф.




ПОДГРАФ
ГРАФ ЧАСТИЧНЫЙ ГРАФ
Ф
Ребро (I,J) обозначает связь вершин I и J, которые называются
смежными, а ребро – инцидентным им.
Дуга - ребро в ориентированном графе, обозначающее направление
связи вершин.
Все дуги, входящие в вершину, образуют входящую звезду,
выходящие – исходящую звезду, а все вместе - звезду вершины.
Степень вершины - это число инцидентных ей ребер (сумма
количества дуг во входящей и выходящей звездах). Сумма степеней всех
вершин в графе должна делиться на 2, иначе количество дуг получилось бы
дробным.
Граф считается ориентированным, если задано множество
упорядоченных ребер. В разреженном (неориентированном) графе число
ребер намного меньше.
Маршрут между Z и W – это последовательность вершин (и ребер),
соединяющих Z и W.
Цепь – маршрут без повторения ребер. Граф связен, если для любой
пары вершин есть соединяющая цепь.
Компонента связности – максимальный связный подграф.
Цикл – замкнутый маршрут (конец маршрута совпадает с его началом).
Простой цикл – замкнутая цепь (конец цепи совпадает с началом).
Дерево - произвольный неориентированный граф без циклов.
66
Путь в ориентированном графе последовательность дуг, в которой конечная
вершина всякой дуги, отличной от последней, является начальной вершиной
следующей.
Простой путь - это путь, в котором каждая дуга используется не более одного
раза.
Элементарный путь – это путь, в котором каждая вершина используется не
более одного раза.


7.2 СПОСОБЫ ОПИСАНИЯ ГРАФОВ:
7.2.1 МАТРИЦА СМЕЖНОСТИ.
Данный способ удобен для небольших графов и графов с весами в
небольших типах данных. Недостаток данного способа – требуется очень
много памяти для хранения матрицы (например, матрица 10000*10000 типа
longint занимает очень много памяти!).
Для создания матрицы смежности для графа с N вершинами
затрачивается минимум N*N байт.
Матрица смежности - это двумерный массив А размерности N*N.

1, если вершины i и j смежны
А[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
67
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;
68
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.
69
Пусть Г(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
Рис. 2
5
4
6
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.
Рассмотрим некоторые оптимальные алгоритмы поиска.
70
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;

Фрагмент вызывающего алгоритма:
71
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
72
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; {начальная инициализация}
Inc(Yk1); Og[Yk1] := v; Nnew [v] :=false;
{в очередь – вершину v }
While Yk2<Yk1 Do { пока очередь не пуста}
Begin
73
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 ВАРИАНТ
Задача Лабиринт.
Попав в лабиринт, состоящий из одинаковых квадратных комнат,

<< Пред. стр.

страница 8
(всего 10)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign