Prim's algorithm: difference between brute force and PQ approaches I'm trying to figure out the different way we obtain an MST with a brute force Prim's algorithm compared to the optimized version based on priority queues.

Given a graph $G=(V,E)$, the former can be stated as in Dasgupta et al.:

X = {}
while(|X| &lt; |V-1|)
  pick a subset S of V for which X has no edges between S and V-S
  let 'e' be the minimum weight edge in E between S and V-S
  X = X union {e}


It uses blue rule and builds the tree edge by edge: at the end you have the MST of the whole graph, until then $X$ is just incomplete. If we use a brute force approach, running time is $O(|V|\cdot |E|)$.

As we know, better running time is obtained mantaining a priority queue that we use to find the cheaper edge incident to the tree that we build on a step by step basis. Anyway i think that this more than just optimization, since solution with this last approach is built incrementally. 

Infact, if with brute force you have a tree built edge by edge considering from the beginning the whole graph, with priority queues you instead discover nodes incrementally: at each step you have a valid MST of a subproblem. As long as the algorithm proceeds, every node is discovered and priority queue becomes empty. At this point the MST has grown to be the solution of the whole graph. I can summarize with the following simple example:



You start from node $A$, and edges to $B$ and $C$ are immediately discovered. They become part of the tree. Anyway tree changes as long as new nodes are discovered (see UPDATE label in the picture). With brute force you don't have anything similar.

Please, let me know if i'm mistaken or if my reasoning is not complete.
First, the psuedo-code given is not intended for brute force Prim's algorithm. It is a meta-algorithm for MST. Quoted from the beginning of Section 5.1.5 of "Algorithms":


  What the cut property tells us in most general terms is that any algorithm conforming to the following greedy schema is guaranteed to work.


Both Kruskal's algorithm based on disjoint sets and Prim's algorithm based on priority queues are instances of the meta-algorithm.



As for your other questions:


  "If we use a brute force approach, running time is O(|V|⋅|E|)."


It does not make much sense to discuss about the time complexity of a meta-algorithm.


  "Anyway I think that this more than just optimization, since solution with this last approach is built incrementally."


The greedy meta-algorithm for MST is incremental. And both Kruskal's algorithm and Prim's algorithm are incremental.