Прим и Краскал: один граф, разный порядок

Интерактивное сравнение: https://grundyjs.ru/algorithms/mst-comparison/?utm_source=rutube&utm_medium=social&utm_campaign=mst_comparison&utm_content=horizontal Сравниваем два алгоритма на одном неориентированном взвешенном графе. Прим растит одно дерево: каждый раз выбирает самое дешёвое ребро между уже присоединёнными вершинами и остальным графом. Краскал рассматривает рёбра всего графа по возрастанию веса и соединяет разные компоненты, пропуская циклы. Прим от A выбирает A—C = 2, C—B = 1, C—E = 5 и E—D = 2. Краскал выбирает B—C = 1, A—C = 2, D—E = 2 и C—E = 5; A—B = 4 пропускает, поскольку его концы уже соединены через C. После третьего принятого ребра у Прима сумма 8, у Краскала — 5. Это промежуточные состояния: в конце оба получают четыре ребра и общую стоимость 10. Синий — Прим, зелёный — Краскал. Общие рёбра показаны параллельными цветными линиями. Краскал временно строит несколько отдельных деревьев. Это сравнение порядка выбора, а не замер скорости: синхронные фазы анимации не равны времени работы алгоритмов. Минимальный остов всей сети и кратчайшие пути от старта — разные задачи. В интерактивном примере можно менять граф, веса и старт Прима, проходить сравнение по шагам, поделиться ссылкой на свой граф и сохранить анимацию. Нулевые и отрицательные веса допустимы; в несвязном графе оба алгоритма строят минимальный остовный лес. Авторская озвучка, без музыки. #алгоритмы #Прим #Краскал #графы #программирование