BFS.py - master - anz/AAB_algorithms

BFS.py
73 строки3 KB
anz
домашнее задание по графам
07 июн 2025, 21:23
07 июн 2025, 21:23f3d2473
from collections import defaultdict
from collections import deque

class Graph:
    def __init__(self):
        self.vertices = set()
        #hashmap где ключи вершины, а значение list из туплей.например,'A':[(B,2), (C, 6)]
        self.edges = defaultdict(list)
    def add_vertex(self, vertex):
        self.vertices.add(vertex)
    def add_edge(self, source, destination, weight):
        self.vertices.add(source)
        self.vertices.add(destination)
        self.edges[source].append((destination, weight))
    def get_neighbours(self, vertex):
        return self.edges[vertex]
def bfs_shortest_paths(graph, start):
    distances = {vertex: float('infinity') for vertex in graph.vertices}
    predecessors = {vertex: None for vertex in graph.vertices}
    distances[start] = 0

    queue = deque([start]) #Создаём очередь и кладём в неё стартовую вершину
    while queue:
        # Извлекаем вершину из начала очереди
        current = queue.popleft()
        # Перебираем всех соседей текущей вершины (игнорируем вес ребра)
        for neighbour, _ in graph.get_neighbours(current):
            if distances[neighbour] == float('infinity'):
                distances[neighbour] = distances[current] + 1
                predecessors[neighbour] = current
                queue.append(neighbour)

    # Возвращаем словарь предков для восстановления путей
    return predecessors

def reconstruct_path(predecessors, start, end):
    path = []
    current = end
    while current is not None:
        path.append(current)
        # Переходим к предшественнику
        current = predecessors[current]
    # Разворачиваем путь, чтобы он шёл от start к end
    path.reverse()
    # Если путь действительно начинается с start, возвращаем его
    if path[0] == start:
        return path
    else:
        # Если end недостижим, возвращаем пустой список
        return []

#тест
graph = Graph()
graph.add_edge('St', 'A', 5)
graph.add_edge('St', 'D', 13)
graph.add_edge('St', 'E', 3)
graph.add_edge('A', 'D', 6)
graph.add_edge('A', 'B', 1000)
graph.add_edge('B', 'C', 5)
graph.add_edge('D', 'B', 15)
graph.add_edge('D', 'C', 3)
graph.add_edge('D', 'E', 100)

start_vertex = 'St'
predecessors = bfs_shortest_paths(graph, start_vertex)

print(f"Кратчайшие пути от вершины {start_vertex}:")
for vertex in graph.vertices:
    path = reconstruct_path(predecessors, start_vertex, vertex)
    if path:
        print(f"До {vertex}: путь = {path}")
    else:
        print(f"Вершина {vertex} недосягаема")