Смекни!
smekni.com

Поиск в ширину на графах (стр. 2 из 4)

(б)

Рис.4. Списки инцидентности ЗПИСЬ[v], v =V, соответствующие графам на рис.1.

из списка, мы можем легко за число шагов, ограниченное кон­стантой, удалить другой элемент, представляющий то же са­мое ребро, не просматривая список, содержащий этот элемент.

Аналогичным способом определяем для каждой вершины и неориентированного графа список ПРЕДШ[v], содержащий вершины из множества (u: u -> v).

Число ячеек памяти, необходимое для представления графа с помощью списков инцидентности, будет, очевидно, иметь по­рядок m + n. На рис.4 представлены списки инцидентности, соответствующие графам на рис. 1.

2. Анализ алгоритма.

Рассмотрим метод поиска в графе, называемый поиском в ширину (англ: breadth first search). Прежде чем описать его, отметим, что при поиске в глубину чем позднее будет посещена вершина, тем раньше она будет использована — точнее, так будет при допущении, что вторая вершина посещается перед использованием первой. Это прямое следствие того факта, что просмотренные, но еще не исполь­зованные вершины скапливаются в стеке. Поиск в ширину, грубо говоря, основывается на замене стека очередью. После такой модификации, чем раньше посещается вершина (поме­щается в очередь), тем раньше она используется (удаляется из очереди). Использование вершины происходит с помощью про­смотра сразу всех еще не просмотренных соседей этой вершины. Вся процедура поиска представлена ниже (данная процедура используется также и для просмотра графа, и в псевдокоде, описанном ниже, отсутствуют операторы, которые не используются для поиска).

1 procedure WS (v);

(*поиск в ширину в графе с началом в вершине v;

переменные НОВЫЙ, ЗАПИСЬ — глобальные *)

2 begin

3 ОЧЕРЕДЬ := Æ; ОЧЕРЕДЬ <= v; НОВЫЙ [v] := ложь

4 while ОЧЕРЕДЬ ¹Æ do

5 begin р<= ОЧЕРЕДЬ; посетить р;

6 for u Î ЗАПИСЬ [р] do

7 if НОВЫЙ [u] then

8 begin ОЧЕРЕДЬ <= u; НОВЫЙ [u]:=ложь

9 end

10 end

end

Примечание: в 7-й строке псевдокода кроме условия НОВЫЙ[u] должно также выполниться условие наличия связи (ребра) между v-й и u-й вершинами. Для установки наличия ребра сначала в списке v-й вершины ищется информационное значение и-й вершины. Если оно найдено, то ребро установлено, если нет, то информационное значение v-й вершины ищется в списке и-й вершины, т.е. наоборот. В результате добавления двух лишних циклов поиска общий алгоритм поиска несколько теряет компактность, но на быстродействии в целом это не сказывается.

1 procedure Write_S;

2 begin

3 for v Î V do НОВЫЙ[u]:= истина; (* инициализация *)

4 for v Î V do

5 if HOBЫЙ[v] then WG(v)

6 end

Способом, аналогичным тому, какой был применен для по­иска в глубину, можно легко показать, что вызов процедуры WS(v) приводит к посещению всех вершин связной компоненты графа, содержащей вершину v, причем каждая вершина про­сматривается в точности один раз. Вычислительная сложность поиска в ширину также имеет порядок О(m + n), так как каждая вершина помещается в очередь и удаляется из очереди в точ­ности один раз, а число итераций цикла 6, очевидно, будет иметь порядок числа ребер графа.

В очереди помещены сначала вершины, находящиеся на расстоянии 0 от v (т. е. сама вершина v), затем поочередно все новые вершины, достижимые из v, т. е. вершины, находя­щиеся на расстоянии 1 от v, и т. д. Под расстоянием здесь мы понимаем длину кратчайшего пути. Предположим теперь, что мы уже рассмотрели все вершины, находящиеся на расстоянии, не превосходящем r, от v, что очередь содержит все вершины, находящиеся от v на расстоянии r, и только эти вершины. Использовав каждую вершину р, находящую­ся в очереди, наша процедура просматривает некоторые новые вершины, и каждая такая новая вершина u находится, оче­видно, на расстоянии г + 1 от v. После использования всех вер­шин из очереди, находящихся на расстоянии r от v, она (оче­редь), очевидно, содержит множество вершин, находящихся на расстоянии r + 1 от v, и легко заметить, что условие индукции выполняется и для расстояния r + 1.

