Альтернативный способ найти минимальную стоимость подключения графа

Question

Я столкнулся с классической проблемой Крускала, где, учитывая неориентированный график и набор весов между ребрами, меня попросили найти минимальную стоимость, необходимую для соединения ребер. Я не был слишком знаком с алгоритмом Крускалса, поэтому придумал собственное решение. Тем не менее, он не дотянул несколько тестовых случаев. Вот алгоритм: 1- Сортировать ребра по весам. Используется приоритетная очередь типа Node.Node состоит из src, dest и weight.

2- Отслеживание посещенных узлов с использованием логического массива размера N, где N - это число узлов.

2- Опрос приоритетной очереди (Снять головку). Если src или dest не посещены, добавьте вес к решению и пометьте их обоих как посещенных.

Может кто-нибудь помочь мне понять, почему этот алгоритм не работает? Логично, что мне кажется, что посещаемый массив должен следить за тем, чтобы не было циклов, так как я добавляю его в решение, только если src или dest не посещаются.

Answer 1

В какой-то момент вам обычно нужно нужно , чтобы добавить ребро в решение с посещением обеих конечных точек. Например, рассмотрим следующий график:

A --1-- B
|
|
3
|
|
C --2-- D

После добавления ребер AB и CD к решению ваш алгоритм откажется добавлять AC, поскольку были посещены как A, так и C.

Алгоритм Крускала отказывается добавлять ребро в решение, если конечные точки уже находятся в одном и том же дереве, что сильно отличается от вашего состояния.