Обхід графа в ширину

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

Пошук в ширину в неорієнтованому графі

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

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

Зауваження: під час проходження графа за допомогою алгоритму обходу в ширину, кожній з вершин зіставляєтьс ціле число  (глибина пошуку в ширину). Тобто, починаючи з вершини , приписуємо їй номер 0. Кожній вершині з оточення вершини 0 приписуємо номер 1. Розглядаємо по черзі оточення всіх вершин з номером 1 і кожної з вхідних в ці оточення вершин (тобто суміжних з 1), ще не занумерованих, приписуємо номер 2. Розглядаємо оточення всіх вершин з номером 2 і так далі, поки можливо.

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

Обхід графа в ширину – приклад:

Використовуючи розглянутий алгоритм обходу побудувати дерево пошуку в ширину наступного неорієнтованого графа:

Неорієнтований граф задачі

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

Вершина «1» поєднана неорієнтованими ребрами ,  і  з вершинами «2», «3» і «5» відповідно. Виходячи з того, що дані вершини ніколи раніше не відвідувались, то в якості глибини для них вказуємо число «один». Відмітимо, що після виконання даного кроку вершини «2», «3» і «5» перетворюються на активні пройдені вершини, а переглянуті ребра , і – на ребра дерева пошуку в ширину. Вершина «1» при цьому перестає бути активною і перетворюється на повністю скановану.

На наступному кроці, переходимо до дослідження не переглянутих ребер всіх вершин глибина яких дорівнює «один». Отже, вершина «2» поєднана непереглянутими ребрами з вершинами «3» та «4». Але вершина «3» вже відвідувалась раніше (ребро помічаємо як зворотнє), тому залишається тільки вершина «4», яка перетворюється на активну відкриту вершину і якій, в якості глибини, присвоюється значення «два». З вершини «3», використовуючи не переглянуті ребра, попадаємо у вже відвідані вершини «4» та «5». Тому жодній з них, для глибини обходу, число «два» не присвоюємо, а вершина «3» перетворюється на повністю скановану. Відмітимо, що виходячи з того, що інцидентних не переглянутих ребер для вершини «5» не залишилось, то вона автоматично перетворюється на повністю скановану вершину.

Побудова дерева обходу в ширину для неорієнтованого графа

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

Блок-схема алгоритму обходу графа в ширину