На рис. 5 представлен граф, вершины которого зануме­рованы согласно очередности, в которой они посещаются в про­цессе поиска в глубину.

Как и в случае поиска в глубину, процедуру WS можно использовать без всяких модификаций и тогда, когда списки

1(1)

10(7)

Рис. 5 Нумерация вершин графа (в скобках), соответствующая очередности, в которой они просматриваются в процессе поиска в ширину.

инцидентности ЗАПИСЬ[v], v = V, определяют некоторый ориентированный граф. Очевидно, что тогда посещаются толь­ко те вершины, до которых существует путь от вершины, с ко­торой мы начинаем поиск

3. Спецификация задачи

3.1 Входные и выходные данные

ver – массив вершин графа, заполняемый случайным образом целыми числами в диапазоне от 0 до 1000;

nv - массив флагов проверки вершин;

ocher – массив для организации очереди, заполняемой значениями рассматриваемых информационных вершин графа;

raz – переменная целочисленного типа, определяющая в программе размер создаваемого графа;

schet – счетчик количества сравнений в процедуре поиска;

key – вводимый с клавиатуры ключ поиска;

mgsi – переменная логического типа, разрешающая вывод списка инцидентности графа;

prosm - переменная логического типа, превращающая процедуру поиска WS в процедуру просмотра графа;

find - переменная логического типа, определяемая при нахождении искомой информационной вершины;

craz, menu, mg, sormen – переменные символьного типа для работы с меню программы.

3.2 Используемые процедуры

Make_Graph – процедура создания графа в динамической памяти;

WS - процедура просмотра графа с v-той вершины методом поиска в ширину;

Write_S – процедура инициализации признаков просмотра вершин и управляющая процедурой WS;

Sort - процедура сортировки вершин графа по неубыванию.

4. Текст программы на языке TURBO PASCAL

4.1 Листинг программы.

{$S+} {$R+} {$I+} {$M 65520,0,655360}

program graph;

uses crt,newtimer;

const

maxraz=400;

type index=^list;

list= record

inf: word;

next: index;

end;

connection=array[1..maxraz] of index;

var

el,em,size: pointer;

lst,m: connection;

ver: array[1..maxraz] of word; {массив вершин}

Nw: array[1..maxraz] of boolean;

ocher: array[1..maxraz+1] of integer;

raz: integer;

exch,fil,i,j,l,schet,v,u,p: word;

key,kols,t,tm: longint;

mgsi,mem,sor,prosm,find: boolean;

craz,menu,mg,sormen:char;

{------------------------------------------------------

***Процедура создания графа в динамической памяти***}

procedure Make_Graph(mgsi: boolean);

label Er;

var

n: index;

i,j: word;

kolvo: longint;

spro: boolean;

begin

randomize;

for i:=1 to raz do begin

ver[i]:=random(1000);

end;

kolvo:=0;

for i:=1 to raz do begin

lst[i]:=nil;

for j:=1 to raz do begin

spro:=true;

if j=raz then goto Er;

if j=i then inc(j);

n:=nil;

n:=lst[j];

if lst[j]<>nil then

repeat

if n^.inf=ver[i] then spro:=false;

n:=n^.next;

until (n=nil) or (not(spro));

if (round(random)=1) and spro then

begin

new(m[i]);

inc(kolvo);

m[i]^.inf:=ver[j];

m[i]^.next:=lst[i];

lst[i]:=m[i];

end;

Er:

end;

end;

writeln;

if mgsi then {ВЫВОД СВЯЗЕЙ ВЕРШИН}

for i:=1 to raz do {}

begin {}

write(ver[i],'-'); {}

m[i]:=lst[i]; {}

if m[i]<>nil then {}

repeat {}

write(m[i]^.inf,'═'); {}

m[i]:=m[i]^.next; {}

until m[i]=nil; {}

