Джейсон, я не буду вдаваться в описание того, как реализовать код на Java, но давайте посмотрим на мыслительный процесс, лежащий в основе алгоритма для вашей задачи.
Поскольку ваши вершины классифицированы на три весовые категориимы можем пометить их сравнительными весами следующим образом: Light is 1;Средний 2;Тяжелый - 3. Таким образом, ваши условия поддерживаются.
Далее мы можем использовать алгоритм минимального остовного дерева (MST) Крускала, как обычно, чтобы создать минимальное остовное дерево на неориентированном взвешенном графе.Этот алгоритм является жадным, поэтому он сортирует ребра от легких к тяжелым, выбирает следующее наименьшее ребро до тех пор, пока он не создает цикл, а затем повторяет шаг 2, пока все вершины не будут включены в MST.(См. Ссылку ниже для справки) https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/
Когда речь идет о проверке правильности вашего алгоритма, возможны два случая.
1).Вы можете раскрыть фактические веса ребер в MST и исключенные.Проверьте исключенные ребра и, если при добавлении исключенного ребра в MST это ребро не самое тяжелое в цикле, поменяйте его местами с самым тяжелым ребром.Продолжайте делать это до тех пор, пока все первоначально исключенные ребра не будут исследованы и MST не сохранит свое свойство содержать каждую вершину.2).Вы не можете раскрыть фактические веса любой вершины в графе.В этом случае нет никакого способа даже проверить, что ваш алгоритм создал Минимальное связующее дерево, поэтому ваш алгоритм не сможет проверить сам себя.В любом случае, использование алгоритма Крускала со сравнительными весами создаст остовное дерево, которое очень близко к минимуму, даже не зная фактических весов.