/
Krisp
/
FBPreposit
Обзор
Документация
Войти
/
Krisp
/
FBPreposit
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
BFS_path
46 строк
1 KB
Krisp
create BFS_path
05 июн 2025, 12:10
05 июн 2025, 12:10
d3dc9e4
Код
Авторство
О чём код?
# bfs_paths.py from collections import deque from graph import Graph def bfs_shortest_paths(graph, start_node): shortest_paths = {start_node: [start_node]} visited = set([start_node]) queue = deque([start_node]) while queue: current = queue.popleft() for neighbor, _ in graph.get_neighbors(current): if neighbor not in visited: visited.add(neighbor) shortest_paths[neighbor] = shortest_paths[current] + [neighbor] queue.append(neighbor) for vertex in sorted(graph.vertices): if vertex == start_node: continue path = shortest_paths.get(vertex) if path: print(f"Кратчайший путь от {start_node} до {vertex}: {' -> '.join(path)}") else: print(f"Путь от {start_node} до {vertex} не существует.") return shortest_paths if __name__ == "__main__": g = Graph() g.add_edge("A", "B", 1) g.add_edge("A", "C", 1) g.add_edge("B", "D", 1) g.add_edge("B", "E", 1) g.add_edge("B", "A", 1) g.add_edge("C", "F", 1) g.add_edge("C", "A", 1) g.add_edge("D", "B", 1) g.add_edge("E", "B", 1) g.add_edge("F", "C", 1) g.add_edge("F", "G", 1) g.add_edge("G", "F", 1) print("Кратчайшие пути от вершины A:") bfs_shortest_paths(g, "A")