/
ariadna
/
AlgoritmStructure_Ari
Обзор
Документация
Войти
/
ariadna
/
AlgoritmStructure_Ari
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
Prima
54 строки
1 KB
ariadna
create Prima
07 июн 2025, 13:16
07 июн 2025, 13:16
fa81a43
Код
Авторство
О чём код?
from graphNEOR import Graph import heapq def prim_mst(graph): visited = set() pq = [] mst_edges = [] total_weight = 0 start_vertex = next(iter(graph.vertices)) visited.add(start_vertex) for neighbour, weight in graph.get_neighbours(start_vertex): if neighbour not in visited: heapq.heappush(pq, (weight, start_vertex, neighbour)) while len(visited) < len(graph.vertices) and pq: weight, source, destination = heapq.heappop(pq) if destination in visited: continue mst_edges.append((source, destination, weight)) total_weight += weight visited.add(destination) for neighbour, edge_weight in graph.get_neighbours(destination): if neighbour not in visited: heapq.heappush(pq, (edge_weight, destination, neighbour)) return mst_edges, total_weight graph = Graph(directed = False) graph.add_edge('A', 'B', 7) graph.add_edge('A', 'D', 3) graph.add_edge('B', 'C', 10) graph.add_edge('C', 'D', 4) graph.add_edge('C', 'E', 6) graph.add_edge('C', 'F', 12) graph.add_edge('D', 'E', 1) graph.add_edge('D', 'F', 2) graph.add_edge('E', 'F', 8) graph.add_edge('F', 'G', 5) print(prim_mst(graph) ) # выводит это : ([('C', 'D', 4), ('D', 'E', 1), ('D', 'F', 2), ('D', 'A', 3), ('F', 'G', 5), ('A', 'B', 7)], 22)