Эти две структуры служат различным целям в алгоритме. Алгоритм Крускала работает, добавляя самое дешевое ребро в каждой точке, которая не образует цикл. С помощью некоторой не особо сложной математики можно показать, что это гарантирует, что результирующее остовное дерево минимально. Интуиция, стоящая за этим, заключается в следующем. Предположим, что алгоритм Крускала не оптимален и что существует более дешевое остовное дерево. Сортируйте все ребра в этом дереве по весу, затем сравните эти ребра в отсортированном порядке с ребрами, выбранными алгоритмом Крускала в отсортированном порядке. Поскольку для противоречия мы предполагаем, что алгоритм Крускала не оптимален, в последовательностях должно быть место, где есть разногласие. Если в этом несогласии алгоритм Крускала имеет более легкий край, чем оптимальное решение, то мы можем сделать оптимальное решение еще лучше, добавив этот край, найдя созданный им цикл, а затем удалив самый тяжелый край в цикле. Это ребро не может быть ребром, которое мы только что добавили, потому что в противном случае это создало бы цикл в MST, создаваемый алгоритмом Крускала, и алгоритм Крускала никогда не добавляет ребро, которое создает цикл. Таким образом, это означает, что алгоритм Крускала, должно быть, отклонился от оптимального решения, не добавляя некоторого светлого края. Но единственная причина, по которой алгоритм Крускала пропускает ребро, состоит в том, что он создает цикл, а это означает, что в оптимальном MST должен быть цикл, что также является противоречием. Это означает, что наше предположение было неверным и алгоритм Крускала должен быть оптимальным.
Надеюсь, это мотивирует, почему алгоритму Крускала нужна куча и структура объединения. Нам нужна куча, чтобы мы могли вернуть все ребра в отсортированном порядке. Если мы не посетим края в этом порядке, то вышеприведенное доказательство сломается, и все ставки будут сняты. Интересно, что на самом деле вам не нужна куча; вам просто нужен способ посетить все края в отсортированном порядке. Если вы хотите, вы можете просто сбросить все ребра в гигантский массив, а затем отсортировать массив. Это не меняет время выполнения алгоритма в случае двоичной кучи, если вы используете быструю сортировку.
Структура объединения-поиска немного сложнее. В каждой точке алгоритма Крускала вы должны знать, будет ли добавление ребра создавать цикл на графике. Один из способов сделать это - сохранить структуру, которая отслеживает, какие узлы уже связаны друг с другом. Таким образом, при добавлении ребра вы можете проверить, подключены ли конечные точки. Если они есть, то край будет образовывать цикл и должен игнорироваться. Структура объединения-поиска - это способ эффективного сохранения этой информации. В частности, его две операции - объединение и поиск - соответствуют соединению двух разных групп узлов, которые ранее не были связаны, как это было бы в случае, если вы добавили ребро, которое связывало два дерева, содержащиеся в разных частях пролета. лес. Шаг поиска дает вам возможность проверить, подключены ли уже два узла; Если это так, вы должны пропустить текущее ребро.
Надеюсь, это поможет!