/
Mikhrutka
/
SpecialistPython2_v2
Обзор
Документация
Войти
/
Mikhrutka
/
SpecialistPython2_v2
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
Module7/examples/bfs.py
38 строк
2 KB
boo-learn
fix tasks Module-7
24 июл 2021, 05:23
24 июл 2021, 05:23
3aab6e7
Код
Авторство
О чём код?
# BFS(Breadth-First Search). Алгоритм поиска в ширину. # Позволяет найти кратчайшие расстояния из одной вершины невзвешенного (ориентированного или неориентированного) графа # до всех остальных вершин. # Под кратчайшим путем подразумевается путь, содержащий наименьшее число ребер. # Алгоитм: # 1. Начальную вершину помещаем в очередь # 2. Пока очередь не пуста: # 2.1 Достаем из очереди первую вершину # 2.2 Для каждой вершины списка смежности # 2.2.1 Если еще до этой вершины еще не доходили, то помечаем расстояние до нее и добавляем ее в конец очереди # 2.2.1 Если вершину уэе посещали, то игнорируем ее # 3 --5--2 6--7 # / \ / / # 0---1--4 graph = [ # список смежности [1, 3], # 0 [0, 3, 4, 5], # 1 [4, 5], # 2 [0, 1, 5], # 3 [1, 2], # 4 [1, 2, 3], # 5 [7], # 6 [6] # 7 ] start = 0 lengths = [None] * (len(graph)) lengths[start] = 0 queue = [start] while queue: cur_vertex = queue.pop(0) for vertex in graph[cur_vertex]: if lengths[vertex] is None: lengths[vertex] = lengths[cur_vertex] + 1 queue.append(vertex) print(lengths)