How to implement Prim's algorithm on a graph?

Question

Mathematics

We need an implementation of Prim's algorithm on a graph represented by an adjacency list using C++ with an STL priority_queue queue. Actually, the essence of the question is exactly how to implement it, just a piece of code or a step-by-step algorithm without vyrviglazny pseudo-code and mat. abstractions. Or in other words, there is a graph implemented as a list of adjacent vertices. Question: how to implement Prim's algorithm for finding the minimum spanning tree (MST) using the priority queue from the STL (C++)?
Thanks

Answer 1

In fact:

set {int} used; 
vector {list {Edge}} edges; 
vector {Edge} ans;
pr_queue {Edge} next_edges;
used.add(0);
edges.addAll(edges[0]);
while(!next_edges.empty()){
  Edge edge = next_edges.front();
  next_edges.pop();
  if(!used.contains(edges.to)){
    used.add(edges.to);
    ans.add(edge);
    next_edges.addAll(edges[edges.to]);
  }
}

For pr_queue add an edge weight comparator.
This algorithm does a lot of unnecessary actions, but is simple

Answer 2

Look also here http://e-maxx.ru/algo/mst_prim. There are very useful optimizations of the algorithm, they will significantly speed up the trivial solution.

Answer 3

vans239: 1
Nerazumovskiy:
Thank you.