Нахождение минимального остовного дерева графа с использованием алгоритма Крускала

Question

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

Я нашелминимальное остовное дерево с использованием алгоритма Прима. Вот моя попытка .

Мне трудно найти минимальное остовное дерево, используя алгоритм Крускала.Я видел много видео, касающихся алгоритма графов Крускала, но в итоге получил тот же граф, что и алгоритм Прима.

Может кто-нибудь показать мне, как найти минимальное остовное дерево графа с помощью алгоритма Крускала.

Answer 1

Примы и Крускалы всегда дадут вам один и тот же ответ, если все ребра графа имеют разные веса, поскольку существует только одно минимальное связующее дерево.Для графа, имеющего много ребер с одинаковыми весами, алгоритмы могут дать вам другой ответ, но не всегда.Зависит от того, как узлы исследуются в реализации.В этом графе может быть много разных мин-охватывающих деревьев.

Поскольку у вашего графа все отличающиеся веса ребер, вы всегда получите один и тот же ответ.