The task uses a function with the Prima algorithm to build a spanning tree of the graph, however, I am told that in the algorithm itself, the selection priority of the next vertex should be done for O (log n), and for me it is done for O (n).

How to remake my algorithm to look for the next vertex for O (log n)?

PS: They say to do with the help of the priority queue, however, I do not understand where to use it here.

Code:

using namespace std; const long long inf = 1001; void My_Prima(vector<vector<pair<int, int>>> const &Vec, const int &n const&m) { vector <int> dista(n, inf); vector <bool> used(n, 0); dista[0] = 0; while (true) { int h = -1; int des = inf; for (int i = 0; i < n; i++) { if (!used[i] && (des >= dista[i])) { h = i; des = dista[i]; } } if (h == -1) { break; } used[h] = true; for (int i = 0; i < Vec[h].size(); i++) { if (!used[Vec[h][i].first]) { dista[Vec[h][i].first] = min(dista[Vec[h][i].first], Vec[h][i].second); } } } long long finsuma = 0; for (int i = 0; i < n; i++) { finsuma += dista[i]; } cout << finsuma; }

    1 answer 1

    Now you use the dista array to search for the next vertex. You should replace it with a priority queue (more precisely, supplement with a queue - since distances will still be needed).

    Instead of the first loop, the item is retrieved from the queue. In the second cycle, instead of updating the distance, the element is put in a queue - or moves in this queue, if it was already there.

    There are two subtleties. First, since the distance to the top can change, the position of the top in the queue must somehow be updated. This requires a mechanism for tracking the position of the top in the queue - which is not in the standard library. Therefore, instead of the priority queue, a tree is often used ( set ), where it is quite easy to find the top.

    To move a vertex in such a queue to a new place, you must first remove it, then update the distance - and finally add it again.

    Secondly, the vertices in the queue must be ordered by distance, which requires a special comparator. But you can do it easier - to store in the queue a couple of numbers, where the first number will be the distance, and the second - the number of the vertex.

    PS

    Council on the design of the code. Constructs of the form pair<int, int> very poorly readable - of them it is not at all clear what each of the components means. It is better to enter your structures - this does not take very many lines of code, and there is much more benefit from this.

     struct edge_data { int end; // Номер конечной вершины ребра int weight; // Вес ребра edge_data (int end, int weight) :end(end), weight(weight) {} }