BFS — различия между версиями
(→Алгоритм) |
(→Лемма 1) |
||
| Строка 7: | Строка 7: | ||
==Алгоритм== | ==Алгоритм== | ||
| − | ==Лемма | + | ==Лемма I== |
Кратчайшие пути в графе образуют дерево. | Кратчайшие пути в графе образуют дерево. | ||
''Доказательство'': | ''Доказательство'': | ||
| − | <math> | + | <math> \leq </math> |
}} | }} | ||
Версия 02:32, 15 мая 2020
Breadth-first search (сокр. BFS, рус. Поиск в ширину, Обход в ширину) - один из алгоритмов обхода графа. Является довольно простым и эффективным. Часто используется для поиска кратчайшего пути в графе.
Задача
Пусть задан неориентированный граф G = (V, E). Пусть все ребра имеют одинаковый вес, равный, например, 1. Пусть также задана некоторая начальная вершина S. Пусть расстояние между вершинами - сумма весов рёбер, по которым нужно пройти, чтобы попасть из одной вершины в другую. И пусть, наконец, нужно найти кратчайшее расстояние от начальной вершины до всех остальных. Решим задачу, используя BFS.
Алгоритм
Лемма I
Кратчайшие пути в графе образуют дерево. Доказательство: Невозможно разобрать выражение (Выполняемый файл <code>texvc</code> не найден; См. math/README — справку по настройке.): \leq }}
