Алгоритм "Алгоритм Крускала"

Алгоритм Крускера

Алгоритм Крускала, как и алгоритм Прима, представляет собой алгоритм нахождения минимального остовного дерева, но реализация алгоритма отличается: он находит минимальное остовное дерево, располагая веса в порядке возрастания дерева.

Шаги алгоритма Крускера

1. Отсортировать все ребра в исходном графе по весу от меньшего к большему.

2. Начиная с ребра с наименьшим весом, если две вершины, соединенные этим ребром, не находятся в одном связном ребре графа, запишите вершину как выбранную.

3. Повторяйте шаг 2, пока все узлы в графе не будут связаны, и не будет найдено минимальное остовное дерево связного графа.

Временная сложность алгоритма Крускера

Предположим, у нас есть V для количества вершин в графе и E для количества ребер в графе. Средняя временная сложность.

Пример алгоритма Крускера

Найдите минимальное остовное дерево взвешенного связного графа, используя алгоритм Крускера.

Путем сортировки весов всех ребер в графе минимальный вес ребра AD равен 5, и он выделяется.

Затем следующее ребро с наименьшим весом — это FH с весом 6, которое выделяется. (Будьте осторожны, чтобы не образовать кольца)

Тогда следующее ребро с наименьшим весом имеет два AB и EH, а вес равен 7. Произвольно выбираем ребро AB и подсвечиваем его. (Будьте осторожны, чтобы не образовать кольца)

Затем следующее ребро с наименьшим весом — это EH, которое имеет вес 7 и подсвечивается. (Будьте осторожны, чтобы не образовать кольца)

Тогда следующим ребром с наименьшим весом будет HG с весом 8, и оно будет выделено. (Будьте осторожны, чтобы не образовать кольца)

Последнее ребро с наименьшим весом — DE с весом 9 и выделено. Теперь все вершины в графе связаны, красное связное ребро является минимальным остовным деревом, а сумма весов минимального остовного дерева равна 42.

Примечание. Для ребер с одинаковым весом мы можем произвольно выбрать ребро, но выбранное ребро не может образовать кольцо с предыдущим ребром. Если ребро с наименьшим весом образует кольцо с выбранным ребром, пропустите текущее ребро и перейдите к следующему ребру с наименьшим весом.

Суммировать

Алгоритм Крускелла, как и алгоритм Прима, представляет собой алгоритм нахождения минимального остовного дерева.

Сравнивая два алгоритма, можно сказать, что алгоритм Крускала в основном разработан для ребер, и его эффективность очень высока, когда число ребер мало, поэтому он имеет большие преимущества для разреженных графов; в то время как алгоритм Прима предназначен для плотных графов, то есть очень больших количество ребер.Вещи будут лучше.

PS:
Чистые горы и чистые воды начинаются с пыли, а знания ценнее усердия.
У меня есть вино, у тебя есть история?
Публичный аккаунт WeChat: "болтать".
Добро пожаловать в чат и поговорим о коде.