Алгоритм обратного удаления: начните с графика, содержащего все ребра. Затем несколько раз go через края в порядке убывания веса. Для каждого ребра проверьте, будет ли удаление этого ребра разъединять график; если нет, удалите его.
Как мне доказать, что этот алгоритм вычисляет MST?