2
$\begingroup$

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:

Prim's algorithm simple instance

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Algorithms" in my opinion is the clearest on this subject although they don't give an implementation with priority queues as well as there isn't any visual example of it. I'd like to know if my example of execution is correct. But if it is, then it's different from other examples given just after they explained the PQ approach. See for example CLRS 3rd edition figure 23.5. I'm trying to understand the way the solution is produced incrementally. It looks like to me that a Prim implementation based on PQ makes something different from execution examples I've seen that rely on meta algorithm. $\endgroup$ – kentilla Dec 20 '15 at 9:56
  • $\begingroup$ @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? $\endgroup$ – hengxin Dec 20 '15 at 12:50
  • $\begingroup$ @kentilla Also see my answer to another question that you are interested in. $\endgroup$ – hengxin Dec 20 '15 at 13:12
  • $\begingroup$ 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. $\endgroup$ – kentilla Dec 22 '15 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.