Тема:Пошук у ширину та глибину.

Конспект уроку

Граф G визначається двома множинами - множиною вершин V та множиною ребер або дуг (пар вершин) E: G=(V, E). Якщо пара вершин неупорядкована, то її прийнято називати ребром, а якщо упорядкована - дугою. Граф, що складається тільки з ребер називається неорієнтованим графом. Граф, що містить тільки дуги, - орієнтованим графом чи орграфом.

На малюнку граф можна представити точками, що відповідають вершинам графа, та лініями, що з'єднують вершини і відповідають ребрам графа, або спрямованими від вершини до вершини лініями, що відповідають дугам графа.

Існує багато алгоритмів на графах, що орієнтовані на розв'язання задач з різних областей застосування. Багато з них вимагають перегляду усієї множини вершин графа. Ця група алгоритмів базується на тому чи іншому методі пошуку у графі.

Пошук у графі передбачає перегляд вершин графа, починаючи з деякої. Методи пошуку у графах розрізняються порядком дослідження вершин.

1. Пошук у глибину

 

Пошук у глибину прагне проникнути подалі від вихідної вершини. Ідея цього методу наступна. На кожному кроці методу:

З поточної вершини рухаємося в першу вершину, суміжну з поточною, у якій ми ще не були, якщо така є.

Якщо такої немає, то повертаємося у вершину, з якої ми потрапили в поточну.

Якщо ж такої немає і ми виявилися у вихідній вершині (повертатися нікуди), то це означає, що перебір вершин графа закінчено.

Для програми знадобиться булевий масив для індикації відвіданих вершин

Var Visited: array[1..N] of Boolean;

У цьому масиві будемо позначати вже відвідані вершини. Спочатку масив повинен бути заповнений значеннями false (жодна з вершин не була відвідана). Також домовимося зберігати граф у вигляді списку суміжності.

Тепер реалізуємо алгоритм у рекурсивній процедурі, де параметром виступає v - номер вершини:

 

Procedure DepthSearch(v: Integer);

Var j: Integer;

Begin Visited[v] := True;

Write('Вершина ', v, 'відвідана.');

for j := 1 to Graph[v].Count do

if not Visited[Graph[v].List[j].Node] then

DepthSearch(Graph[v].List[j].Node);

end;

Для того, щоб написати нерекурсивну версію, нам треба ввести додаткові змінні, що будуть зберігати стек повернення (фактично шлях, яким ми потрапили з вихідної вершини в дану).

 

Procedure DepthSearch2(v: Integer);

Var

Way: array[1..N] of

record {вміст стеку повернення}

Node, {номер вершини}

Number: Integer; {кількість розглянутих елементів}

{ списку суміжності}

end;

Count: Integer; {розмір (вершина) стеку}

{повернення}

Current, j: Integer;

Found: Boolean;

begin

Count:=1; Way[Count].Node:=v; Way[Count].Number:=0;

Visited[v] := True;

Write('Вершина ', v, 'відвідана.');

repeat

Current := Way[Count].Node;

Found := False;

for j:=Way[Count].Number+1 to Graph[Current].Count do

begin

if not Visited[Graph[Current].List[j]] then

begin

Inc(Count);

Way[Count].Node := Graph[Current].List[j];

Way[Count].Number := 0;

Visited[Graph[Current].List[j]] := True;

Write('Вершина ', Graph[Current].List[j],

'відвідана.');

Found := True;

Break;

end;

end;

if not Found then Dec(Count);

until Count = 0;

end;

 

2. Пошук у ширину

 

 

Цей алгоритм пошуку в графі також називають хвильовим алгоритмом через те, що обхід графа йде за принципом поширення хвилі. Хвиля розтікається рівномірно в усі боки з однаковою швидкістю. На i-ому кроці будуть виписані усі вершини, досяжні за i ходів, якщо ходом вважати перехід з однієї вершини в іншу.

Метод пошуку в ширину виходить із програми пошуку в глибину, якщо ми замінимо стек повернення на чергу. Ця проста заміна модифікує порядок обходу вершин так, що обхід йде рівномірно в усі сторони, а не всередину як при пошуку в глибину.

 

 

Procedure WidthSearch(v: Integer);

 

Procedure WidthSearch(v: Integer);

Var Delayed: array[1..N] of Integer; {черга}

Count, {хвіст черги}

Head: Integer; {голова черги}

Current, j: Integer;

begin

Count := 1; Head := 0; Delayed[Count] := v;

Visited[v] := True;

Write('Вершина ', v, 'відвідана.');

repeat

Inc(Head); Current := Delayed[Head];

for j := 1 to Graph[Current].Count do

if not Visited[Graph[Current].List[j]] then

begin

Inc(Count);

Delayed[Count] := Graph[Current].List[j];

Visited[Graph[Current].List[j]] := True;

Write('Вершина ', Graph[Current].List[j],

'відвідана.');

end;

until Count = Head;

end;