writeln('ᄃ'); writeln; {}

end; {}

writeln('КОЛ-ВО РЕБЕР СОЗДАННОГО ГРАФА: ',kolvo);

end;

{------------------------------------------------------

***Процедура просмотра графа с v-той вершины методом поиска в ширину***}

Procedure WS(v:word; var find: boolean;

var schet: word);

var {v - пор. номер вершины графа}

ik,oo,o9,o3,op: integer;

rebro: boolean;

begin {оо - размер очереди в данном цикле}

ocher[1]:=v; oo:=1; {вставка текущего индекса вершины в начало очереди}

Nw[v]:=False; {флаг на вершину текущего индекса}

while oo>0 do begin {пока есть очередь...}

p:=ocher[1];{удаление 1-го элемента из очереди и присваивание его p}

for op:=1 to oo-1 do ocher[op]:=ocher[op+1]; ocher[oo]:=0;

dec(oo);

inc(schet); {счетчик сравнений}

if not(prosm) and (ver[p]=key) then {if ver[p]=key...}

begin

find:=true;

exit; {поиск окончен}

end;

{вывод (просмотр) информации вершины}

if prosm then begin

if wherex>=79 then writeln;

write(ver[p],' ');

end;

o9:=oo;

for u:=1 to o9 do {u изменяется в диапазоне размера очереди}

begin

rebro:=false;{связи между ver[v] и ver[u] нет}

{указатель на начало списка связей v-й вершины}

m[v]:=lst[v];

while m[v]<>nil do

begin {поиск значения ver[u] в списке связей v-й вершины}

if m[v]^.inf=ver[u] then begin

{ребро есть} rebro:=true;

break;

end;

m[v]:=m[v]^.next; {ребра пока нет...}

end;

{если связь не установлена, поищем связь с ver[v] в списке u-й вершины, т.е. наоборот...}

if not(rebro) then

begin

m[u]:=lst[u];{указатель на начало списка связей u-й вершины}

while m[u]<>nil do

begin

if m[u]^.inf=ver[v] then begin

rebro:=true;

break;

end;

m[u]:=m[u]^.next;

end;

end;

{если связь все таки есть и u-я вершина еще не рассмотрена...}

if rebro and Nw[u] then

begin

inc(oo); {вставка u в начало очереди}

for op:=oo downto 2 do ocher[op]:=ocher[op-1];

ocher[1]:=u;

Nw[u]:=False;{флаг на вершину с индексом u}

end;

end;

end;

end;

{------------------------------------------------------

***Процедура просмотра графа***}

Procedure Write_S(key: longint; prosm: boolean;

var find: boolean; var schet: word);

begin

{инициализация признаков просмотра вершин}

for i:=1 to raz do Nw[i]:=true;

for i:=1 to raz do

{если из raz вершин i-ая не использована, то смотреть граф с i-ой вершины}

if Nw[i] and not(find) then WS(i,find,schet);

end;

{------------------------------------------------------

***Процедура сортировки вершин по неубыванию***}

procedure Sort;

begin

for l:=1 to raz-1 do

for j:=1 to raz-l do

if ver[j]>ver[j+1] then

begin

exch:=ver[j];

el:=lst[j];

em:=m[j];

ver[j]:=ver[j+1];

lst[j]:=lst[j+1];

m[j]:=m[j+1];

ver[j+1]:=exch;

lst[j+1]:=el;

m[j+1]:=em;

end;

end;

{=====================================================}

begin

while menu<>'4' do

begin

textmode(1);

textbackground(blue);

clrscr;

textcolor(red);

gotoxy(16,3); writeln('Г Р А Ф Ы');

textcolor(white);gotoxy(5,5);

writeln('* Исследование поиска в ширину *');

textcolor(black); gotoxy(7,22);

writeln('Created by Andrew Spikhailo');

gotoxy(15,24); write('ARMAVIR 2001');

textcolor(white);

gotoxy(7,10); write('┌───────────MENU───────────╖');

gotoxy(7,11); write('│');textcolor(green);

write('1 Создание графа '); textcolor(white);write('║');

gotoxy(7,12); write('│');textcolor(green);