1
$\begingroup$

I am trying to address the following claim- "running prim algorithm on a disconnected undirected graph returns minimum spanning forest". I thing that the claim may be false (i.e there might be an example of a disconnected undirected graph so that the prim algorithm doesn't return MSF) but I cannot think of such example.

Also when I look at the algorithm- it seems to me that when we are done with one connectivity component, we'll just extract from Q (a min heap) a vertex that in another connectivity component so it would just work fine. What am I missing?

$\text{MST-PRIM}(G, w, r):$
$\quad\quad\textbf{for }\text{each }u\text{ in }G.\!V$:
$\quad\quad\quad u.key = \infty$
$\quad\quad\quad u.\pi = \text{NIL}$
$\quad\quad r.key = 0$
$\quad\quad Q = G.\!V$
$\quad\quad \textbf{while }Q\not=\emptyset:$
$\quad\quad\quad u = \text{EXTRACT-MIN}(Q)$
$\quad\quad\quad\textbf{for }\text{each } v\in G.\!Adj[u]:$
$\quad\quad\quad\quad\textbf{if }v\in Q\text{ and }w(u, v) < v.key:$
$\quad\quad\quad\quad\quad v.\pi = u$
$\quad\quad\quad\quad\quad v.key = w(u, v)$

The above description is taken from CLRS, chapter Minimum Spanning Trees, where the algorithm will return $\{(v,v.\pi): v\in G\!.V-\{r\}\}$.

$\endgroup$
1
  • 1
    $\begingroup$ Please transcribe the algorithm into text or code environment. Don't forget to give proper attribution to your sources! $\endgroup$
    – Nathaniel
    Jan 14, 2023 at 11:50

1 Answer 1

0
$\begingroup$

It depends on how you/we understand/define what is Prim's algorithm when the given graph is disconnected. You did not missing anything important.

"The most basic form of Prim's algorithm only finds minimum spanning trees in connected graphs.", said by Wikipedia. That most basic form starts with a vertex and only grow edges that connect to the vertices that has been added. Many descriptions of Prim's algorithm such as here on cp-algorithms/, here on programiz and here on javatpoint stick to this simplest form.

However, suppose we consider the pseudocode shown in the question as the definition of Prim's algorithm. Then it will find a minimum spanning forest (MSF) for the given graph, since at the end of the algorithm all vertices will be extracted from queue $Q$ that was initialized with all vertices. Here we assume, of course, that "Extract-Min" will not malfunction when the minimum value of the keys is $\infty$. As you noted, when we are done with one connected component, we'll just extract from $Q$ (a min heap) a vertex that in another connected component. In this sense, the name of the procedure, "MST-Prim" could have been "MSF-Prim". So, you can be correct in asserting "the claim may be false".


In contrast, whatever description is used for Kruskal's algorithm, it will return a minimum spanning forest of the given graph. There is no ambiguity here.

$\endgroup$
2
  • $\begingroup$ Thank you very much! I thought I was going crazy haha. I really appreciate the help! $\endgroup$
    – DR_2001
    Jan 14, 2023 at 13:56
  • $\begingroup$ You are welcome! I had been there, too. $\endgroup$
    – John L.
    Jan 14, 2023 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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