Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

LunaticPriest's blog

By LunaticPriest, history, 12 months ago, In English,

Prim's algorithm requires a binary heap. At first, I thought I could easily use a priority queue, but it turns out that I have to reduce the weights of vertices in the priority queue, but it takes O(n) to find the vertex and modify its weight. A min-heap has the ability to reduce the weights of the vertices but it takes a lot of time to code it up, so it isn't useful for competitions. How to reduce the weight of the vertex with less complexity?

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If you want a min heap, just use priority_queue<int, vector<int>, greater<int> > pq; instead of just priority_queue<int> pq

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I am aware of that method, what I'm actually concerned about is the complexity of finding the vertex and changing its weight.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Couldn't you just change the weight and rerun Prim for O(n lg n)?

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        If each weight change costs me O(n), in the worst case I believe it will change a weight number of edges times, so the complexity becomes something like O(V*E) which can also be O(V^3), but the algorithm should be O(nlogn).

        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think you are a little confused here, the algorithm will work in the same O(E logV) once you have the correct graph, so the problem is not the algorithm itself but you need to create a different graph.

»
12 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Why do you have to reduce the weight of edges in the priority queue?

»
12 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

On an unrelated note, why are you trying to implement Prim's algorithm? For homework? For practice? If you do not need to do it for official reasons, I suggest that you use kruskal's algo instead. It is much much easier than prim's algo and is better suited for programming contests.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think prim has some applications with counting number of trees in some problems (this is just a vague memory, so I can't provide details).

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You have several options:

  1. Instead of changing the weight of the vertex insert several copies of the same vertex on the priority queue (PQ). Each vertex will be inserted in the PQ at most its degree, hence you will need to push/pop $$$O(E)$$$ times from the PQ. (Note if you do this you will only process each vertex once, the first time). Now the complexity will be $$$O(E \log E)$$$ but since $$$E$$$ is at most $$$V^2$$$ we got same complexity $$$O(E \log V)$$$. (This is not the best complexity you can achieve using Prim).

  2. Use a set instead of a PQ. When you want to modify an element just delete it and insert the modified value again. Time complexity is the same using set and PQ, but PQ is significantly faster and you should prefer it if you have that option.

  3. Use Kruskal instead.

I find Kruskal easier to implement as pointed by LanceTheDragonTrainer, I only implement Prim when the graph is dense, and instead of using a PQ you can use and array. Updates and finding minimum is done in linear time. Overall complexity is $$$O(V^2)$$$ and code is even simpler than Kruskal.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

we can use std::set in C++ (which are implemented via red-black trees). std::priority_queue has a limitation that when an edge [u, v, w] is relaxed, we insert the updated information {w(new), v}, but stale information {w(old), v} still remains in the priority queue. so instead we can use std::set which can relax( or update) the edge already present in the set in O(logE) time. here is the implimentation

const int INF = 1000000000;
struct Edge {
    int w = INF, to = -1;
    bool operator<(Edge const& other) const {
        return make_pair(w, to) < make_pair(other.w, other.to);
    }
};

void prims(vector<vector<Edge>> &adj,int &n) {
    int total_weight = 0;
    vector<Edge> min_e(n);
    min_e[0].w = 0;
    set<Edge> q;
    q.insert({0, 0});
    vector<bool> selected(n, false);
    for (int i = 0; i < n; ++i) {
        if (q.empty()) {
            cout << "No MST!" << endl;
            exit(0);
        }

        int v = q.begin()->to;
        selected[v] = true;
        total_weight += q.begin()->w;
        q.erase(q.begin());

        if (min_e[v].to != -1) // if to is set
            cout << v << " " << min_e[v].to << endl;

        for (Edge e : adj[v]) {
            if (!selected[e.to] && e.w < min_e[e.to].w) {
                q.erase({min_e[e.to].w, e.to});
                min_e[e.to] = {e.w, v};
                q.insert({e.w, e.to});
            }
        }
    }

    cout << total_weight << endl;
}