BFS: различия между версиями
Перейти к навигации
Перейти к поиску
Нет описания правки |
|||
| (не показано 7 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Breadth-first search''' (сокр. '''BFS''', рус. ''Поиск в ширину'', ''Обход в ширину'') - один из алгоритмов обхода графа. | '''Breadth-first search''' (сокр. '''BFS''', рус. ''Поиск в ширину'', ''Обход в ширину'') - один из алгоритмов обхода графа. Является довольно простым и эффективным. Часто используется для поиска кратчайшего пути в графе. | ||
==Задача== | ==Задача== | ||
Пусть задан неориентированный граф ''G = (V, E)''. Пусть все ребра имеют одинаковый вес, например, ''1''. Пусть также задана некоторая начальная вершина ''S'' | Пусть задан неориентированный граф ''G = (V, E)''. Пусть все ребра имеют одинаковый вес, равный, например, ''1''. Пусть также задана некоторая начальная вершина ''S''. Пусть ''расстояние между вершинами'' - сумма весов рёбер, по которым нужно пройти, чтобы попасть из одной вершины в другую. И пусть, наконец, нужно найти кратчайшее расстояние от начальной вершины до всех остальных. Решим задачу, используя '''BFS'''. | ||
==Алгоритм== | |||
===Лемма I=== | |||
Кратчайшие пути в графе образуют дерево. | |||
''Доказательство'': | |||
Текущая версия от 23:34, 14 мая 2020
Breadth-first search (сокр. BFS, рус. Поиск в ширину, Обход в ширину) - один из алгоритмов обхода графа. Является довольно простым и эффективным. Часто используется для поиска кратчайшего пути в графе.
Задача
Пусть задан неориентированный граф G = (V, E). Пусть все ребра имеют одинаковый вес, равный, например, 1. Пусть также задана некоторая начальная вершина S. Пусть расстояние между вершинами - сумма весов рёбер, по которым нужно пройти, чтобы попасть из одной вершины в другую. И пусть, наконец, нужно найти кратчайшее расстояние от начальной вершины до всех остальных. Решим задачу, используя BFS.
Алгоритм
Лемма I
Кратчайшие пути в графе образуют дерево.
Доказательство: