Алгоритми пошуку в глибину та ширину в графах - MathHelpPlanet

Обговорення та вирішення завдань з математики, фізики, хімії, економіки

Часовий пояс: UTC + 3 години [ Літній час ]

Введення в аналіз

Теорія черг (СМО)

Алгоритми пошуку в глибину та ширину в графах

Одним із способів побудови максимального кістякового лісу може бути пошук у глибину. Саме при пошуку в глибину всяке ребро, яким з поточної вершини ми потрапляємо в невідзначену раніше вершину, буде деревним. Кожне ребро, яке не є деревним, буде зворотним. Максимальний кістяковий ліс, що знаходиться за допомогою алгоритму пошуку в глибину, називають кістяковим лісом пошуку в глибину або глибинним кістяковим лісом.

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

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

Зазначимо, що не всякий максимальний остовний ліс може бути отриманий за допомогою алгоритму пошуку в глибину. Наприклад, для графа, зображеного на рис. 5.23, виділений максимальний остовний ліс не можна отримати при пошуку в глибину, з якої б вершини ми не починали пошук.

Для роботи алгоритму пошуку в глибину використовується спосіб зберігання даних, званий стеком. Елементи в стеку впорядковуються як надходження. До стек можна додавати нові елементи і з нього можна витягувати елементи. При цьому доступний тільки останній доданий елемент - вершина стека, чим і визначається режим роботи стека (останнім прийшов - першим пішов). Образно стек можна подати у вигляді стопки тарілок. З чаркиможна взяти тільки верхню тарілку і лише нагору можна додати нову. Зазвичай стек реалізується як списку.

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

Алгоритм пошуку у глибину

Вхід. Граф [math]G=(V,E)[/math] , заданий списками суміжності.

Вихід. Безліч Tree дерев'яних і Back зворотних ребер відповідно; безліч [math]F_c[/math] фундаментальних циклів, масив [math]D[/math] , що містить D-номери вершин.

0. Переглянути масив лідерів та сформувати безліч [math]V_0[/math] вершин графа. Ця множина використовується для зберігання нових (не оброблених алгоритмом) вершин. У ході роботи алгоритму оброблені вершини видалятимуться з цієї множини.

У процесі роботи алгоритму кожної вершини v необхідно знати, які вершини з її списку суміжності [math]L[v][/math] оброблені попередніх кроках роботи алгоритму. І тому формується масив [math]L_p[/math] розміру [math]V_0[/math] , у якому зберігаються номери перших ще оброблених алгоритмом вершин списку суміжності [math]L[v][/math] кожної вершини [math] [/ Math] . Спочатку всі елементи масиву [math]L_p[/math] вважають рівними 1.

