1. Пошук в ширину
2. Процедура пошуку в ширину

Анотація: Пошук в ширину. Процедура пошуку в ширину. BFS-дерево і обчислення відстаней.

Пошук в ширину

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

Процедура пошуку в ширину

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

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

Розглянемо алгоритм пошуку в ширину із заданою стартовою вершиною . Спочатку все вершини позначаються як нові. Першою відвідується вершина , Вона стає єдиною відкритою вершиною. Надалі кожен черговий крок починається з вибору деякої відкритої вершини . Ця вершина стає активною. Далі досліджуються ребра, інцидентні активної вершині. Якщо таке ребро з'єднує вершину з новою вершиною , То вершина відвідується і перетворюється у відкриту. Коли все ребра, інцидентні активної вершині, досліджені, вона перестає бути активною і стає закритою. Після цього вибирається нова активна вершина, і описані дії повторюються. Процес закінчується, коли безліч відкритих вершин стає порожнім.

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

Опишемо процедуру пошуку в ширину (BFS - від англійської назви цього алгоритму - Breadth First Search) з заданою стартовою вершини . У цьому описі позначає безліч всіх вершин, суміжних з вершиною , - черга відкритих вершин. Передбачається, що при відвідуванні вершини вона позначається як відвідана і ця позначка означає, що вершина вже не є новою.

Procedure BFS (a)

1. відвідати вершину
2. 
3. while do
4. 
5. for do
6. досліджувати ребро
7. if вершина нова
8. then відвідати вершину
9. 

Відзначимо деякі властивості процедури BFS.

1. Процедура BFS закінчує роботу після кінцевого числа кроків.

   Дійсно, при кожному повторенні циклу while з черги видаляється одна вершина. Вершина додається до черги тільки тоді, коли вона відвідується. Кожна вершина може бути переглянуло не більше одного разу, так як відвідуються тільки нові вершини, а в результаті відвідування вершина перестає бути новою. Таким чином, число повторень циклу while не перевищує числа вершин.

2. В результаті виконання процедури BFS будуть відвідані всі вершини з компоненти зв'язності, що містить вершину a, і тільки вони.

   Очевидно, що вершина може бути переглянуло тільки в тому випадку, коли існує шлях, що з'єднує її з вершиною (Так як відвідується завжди вершина, суміжна з уже відвідується). Те, що кожна така вершина буде переглянуло, легко доводиться індукцією по відстані від даної вершини до вершини .

3. Час роботи процедури BFS є , де - число ребер в компоненті зв'язності, що містить вершину .

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

Отже, процедура BFS ( ) Виробляє обхід компоненти зв'язності, що містить вершину . Щоб перейти до іншої компоненті, досить вибрати якусь нову вершину (якщо такі вершини ще є), в якості стартової. нехай - безліч вершин графа. Наступний алгоритм здійснює повний обхід графа методом пошуку в ширину.

Алгоритм 1. Пошук в ширину.

1. позначити всі вершини як нові
2. створити порожню чергу
3. for do if нова then BFS ( )

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

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