Как реализовать алгоритм Прима на графе? Нужна реализация алгоритма Прима на графе, представленном списком смежности с помощью C++ с STL-овской priority_queue очередью. Собственно, суть вопроса именно в том, как реализовать, просто кусок кода или пошаговый алгоритм без вырвиглазного псевдокода и мат. абстракций. Или другими словами есть граф, реализованный в виде списка смежных вершин. Вопрос: как с помощью очереди с приоритетом из STL (C++) реализовать Алгоритм Прима для поиска минимального остовного дерева (MST)?
Спасибо

Предыдущий
вопрос Следующий
вопрос

Вот пример реализации алгоритма Прима на графе, представленном списком смежности, с использованием очереди с приоритетом из STL (C++):

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
const int INF = 1e9;
int primsAlgorithm(vector<vector<pair<int, int>>> &adjList) {
int n = adjList.size();
int totalWeight = 0;
vector<bool> visited(n, false);
vector<int> minWeight(n, INF);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, 0});
minWeight[0] = 0;
while (!pq.empty()) {
int u = pq.top().second;
int weight = pq.top().first;
pq.pop();
if (visited[u]) continue;
visited[u] = true;
totalWeight += weight;
for (auto edge : adjList[u]) {
int v = edge.first;
int w = edge.second;
if (!visited[v] && w < minWeight[v]) {
minWeight[v] = w;
pq.push({w, v});
}
}
}
return totalWeight;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> adjList(n);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
adjList[u].push_back({v, w});
adjList[v].push_back({u, w});
}
int totalWeight = primsAlgorithm(adjList);
cout << "Total weight of MST: " << totalWeight << endl;
return 0;
}

В данном коде алгоритм Прима запускается из функции primsAlgorithm, которая принимает список смежности графа. Алгоритм строит минимальное остовное дерево и возвращает его общий вес.

В функции main считывается входные данные (число вершин, рёбер и сами рёбра) и затем вызывается функция primsAlgorithm. Результат выводится на экран.