Что делает: ищет MST в взвешенном неориентированном связном графе (похож на алгоритм Дейкстры)

Общая идея:

Помечаем расстояния равными бесконечности. Начнём с произвольной вершины. Рассматривая смежные ей вершины, находим ту, расстояние до которой является минимальной. Добавляем это ребро в MST. Теперь, уже от двух вершин, ищем следующую вершину с кратчайшим расстоянием, и так до тех пор, пока не найдём MST

Реализация:

// псевдокод писала Я так что чекните если что не так!

int main() {
	for u из G(V) do 
		u.distance = INF // указываем начальные расстояния как бесконечность
	create PriorityQueue // создаем приоритетную очередь
	MST.push_back(u)
	Prim(u)
}

void Prim(int u) {
	while (!PriorityQueue.empty()) {
		minEdge = PriorityQueue.extractMin() // вытаскиваем вершину из приоркью
		for v из смежных MST.vertices do { // проходимся по вершинам, смежным
																			// уже добавленным в MST
			if (v == minEdge && u.component != v.component) 
				MST.push_back(v) // если вершинка из другой компоненты
												// и ребро минимальное, добавляем их в MST
		}
	}
}

‼ Особенности алгоритма Прима:

1. жадный алгоритм
2. реализуется на приоритетной очереди (которая реализуется либо на фибоначчиевой куче, либо на двоичной куче)
3. существует модификация, позволяющая на полных графах работать за V^2

Визуализация: этим я займусь чуть попозже