Реализации алгоритмов/Поиск в ширину: различия между версиями
Содержимое удалено Содержимое добавлено
RomanSuzi (обсуждение | вклад) дополнение |
RomanSuzi (обсуждение | вклад) Скопировано из w:Поиск в ширину |
||
Строка 1:
{{wikipedia|Поиск в ширину}}
'''Поиск в ширину''' ({{lang-en|breadth-first search}}, '''BFS''') — метод [[w:Обход графа|обхода графа]] и [[w:Алгоритм поиска|поиска пути в графе]].
Поиск в ширину работает путём последовательного просмотра отдельных ''уровней'' [[w:Граф (математика)|графа]], начиная с узла-источника <math>u</math>.
Рассмотрим все [[w:Ребро (теория графов)|рёбра]] <math>(u,v)</math>, выходящие из [[w:Узел (теория графов)|узла]] <math>u</math>. Если очередной узел <math>v</math> является целевым узлом, то поиск завершается; в противном случае узел <math>v</math> добавляется в [[w:Очередь (структура данных)|очередь]]. После того, как будут проверены все рёбра, выходящие из узла <math>u</math>, из очереди извлекается следующий узел <math>u</math>, и процесс повторяется.
== [[Python]] ==
| |||