Как мне приступить к решению для объединения Kruskal’s

#c #graph #minimum-spanning-tree #kruskals-algorithm

#c #График #минимальное связующее дерево #kruskals-алгоритм

Вопрос:

Я попытался просмотреть график и изменить каждый экземпляр некоторого идентификатора на более новый идентификатор, и это все равно привело к циклу. Что планируется решить для ациклического решения?

Комментарии:

1. Вероятно, вы реализовали это неправильно, если вы все еще получаете цикл после запуска алгоритма. Предполагая, что объединение Крускала должно означать алгоритм Крускала для генерации MST.

Ответ №1:

Вы никогда не должны получать циклы при добавлении новых ребер в алгоритм Крускала. Если вы добавляете ребро, которое соединяет тот же компонент с самим собой, вы пропускаете это ребро. Вы никогда не получите циклов, потому что это не будет минимальное связующее дерево