#c #graph #minimum-spanning-tree #kruskals-algorithm
#c #График #минимальное связующее дерево #kruskals-алгоритм
Вопрос:
Я попытался просмотреть график и изменить каждый экземпляр некоторого идентификатора на более новый идентификатор, и это все равно привело к циклу. Что планируется решить для ациклического решения?
Комментарии:
1. Вероятно, вы реализовали это неправильно, если вы все еще получаете цикл после запуска алгоритма. Предполагая, что объединение Крускала должно означать алгоритм Крускала для генерации MST.
Ответ №1:
Вы никогда не должны получать циклы при добавлении новых ребер в алгоритм Крускала. Если вы добавляете ребро, которое соединяет тот же компонент с самим собой, вы пропускаете это ребро. Вы никогда не получите циклов, потому что это не будет минимальное связующее дерево