Получите наименьшее преимущество!
Краскала - это алгоритм минимального остовного дерева. Подход состоит в том, чтобы многократно выбирать наименьшее ребро, пока еще не создан цикл с остовным деревом.
Давайте рассмотрим это подробно на примере, прежде чем приводить этот важнейший код Swift (см. Суть в конце этой статьи).
Предварительные требования:
- Некоторый опыт работы с деревьями и графами (поможет немного теории графов!)
- Замыкания (один используется для определения минимального края в приведенном ниже коде)
Терминология
Вершина: точка пересечения или разветвления ребер (также известная как узел, множественное число вершин).
Ребра: связи между вершинами, содержащие вес.
Путь: набор ребер и узлов между вершинами.
График: набор узлов и ребер.
Связующее дерево: связующее дерево - это подмножество графа, все вершины которого покрыты минимально возможным количеством ребер.
Мотивация
Алгоритм Краскала - это жадный подход к поиску минимального остовного дерева. Это облегчает сортировку, и это определенно то, о чем начинающий студент, изучающий информатику, должен что-то знать.
Связующее дерево
Остовное дерево - это подмножество рассматриваемого графа, все вершины которого соединены минимальным количеством ребер.
По определению у остовных деревьев не может быть циклов.
Полный неориентированный граф может иметь максимальное количество остовных деревьев n ^ n-2, где n - количество узлов.
Алгоритм
- Создайте набор всех ребер в минимальном остовном дереве
Пока набор не пустой, а остовное дерево не полное
- Нарисуйте край наименьшего веса, убрав его из набора
- Продолжайте добавлять ребра с минимальным весом, пока они не образуют цикл (замкнутый путь)
Примечания по реализации для использования матрицы
Мы можем подсчитать количество ребер, и, поскольку в остовном дереве всегда будет n - 1 ребра, мы знаем, что нужно взять это количество ребер всего.
Важнейшей частью этого является функция обеспечения того, чтобы наименьшее возможное ребро не только не было наименьшим ребром, но и два узла, которые будут задействованы, не оба уже находятся в одном наборе.
Например (на диаграмме ниже) после выбора первых двух ребер (0-1 и 0-2), следующим самым маленьким ребром будет 1– 2.
Однако, если бы это было выбрано, у нас был бы цикл.
Чтобы узнать это программно, мы создали массив parent.
Изначально ни один узел не имеет родителя, поэтому фактически указывает на себя:
parent = [0,1,2,3,4]
Край 1:
0 - ›2 со стоимостью 1
parent = [2,1,2,3,4]
то есть 0 теперь имеет 2 в качестве родительского (поэтому первый элемент в родительском массиве теперь равен 2, показывая, что элемент 0 теперь имеет 2 в качестве родительского элемента)
Край 2:
Если бы мы попытались выбрать то же самое ребро, что и раньше (0 - ›2), родительским элементом обоих узлов был бы один и тот же узел (2), что указывало бы на цикл. по определению.
Итак, мы выбираем самый нижний край без того же родителя
0 - ›1 со стоимостью 2
parent = [2,1,1,3,4]
Край 3:
Если бы мы хотели выбрать ребро 1 - ›2, родители обоих узлов совпадают! Как и раньше, выбор этого края создаст цикл.
В результате мы выбираем следующий наименьший край, от 3 до ›4 со стоимостью 5.
parent = [2,4,1,4,4]
Родительский код поиска:
Из-за того, как работает создание общего родителя, мы всегда в конечном итоге найдем узел, который является его собственным конечным родителем. В противном случае у нас был бы цикл на графике, и это ситуация, которую мы пытаемся предотвратить.
Создание общего родителя
С двумя узлами мы делаем конечного родителя для первого узла вторым узлом. Это дает нам следующую ситуацию:
Код
Этот код можно сделать намного быстрее, если использовать реализацию графа в виде матрицы смежности, но разработчику предстоит выбрать лучший способ для конкретного использования.
Хотите связаться? Воспользуйтесь ссылкой здесь:
