Просмотр исходного текста страницы BFS

'''Breadth-first search''' (сокр. '''BFS''', рус. ''Поиск в ширину'', ''Обход в ширину'') - один из алгоритмов обхода графа. Является довольно простым и эффективным. Часто используется для поиска кратчайшего пути в графе.

==Задача==

Пусть задан неориентированный граф ''G = (V, E)''. Пусть все ребра имеют одинаковый вес, равный, например, ''1''. Пусть также задана некоторая начальная вершина ''S''. Пусть ''расстояние между вершинами'' - сумма весов рёбер, по которым нужно пройти, чтобы попасть из одной вершины в другую. И пусть, наконец, нужно найти кратчайшее расстояние от начальной вершины до всех остальных. Решим задачу, используя '''BFS'''.

==Алгоритм==


===Лемма I===
Кратчайшие пути в графе образуют дерево.

''Доказательство'':