В этот раз поговорим про breadth-first Search — алгоритм, способный быстро и без ограничений пройтись по графу. Алгоритм: Сначала берём стартовую вершину и добавляем в очередь. После вытаскиваем её из очереди и добавляем соседей. С соседями делаем тоже самое, что и с первой вершиной. BFS часто используют для вычисления расстояния между вершинами, поиска кратчайшего пути. Теперь посмотрим, как выглядит исходный код программы для реализации поиска в ширину на python. Рассмотрим следующий граф, который реализован в приведенном ниже коде: Вывод; Following is the Breadth-First Search
5 3 7 2 4 8 #алгоритмы #графы
В этот раз поговорим про breadth-first Search — алгоритм, способный быстро и без ограничений пройтись по графу.
Алгоритм: Сначала берём стартовую вершину и добавляем в очередь. После вытаскиваем её из очереди и добавляем соседей. С соседями делаем тоже самое, что и с первой вершиной.
BFS часто используют для вычисления расстояния между вершинами, поиска кратчайшего пути.
Теперь посмотрим, как выглядит исходный код программы для реализации поиска в ширину на python.
Рассмотрим следующий граф, который реализован в приведенном ниже коде:
Вывод;
Following is the Breadth-First Search
5 3 7 2 4 8
#алгоритмы #графы