Алгоритм проходження графу вглиб

Для пояснення принципу проходження графу вглиб скористаємося графом, поданим на рисунку 11.

Рисунок 11 – Демонстрація проходження графу вглиб.

Цифри на ребрах графу позначають кроки відвідування. Будемо розрізняти відвідувані () і не відвідувані (-) вершини. Кожна вершина обходиться два рази. Якщо всі суміжні вершини пройдені, то повертаємося у попердню вершину.

Проходження графу вглиб здійснюється за такими правилами:

1) перебуваючи у вершині х, треба рухатися до будь-якої іншої, раніше не відвіданої вершини (якщо така знайдеться), одночасно запам'ятовуючи дугу, по якій ми вперше потрапили до цієї вершини;

2) якщо з вершини х ми не можемо потрапити до раніше не відвіданої вершини або такої взагалі немає, то ми повертаємося у вершину z, з якої вперше потрапили до х, і продовжуємо обхід вглиб з вершини z.

Визначимо списки суміжності для кожної вершини графу G:

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

Для кожного вибору початкової вершини у зв'язному графі може бути отримане єдине проходження. Якщо граф являє собою об'єднання компонентів: і | х_і |= n_i, то кількість проходжень такого незв'язного графа: n₁•n₂•...•n_p(i=1,2,...,р)...

Алгоритм проходження графу вглиб буде виглядати так:

procedure ОБХІД-ВГЛИБ(р: вершина);

begin

відвідати вершину р;

for all q from множини вершин, суміжних до р, do

if q ще не відвідана then ОБХІД-ВГЛИБ(q) end

end

end;

begin

for all p from множини вершин G do

if p ще не відвідувалась then ОБХІД-ВГЛИБ(р) end

end

end.

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

procedure dfs(v: integer);

var

i:integer;

begin

used[v]:=true; {відзначити вершину як відвідану}

for i:=1 to n do

{якщо між вершинами є зв'язок та вершина не відвідана}

if (a[v,i]=1)and(not used[i]) then

dfs(i); {викликаємо процедуру з цією вершиною}

end;

Нерекурсивна функція проходження графу вглиб виглядає так:

procedure dfs(v: integer);

var

і: integer;

found: boolean;

begin

used[v]:=true; {відзначили вершину як відвідану}

іnс(с); {збільшуємо кількість занесених у стек вершин}

st[c]:= v; {занесли у стек}

{доки стек не порожній}

while c > 0 do

begin

v:= st[c]; {беремо вершину з голови стеку}

found:= false; {шляху не знайдено}

{проходимо по усіх вершинах з метою пошуку шляху з

обраної вершини}

for і:= 1 to n do

if a[v, і] and not used [і] then

begin

found:= true; {знайшли шлях}

break;

end;

{якщо шлях знайдений}

if found then

begin

used [і]:=true;

inc(c); {додається у стек}

st[c]:= і;

p[i]:=v;

end

else {вилучаємо вершину зі стека}

dec(c);

end;

end;