# 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| < |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.

• @kentilla execution examples I've seen that rely on meta algorithm: We can tell if an execution is valid only when according to some concrete instance of the meta-algorithm, such as Kruskal's algorithm or Prim's algorithm. Your example execution for Prim's algorithm is not clear to me: what do the bold/dotted lines mean? what does UPDATE mean? Commented Dec 20, 2015 at 12:50
• There is a $\pi$ attribute for every node in the graph, that represents parents in the tree you are building. So I used bold lines for edges costructed this way, i.e. to display $(u, u.\pi)$ couples. Dotted lines are graph edges that are not eligible to become part of the MST, since there isn't any $(u, u.\pi)$ couple for them. As long as pq is consumed, such $\pi$ attribute may be overwritten, this is what I mean for update (this should be more clear considering a parallelism with Dijkstra behaviour). Anyway i tried to explain it better in the other related question. Thanks for your hints. Commented Dec 22, 2015 at 17:32