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

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

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

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

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

Читати повністю