Why do we need a priority queue in Prim Algorithm

Question

As my question says, I want to know why we use the priority queue in Prim Algorithm ? How does this save us from the naive way (yes, I heard about it, but I don’t know why).

I would be very happy if someone could explain the adjacency list step by step. I use the book Cormen.

Pseudocode:

Prim(G,w,r) //what is w (weight?) and r? For each u in V[G] do key[u] ← ∞ // what is key? π[u] ← NIL key[r] ← 0 Q ← V[G] While Q ≠ Ø do u ← EXTRACT-MIN(Q) for each v in Adj[u] if v is in Q and w(u,v) < key[v] then π[v] ← u key[v] ← w(u,v) 

I am thinking of using std :: vector, then std :: make_heap (); as a priority queue for storing ribs.

Answer 1

In the primitive algorithm, there is a step where you should get the "closest" vertex. This step will cost O (N) when using a regular array, but to use a priority queue (for example, a bunch), you only need O (logN)

Therefore, the reason for using the priority queue is to reduce the complexity of the algorithm time (which means that the program is accelerating)

**

Update:

**

Here is a description of the Prim algorithm from Wikipedia . The bold part is the part for finding the nearest peak that I spoke about:

Input: A nonempty connected weighted graph with vertices V and edges E (weights can be negative).

Initialize: Vnew = {x}, where x is an arbitrary node (starting point) from V, Enew = {}

Repeat until Vnew = V: Select an edge (u, v) with a minimum weight such that u is in Vnew and v is not (if there are several edges with the same weight, any of them can be selected) Add v in Vnew and (u, v) so that Enew

Exit: Vnew and Enew describe a minimal spanning tree.

Answer 2

You do not need it. In fact, a naive implementation of the Prim algorithm would be just a linear search for an array of distances to find the next nearest vertex. Dijkstra's algorithm works in exactly the same way.

The reason people use it is because it significantly speeds up the execution time of the algorithm. It deviates from O(V^2 + E) to O(E*log(V)) .

The key to this is the EXTRACT-MIN(Q) function. If you do it naively, this operation will take O(V) . With a bunch, it only takes O(logV) .

Answer 3

Performing this roughly from memory, this may be a bit inconsistent, but it gets the point at:

 class Graph Set<node> nodes; // The set of nodes in the graph MultiMap<Node, Edge> edges; // Map from Node, to a list of weighted edges connected to the node. If it weren't weighted, any spanning tree by definition would be a minimum spanning tree. Graph Prim(Graph input): Graph MST = new Graph(); PriorityQueue<Edge> candidateEdges; Node anyNode = input.pickAnyNodeAtRandom() candidateEdges.putAll(input.edges.get(anyNode)); while MST.nodes.size() < input.nodes.size(): edge = candidateEdges.takeLowest() // THIS IS THE IMPORTANT PART if edge.v1 in MST.nodes and edge.v2 not in MST.nodes: MST.nodes.add(edge.v2) MST.edges.add(edge) candidateEdges.add(edge.v2.edges) 

Basically, at each step of the algorithm you are looking for a minimum edge with one vertex in a partial minimum spanning tree and one vertex not in the tree, and you are going to add an edge to the tree. How do you do this effectively? If you have a way to efficiently arrange all the faces associated with a vertex in your partial spanning tree, you can simply iterate over them until you find an edge with an acceptable vertex.

Without such an ordered data structure, you will have to go through all the candidate faces each time to find the minimum, and not be able to effectively get the minimum.

Answer 4

The primitive algorithm uses two sets - allows you to speak U and V / U.

You start with the root, (the root is the only element in U). You place all the vertices adjacent to it in the queue, with the weight [v] = dist [root, v], where v is adjacent to the root. So, when you exit the queue, you take a vertex (say, u) that has one end at U and ends at V / U and is the smallest with this property. You set its weight, its parent root, etc .... and put all your add-on nodes in the queue. So, now the queue has all the nodes associated with the root, and all the ajdacent nodes from root and all the ajdacent nodes to u with their respective weights. So, when you exit it, you will again get the node from V / U, which is the “closest” to U.

In the implementation, they initially add each vertex to the INFINITY priority queue, but they gradually update weights, as you can see. This is also reflected in the priority queue, guaranteeing the text above.

Hope this helps.