Алгоритм Прима

O(V2) int prim(vector<vector<Edge>> &graph) { vector<bool> visited(graph.size()); vector<int> dist(graph.size(), 1e9); dist[0] = 0; int mstWeight = 0; for (int i = 0; i < graph.size(); i++) { int nearestV = -1; for (int v = 0; v < graph.size(); v++) if (!visited[v] && (nearestV == -1 || dist[v] < dist[nearestV])) nearestV = v; visited[nearestV] = true; mstWeight += dist[nearestV]; for (auto &[from, to, weight] : graph[nearestV]) if (dist[to] > weight) dist[to] = weight; } return mstWeight; } Полностью аналогично реализации Дейкстры за O(V2). Единственная разница — в качестве расстояния до вершины используется длина не всего пути, а последнего ребра.

O(ElogV) int prim(vector<vector<Edge>> &graph) { vector<bool> visited(graph.size()); vector<int> dist(graph.size(), 1e9); set<pair<int, int>> unvisited; dist[0] = 0; unvisited.insert({ dist[0], 0 }); int mstWeight = 0; while (!unvisited.empty()) { int nearestV = unvisited.begin()->second; unvisited.erase(unvisited.begin()); visited[nearestV] = true; mstWeight += dist[nearestV]; for (auto &[from, to, weight] : graph[nearestV]) { if (!visited[to] && dist[to] > weight) { unvisited.erase({ dist[to], to }); dist[to] = weight; unvisited.insert({ dist[to], to }); } } } return mstWeight; } Почти аналогично реализации Дейкстры за O(ElogV). В качестве расстояния до вершины используется длина не всего пути, а последнего ребра. В отличие от Дейкстры, использование visited обязательно (контртест — 1 2 2, 2 3 1).

Ссылки

• e-maxx.ru — Алгоритм Прима
• neerc.ifmo.ru/wiki — Алгоритм Прима
• brestprog.neocities.org — Минимальное остовное дерево. Алгоритм Прима. Алгоритм Крускала)
• informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 8
• algs4.cs.princeton.edu/lectures — 4.3 Minimum Spanning Trees
• VisuAlgo — Minimum Spanning Tree
• CodeLibrary — Prim's algorithm in O(V^2)
• CodeLibrary — Prim's algorithm in O(ElogV)
• Algos — Minimum spanning tree using Prim algorithm