3
$\begingroup$

Suppose we were using a priority queue (PQ) to implement Prim's algorithm. My understanding is that initially the weight of all vertices is set to $\infty$. The weight of the starting vertex is then set to $0$. All of the vertices are then inserted into the PQ.

  1. Does that mean that we can insert the vertices in any order into the PQ?

  2. Given that we can insert the vertices in any order, suppose we have a graph with the following vertices $a$, $b$ and $c$ and the following weights $w(a,b)=1$, $w(a,c)=2$. Once we set a.key = 0 and then extract a from PQ, we have b.key = 1 and c.key = 2. Given the answer to (1) was yes, my understanding would be that in a binary tree representation of the heap, $b$ would now be the root and $c$ would be a child of $b$. However, depending on the order in which the $a$, $b$ and $c$ were added to the heap, $c$ could be either the left or right child of $b$, right?

  3. Suppose now that the graph has vertices $a$, $b$, $c$, $d$ and edges $(a, b)$, $(a, c)$, $(a, d)$. Suppose they were inserted into the heap in the order $a$, $b$, $c$, $d$. The binary tree representation of the heap should then be:
    $a$ is the root, $\operatorname{left}(a) = b$, $\operatorname{right}(a) = c$, $\operatorname{left}(b) = d$

So, that would mean that the parent-child relationships do not correspond to the parent-child relationships in the original graph and they don't have to, right?

$\endgroup$
  • 1
    $\begingroup$ Yes, before you run the algorithm you don't know anything about the vertices (apart from which one is the starting one), so in particular you can't tell them apart. $\endgroup$ – Yuval Filmus Feb 19 '14 at 5:48
  • $\begingroup$ What do you mean by "in any order"? Given a graph, you have to insert the vertices in the order enforced by Prim's algorithm. See an example here. $\endgroup$ – hengxin Feb 19 '14 at 5:51
  • 1
    $\begingroup$ @hengxin you are right about the vertices being added to MST in the order enforced by Prim. I was asking about how the heap for the PQ is being built. Hence, Yval's answer. $\endgroup$ – EggHead Feb 19 '14 at 14:55
  • $\begingroup$ @YuvalFilmus I have added follow up questions based on your answer. Thanks! $\endgroup$ – EggHead Feb 19 '14 at 15:23
1
$\begingroup$
  1. Assuming your PQ is backed by a heap (as you refer to it later). Since the only invariant in a heap is that the parent must be $<$ the children (heap property) you can see there can be no ordering between children of a single parent. A priority queue will always return you the minimal element regardless of order, just think about how $\min$ works: $\min\{1,2,3\}=\min\{2,3,1\}=\min\{3,2,1\}$.

  2. Because a heap is represented in a continous array, you'll have $[b, c]$ after removing $a$ which means that $c$ will always be the left child. Look at the heap image on Wikipedia and notice it's leaning left.

  3. Yes, that's the order they'll be in a usual heap, because all their weights are $\infty$. But any other structure (regardless of insertion order) would be acceptable as long as $a$ is the root, because it wouldn't hurt the heap property.

parent-child relationships [in PQ's heap] do not correspond to the
parent-child relationships in the original graph

That is absolutely correct. Just because your PQ is backed by a heap which encodes a tree you can't assume that the graph structure will have anything to do with the heap tree's structure. Just think about a non-tree graph with cycles and multiple edges between vertices: how would that be reflected in the heap's tree? There isn't even a correspondence with the partial MST.

Another argument: the whole structure correspondence breaks big time as soon as you modify just one key in the heap and sift it to it's place. For example:

     a(0)                            a(0)
   b(∞) c(∞)   --- d.key = 1 -->   d(1) c(∞)
 d(∞)                             b(∞)

even before modifying the key $d$ was the child of $b$ which wasn't true in the graph and is not even reachable. The same is true after modification for the reverse.


The best is to think of a PQ as:

interface PriorityQueue {
    add(node, cost)
    update(node, cost)
    (node, cost) popMin()
}

the fact that it's implemented as a heap shouldn't be of a concern, just assume that the PQ does add and update in $\mathcal{O}(n\log{n})$ and popMin in $\mathcal{O}(1)$ to get quasilinear runtime of Prim's algorithm. Even when you implement it you should separate the algorithm from the PQ implementation.

$\endgroup$
1
$\begingroup$

Prim's algorithm considers edges in increasing cost, and once an edge is added (or not) it isn't considered again, and it's cost isn't changed at all. No need for a priority queue's complications, just sort and be done.

$\endgroup$
  • $\begingroup$ You need to update some edge's costs which breaks the sorting. If you re-sort on every visit you'll get a quadratic algorithm instead of quasilinear. $\endgroup$ – TWiStErRob Jan 14 '16 at 14:47

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.