![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Для пояснення принципу проходження графу вглиб скористаємося графом, поданим на рисунку.
(*)
Цифри на ребрах графу позначають кроки відвідування. Будемо розрізняти відвідувані () і не відвідувані (
) вершини. Кожна вершина обходиться два рази. Якщо всі суміжні вершини пройдені, то повертаємося у попередню вершину.
Проходження графу вглиб здійснюється за такими правилами:
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;
Дата публикования: 2015-06-12; Прочитано: 237 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!