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

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

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

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

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

План

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

Маємо граф 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. Алгоритм Деккера.

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