Я думаю, что алгоритм Крускала всегда найдет оптимальное решение.Он даже работает с графиком с отрицательной стоимостью ребра.Существует доказательство оптимальности жадного алгоритма Крускала из учебника, названного Разработка алгоритма : рассмотрим любое ребро e = (v, w), добавленное алгоритмом Крускала, и пусть S будет множеством всех узлов, к которымУ v есть путь в момент перед добавлением e.Ясно, что v ∈ S, но w ̸∈ S, поскольку добавление e не создает цикл.Более того, ни одно ребро от S до V - S еще не встречалось, поскольку любое такое ребро можно было бы добавить без создания цикла и, следовательно, было бы добавлено алгоритмом Крускала.Таким образом, e является самым дешевым ребром с одним концом в S, а другой в V - S, поэтому он принадлежит каждому минимальному остовному дереву.Итак, если мы можем показать, что выходные данные (V, T) Алгоритма Крускала на самом деле являются остовным деревом G, то мы будем готовы.Ясно, что (V, T) не содержит циклов, поскольку алгоритм явно разработан, чтобы избежать создания циклов.Кроме того, если бы (V, T) не были связаны, то существовало бы непустое подмножество узлов S (не равное всем V), так что не было ребра от S до V -S.Но это противоречит поведению алгоритма: мы знаем, что поскольку G подключен, между S и V - S есть хотя бы одно ребро, и алгоритм добавит первое из них, с которым он сталкивается.