Алгоритм Прима: минимальное остовное дерево

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