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

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

(*)

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

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

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

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

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

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

Для кожного вибору початкової вершини у зв'язному графі може бути отримане єдине проходження. Якщо граф є об'єднанням компонентів: , то кількість проходжень такого незв’язного графа .

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

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

i:integer;

found:boolean;

begin

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

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

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

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

while c>0 do

begin

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

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

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

for i:=1 to n do

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

begin

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

break;

end;

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

if found then

begin

used[i]:=true;

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

st[c]:=i;

p[i]:=v;

end

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

dec(c);

end;

end;