Как использовать union-find, minheap, Kruskal's и алгоритм сортировки для создания связующего дерева с минимальной стоимостью? (C++)
Я прошу прощения, если этот вопрос является немного широким, но я испытываю затруднения, пытаясь понять, как я создал бы остовное дерево минимальной стоимости. Это в C++, если это вообще имеет значение.
Из того, что я понимаю, вы бы использовали Kruskal's, чтобы выбрать минимальные ребра стоимости для построения связующего дерева. Я думаю о том, чтобы считать ребра в мини-кучу, и таким образом вы можете удалить сверху, чтобы получить ребро с минимальными затратами.
Пока что мне удалось реализовать только minheap и наборы для объединения-поиска, я до сих пор не уверен в цели объединения-поиска и алгоритма сортировки для создания связующего дерева.
Буду очень признателен за любые советы.
РЕДАКТИРОВАТЬ: я не ограничен объединение найти, minheap, kruskals и алгоритм сортировки, и я не обязан делать какие-либо. Это были только пункты, предложенные инструктором.
1 ответ
Эти две структуры служат различным целям в алгоритме. Алгоритм Крускала работает, добавляя самое дешевое ребро в каждой точке, которая не образует цикл. Используя некоторую не особенно сложную математику, можно показать, что это гарантирует, что результирующее остовное дерево будет минимальным. Интуиция, стоящая за этим, заключается в следующем. Предположим, что алгоритм Крускала не оптимален и что существует более дешевое остовное дерево. Сортируйте все ребра в этом дереве по весу, затем сравните эти ребра в отсортированном порядке с ребрами, выбранными алгоритмом Крускала в отсортированном порядке. Поскольку для противоречия мы предполагаем, что алгоритм Крускала не оптимален, в последовательностях должно быть место, где есть разногласие. Если в этом разногласии алгоритм Крускала имеет более легкий край, чем оптимальное решение, то мы можем сделать оптимальное решение еще лучше, добавив этот край, найдя созданный им цикл, а затем удалив самый тяжелый край в цикле. Это ребро не может быть ребром, которое мы только что добавили, потому что в противном случае это создало бы цикл в MST, создаваемый алгоритмом Крускала, и алгоритм Крускала никогда не добавляет ребро, которое создает цикл. Таким образом, это означает, что алгоритм Крускала, должно быть, отклонился от оптимального решения, не добавляя некоторого светлого края. Но единственная причина, по которой алгоритм Крускала пропускает ребро, состоит в том, что он создает цикл, а это означает, что в оптимальном MST должен быть цикл, что также является противоречием. Это означает, что наше предположение было неверным и алгоритм Крускала должен быть оптимальным.
Надеюсь, это мотивирует, почему алгоритму Крускала нужна куча и структура объединения. Нам нужна куча, чтобы мы могли вернуть все ребра в отсортированном порядке. Если мы не посетим края в этом порядке, то вышеприведенное доказательство не работает и все ставки отменены. Интересно, что на самом деле вам не нужна куча; вам просто нужен способ посетить все края в отсортированном порядке. Если вы хотите, вы можете просто сбросить все ребра в гигантский массив, а затем отсортировать массив. Это не меняет время выполнения алгоритма в случае двоичной кучи, если вы используете быструю сортировку.
Структура объединения-поиска немного сложнее. В каждой точке алгоритма Крускала вы должны знать, будет ли добавление ребра создавать цикл на графике. Один из способов сделать это - сохранить структуру, которая отслеживает, какие узлы уже связаны друг с другом. Таким образом, при добавлении ребра вы можете проверить, подключены ли конечные точки. Если они есть, то край будет образовывать цикл и должен игнорироваться. Структура поиска профсоюзов является способом эффективного сохранения этой информации. В частности, две его операции - объединение и поиск - соответствуют действию соединения двух отдельных групп узлов, которые ранее не были связаны, как в случае, если вы добавили ребро, которое соединяло два дерева, содержащиеся в разных частях остовного участка. лес. Шаг поиска дает вам возможность проверить, подключены ли уже два узла; Если это так, вы должны пропустить текущее ребро.
Надеюсь это поможет!