Introduction

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

Алгоритм Прима выращивает дерево наружу из начальной вершины. На каждом шаге он добавляет одно самое дешевое ребро, которое соединяет дерево с вершиной, еще не входящей в него.

Граф является неориентированным и взвешенным, заданным как n (вершины от 0 до n - 1) и edges, плоский массив троек [u0, v0, w0, ...] для неориентированного ребра u - v весом w. Мы начинаем с вершины 0.

Давайте завершим эту серию!