Стек вершин STACK та список вершин фундаментального циклу Cycle покласти порожніми [math](STACK=\varnothing,

Безліч Tree деревних ребер, Back зворотних ребер і [math]F_c[/math] фундаментальних циклів покласти порожніми [math](Tree=\varnothing,

Back = \ varnothing, F_c = \ varnothing) [/ math] . Масив D-номерів [math]D[/math] обнулити.

Задати початкову вершину для пошуку[math](v=v_0)[/math] . (Зазвичай це перша вершина масиву лідерів.) Лічильник D-номерів вершин count покласти рівним 1 ( count =1).

1. Якщо безліч [math]V_0[/math] не порожня [math](V_0\ne\varnothing)[/math] , перейти на крок 2, якщо інакше - на крок 8 (вихід).

2. Якщо стек порожній [math](STACK=\varnothing)[/math] і алгоритм стартує з вершини [math]v_0[/math] ( count =1), то перейти на крок 3 якщо інакше, то вибрати з множини [math]V_0[/math] довільну вершину, з якої пошук у глибину буде продовжено [math](v=u,\, u\in V_0)[/math] , і перейти на крок 3 .

3. Помістити поточну вершину [math][/math] у стек STACK . Присвоїти вершині [math][/math] D-номер [math](D[v]=count)[/math] . Збільшити лічильник D-номерів на 1 [math](count=count+1)[/math] . Видалити вершину [math][/math] з множини [math]V_0[/math] нових вершин. Перейти до кроку 4 .

4. Перевірити по елементу [math]L_p[v][/math] , що не досягнуто кінця списку суміжності [math]L[v][/math] поточної вершини [math][/math] . Якщо у списку суміжності є ще не оброблені вершини, одержати зі списку суміжності чергову вершину [math]w[/math] , збільшити [math]L_p[v][/math] на 1 і перейти на крок 6 .

Якщо список суміжності [math]L[v][/math] вершини v повністю оброблений, видалити вершину [math][/math] зі стека STACK і перейти на крок 5 .

5. Якщо стек STACK порожній, повернутися на крок 1, якщо інакше, то як поточна вершина [math][/math] взяти вершину, що знаходиться у вершині стека, і перейти на крок 4 .

6. Якщо вершина [math]w[/math] нова [math](w\in V_0)[/math] , то додати ребро [math]\[/math] до множини деревних ребер

зробити вершину [math]w[/math] поточною [math](v=w)[/math] і повернутися на крок 3 . Якщо вершина w не нова [math](w\notin V_0)[/math] , то перейти наКрок 7 .

7. Якщо ребра [math]\[/math] немає серед деревних [math](\\notin Tree)[/math] , помістити ребро до списку зворотних ребер

Помістити вершину [math]w[/math] до списку Cycle . Читати вміст стеку STACK , починаючи з вершини стека, до появи вершини [math]w[/math] і поміщати у список Cycle (включаючи вершину [math]w[/math] ), тобто. формувати фундаментальний цикл, що відповідає зворотному ребру [math]\[/math].

Додати список Cycle до множини фундаментальних циклів [math]F_c[/math]

Список Cycle покласти порожнім [math](Cycle=\varnothing)[/math] .

Повернутись на крок 4 .

8. Закінчити роботу.

Нехай для неорієнтованого графа, зображеного на рис. 5.20,а, списки суміжності мають вигляд (5.1). При виконанні пошуку в глибину виділені ребра є деревними, решта – зворотними. Біля кожної вершини вказано присвоєний їй D-номер. Фундаментальні цикли - в порядку їх знаходження - такі:

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

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

Слабкими компонентами цього глибинного кістякового лісу будуть деякі орієнтованідерева: тому, використовувана далі термінологія з теорії дерев відноситься до тієї чи іншої слабкої компоненти глибинного кістякового лісу. У орієнтованому графі вершинам також присвоюються D-номери. Але класифікація дуг при пошуку в глибину в орієнтованому графі складніша порівняно з аналогічною класифікацією ребер при пошуку в глибину в неорієнтованому графі. Розрізняють чотири класи дуг:

1) деревні дуги - кожна така дуга веде від батька до сина в глибинному кістяковому лісі;

2) прямі дуги - кожна така дуга веде від справжнього предка до справжнього нащадка (але не від батька до сина) у глибинному остовному лісі;

3) зворотні дуги - від нащадків до предків (включаючи всі петлі);

4) поперечні дуги - всі дуги, що не є ні деревними, ні прямими, ні зворотними.

Отже, в результаті роботи алгоритму будуть отримані безлічі Tree - деревних дуг, Back - зворотних дуг, Forward - прямих дуг, [math]C[/math] - поперечних дуг і масив [math]D[/math], що містить D-номери вершин.

У процесі роботи алгоритму, порівняно з алгоритмом пошуку в глибину в неорієнтованому графі, є ряд особливостей. Тож якщо чергова вершина [math]w[/math] , витягнута зі списку суміжності поточної вершини [math][/math] , нова, тобто. [math]w\in V_0[/math] , то дуга [math](v,w)[/math] є деревною. Слід додати дугу [math](v,w)[/math] до множини деревних дуг [math]Tree=Tree\cup\[/math] , зробити вершину [math]w[/math] поточною [math](v= w)[/math] і розпочати її обробку.

Якщо вершина [math]w[/math] не нова [math](w\notin V_0)[/math] , то дуга [math](v, w)[/math] буде або прямою, або зворотною, або поперечною.

