Пошук в ширину – один із базових алгоритмів, що є основою багатьох інших. Наприклад, алгоритм Дейкстри пошуку найкоротших шляхів з одної вершини і алгоритм Прима пошуку мінімального остового дерева можуть розглядатися як узагальнення пошуку в ширину. Згідно з цим алгоритмом обхід вершин заданого графа здійснюється в порядку їх віддаленості від деякої заздалегідь обраної, або зазначеної як початкова, вершини
(називається коренем пошуку в ширину). Інакше кажучи, спочатку відвідується сама вершина
, потім всі вершини, суміжні з
, тобто ті, які знаходяться від неї на відстані в одне ребро, потім вершини, що знаходяться від
на відстані в два ребра, і так далі.
Пошук в ширину в неорієнтованому графі
Розглянемо алгоритм пошуку в ширину із заданої стартової вершини . Отже, спочатку всі вершини позначаються як непройдені. Першою відвідується вершина
, вона стає єдиною пройденою активною вершиною. На наступному кроці, досліджуються ребра, інцидентні даній вершині. У загальному випадку, при такому дослідженні, можливі два варіанти подальших дій:
- Якщо всі ребра, інцидентні вершині
переглянуті, вона перестає бути активною і перетворюється в повністю скановану вершину. В такому випадку вибирається нова активна вершина, і описані дії повторюються.
- Якщо існують не переглянуті ребра, інцидентні
, то досліджуємо їх. Якщо таке ребро з’єднує вершину
з новою вершиною, в нашому випадку це вершина
, то вершина
відвідується і перетворюється у пройдену активну вершину. Відмітимо, що в такому випадку ребро
називається ребром дерева для якого, як і у випадку з пошуком у глибину, задається відповідний напрямок з
в
. Якщо ж вершина
, була пройдена раніше, то продовжуємо пошук іншого непройденого ребра, інцидентного
. В цьому випадку ребро називається зворотним.
Зауваження: під час проходження графа за допомогою алгоритму обходу в ширину, кожній з вершин зіставляєтьс ціле число (глибина пошуку в ширину). Тобто, починаючи з вершини
, приписуємо їй номер 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» присвоюємо статус повністю сканованої і на цьому алгоритм обходу графа в ширину можна вважати завершеним.