• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

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

План

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

Маємо граф G = (X,U), X={x₁,x₂,...,x_n}... Кожне проходження можна розглядати як певну послідовність. Максимальна кількість проходжень (перестановок) – n!.

Для пояснення принципу проходження графу вглиб скористаємося графом, поданим на рисунку 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;

Читайте також:

1. I. Доповнення до параграфу про точкову оцінку параметрів розподілу
2. Rete-алгоритм
3. Адміністративно-правове регулювання проходження державної служби
4. Алгоритм
5. Алгоритм
6. Алгоритм 1.
7. Алгоритм RLE
8. Алгоритм безпосередньої заміни
9. Алгоритм Берлекемпа-Мессі
10. Алгоритм відшукання оптимального плану.
11. Алгоритм Дейкстри.
12. Алгоритм Деккера.

Переглядів: 1827