На этом шаге мы начнем реализацию приложения.
Прежде чем разработать метод поиска минимального связующего дерева, создадим функцию, которую сможем использовать для проверки суммарного веса решения. Найденное минимальное связующее дерево будет представлять собой список взвешенных ребер, из которых оно состоит. Сначала мы определим WeightedPath как список WeightedEdge. Затем определим функцию total_weight(), которая принимает список WeightedPath и находит общий вес, получаемый в результате сложения всех весов ее ребер.
from typing import TypeVar, List, Optional from pr55_1 import WeightedGraph from weighted_edge import WeightedEdge from priority_queue import PriorityQueue V = TypeVar('V') # тип вершин в графе WeightedPath = List[WeightedEdge] # псевдоним типа для путей def total_weight(wp: WeightedPath) -> float: return sum([e.weight for e in wp])
На следующем шаге мы рассмотрим алгоритм Ярника.
