BFS — различия между версиями

Материал из Public ATP Wiki
Перейти к: навигация, поиск
(Лемма 1)
(Алгоритм)
 
(не показаны 3 промежуточные версии этого же участника)
Строка 7: Строка 7:
 
==Алгоритм==
 
==Алгоритм==
  
==Лемма I==
+
 
 +
===Лемма I===
 
Кратчайшие пути в графе образуют дерево.
 
Кратчайшие пути в графе образуют дерево.
 +
 
''Доказательство'':
 
''Доказательство'':
<math> \leq </math>
 
}}
 

Текущая версия на 02:34, 15 мая 2020

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

Задача

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

Алгоритм

Лемма I

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

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