5. Пошук у глибину і ширину
Розглянемо метод пошуку в неорієнтованому графі G, який дістав назву пошук у глибину. Як уже зазначалося, загальна ідея методу полягає в такому. Процес перевірки деякої умови в вершині графу асоцію-ватимемо з процесом відвідування вершини. Відвідаємо вершину v,. Потім вибираємо вершину u навколо вершини v, (суміжну з v1), яка не була ще відвідана, і повторюємо процес знову. Нехай ми відвідали вершину v. Якщо існує нова, ще не відвідана суміжна вершина u з оточення v, тоді відвідуємо її і відмічаємо, що вона перестала бути новою. Процес пошуку далі продовжується з вершини u. Якщо ж для v не існує жодної нової суміжної вершини, тоді відмічаємо, що вершина v вже використана, повертаємось у вершину, з якої ми потрапили у v, і продовжуємо процес пошуку. Якщо вершина v була вершиною v1, то процес пошуку закінчується.
Оцінимо часову оцінку запропонованого алгоритму. Для визначеності вважатимемо, що час, потрібний на відвідування вершини, має константний характер і граф заданий списком суміжності. Враховуючи, що для вибору чергової вершини відвідування потрібно переглянути всі суміжні вершини попередньої вершини відвідування (максимальна кількість суміжних елементів визначається m), а кількість усіх вершин у графі п, часова складність становитиме О (п + т).
Зрозуміло, що у разі задання графу матрицею суміжності часова складність визначатиметься О (п ).
Пошук у ширину можна отримати з алгоритму пошуку в глибину заміною стека чергою. Після відвідування вершини проглядаються всі її суміжні вершини.
Розглянемо застосування алгоритмів пошуку в задачах з графами.
=
(V,
Е),
побудоване процедурою пошуку в глибину.
Вершина v
є V
є точкою з'єднання графу G
тоді і тільки тоді, коли або v
= r
і r
має не менше двох синів в D,
або v
r
і існує син w
вершини v,
такий що ні w,
ні будь-який з його нащадків не зв 'язані
ребром з жодним предком v.
Отже, для знаходження компонент двозв'язності достатньо провести пошук у глибину з деякої вершини r, обчислюючи для кожної вершини v Два параметри: WGN [v] і L [v]. WGN [v] визначає номер вершини v у по-рядку, в якому вершини відвідуються при пошуку в глибину, починаючи з вершини r. L [v] визначає найменше значення WGN [и], де и = v або вершина и зв'язана хордою з вершиною v або її довільним нащадком у D, де D= <V, T> — дерево, яке відповідає нашому пошуку в глибину.