Якщо D-номер вершини v строго менший за D-номера вершини [math]w[/math] [math](D[v]

Алгоритм пошукузавширшки в орієнтованому графі

На відміну від алгоритму пошуку завглибшки, алгоритм пошуку завширшки використовує не стік, а чергу вершин. Ми дамо тут варіант пошуку завширшки, коли, починаючи пошук у деякій початковій вершині [math]v_0[/math] , ми зупиняємося при першому спустошенні черги. Це означає, що деякі з вершин можуть залишитись невідзначеними. Таким чином, може бути вирішена задача розпізнавання досяжності від заданої вершини. Ми сумісний також пошук завширшки з обчисленням довжини найкоротшого шляху від [math]v_0[/math] до будь-якої вершини графа. Припускатимемо, що вершини графа пронумеровані без перепусток числами від 0 до [math]N\colon\, \>[/math] .

Пошук завширшки розглядаємо тільки для орієнтованого графа.

Вхід. Граф [math]G=(V,E)[/math] , заданий списками суміжності; [math]v_0[/math] - Початкова вершина (не обов'язково перший елемент масиву лідерів).

Вихід. Масив [math]M[/math] міток вершин, де кожна мітка дорівнює довжині шляху від [math]v_0[/math] до [math][/math] .

0. Черга [math]Q[/math] покласти порожній [math](Q=\varnothing)[/math]. Усі вершини позначити як недосяжні з вершини [math]v_0[/math] , присвоюючи елементам масиву [math]M[/math] значення [math]+\infty

Стартову вершину [math] v_0 [/ math] позначити номером 0, тобто. довжину шляху від стартової вершини [math] v_0 [/math] до самої себе покласти рівною 0 [math] (M [v_0] = 0) [/ math]. Помістити вершину [math]v_0[/math] у чергу [math]Q[/math] . Перейти до кроку 1 .

1. Якщо черга [math]Q[/math] не порожня [math](Q\ne\varnothing)[/math] , то з "голови" черги витягти (з видаленням з черги) вершину [math]u[/math ] та перейти на крок 2 . Якщо черга порожня, перейдіть на крок 3 .

2. Якщо список суміжності [math]L(u)[/math] вершини[math]u[/math] порожній, повернутися на крок 1 .

3. Роздрукувати масив [math] M [/ math]. Закінчити роботу.

Алгоритм пошуку завширшки може бути доповнений процедурою "зворотного ходу", що визначає номери вершин, що лежать на найкоротшому шляху з вершини [math]v_0[/math] у цю вершину [math]u[/math] . Для цього необхідно завести масив [math]PR[/math] розміру [math]V[/math] , кожен елемент [math]PR[w][/math] якого містить номер тієї вершини, з якої було здійснено перехід у вершину [ math]w[/math] при її позначці.

Якщо вершина [math]w[/math] знаходиться у списку суміжності [math]L(u)[/math] вершини [math]u[/math] , заповнення елемента масиву [math]PR[w][/math] відбувається при зміні мітки вершини [math] w

M[w][/math] з [math]+\infty[/math] на одиницю. У цьому елементі [math]PR[w][/math] зберігається номер вершини і [math](PR[w]=u)[/math] . Для початкової вершини [math]PR[v_0][/math] можна покласти рівним 0, припущення, що початкова вершина [math]v_0[/math] має номер 0 та інші вершини пронумеровані від 1 до N.

Складність розглянутого алгоритму пошуку шириною, відомого під назвою "Алгоритм хвильового фронту", становить [math]O(\max(V,E))[/math] .

Приклад 5.8. На рис. 5.25 дано приклад роботи алгоритму хвильового фронту (під час пошуку з вершини [math]v_0[/math] ) для орієнтованого графа, зображеного на рис. 5.24. Списки суміжності орієнтованого графа мають вигляд (5.2).

Біля кожної вершини [math]v_i[/math] поставлена ​​мітка [math]M[v_i][/math] , яку отримує вершина під час пошуку завширшки. Виділено дуги, що становлять найкоротші шляхи з вершини [math]v_0[/math] до інших. Зазначимо, що вершини [math]v_5,\,v_6[/math] і [math]v_7[/math] не досяжні з [math]v_0[/math] та їх початкові мітки[math]+\infty[/math] залишилися без зміни. При розглянутому ході алгоритму масив [math]PR[/math] міститиме наступні номери вершин:

Для решти вершин відповідні значення не визначено, оскільки вони не "відвідувались".

Використовуючи масив [math]PR[/math], відновимо найкоротший шлях з вершини [math]v_0[/math] у вершину [math]v_4[/math]. Оскільки [math]PR[v_4]=2[/math] , a [math]PR[v_2]=0[/math] , шуканий шлях є [math]v_0,v_2,v_4[/math] .

---