3
$\begingroup$

I'm trying to find an efficient algorithm that will find me the minimum spanning tree of an undirected, weighted graph of this particular form:

enter image description here

My idea was a recursive solution: Suppose the algorithm recieve the graph with n as a parameter,

if n==2 then:
    take the lower cost path between vo-->v1-->v2 and v0-->v2
if n==1 then:
    take the lower cost path between v0-->v2-->v1 (if v2 exists) and v0-->v1
else:
    - recursivly call the algorithm for n-1
    - take the lower cost edge between v0-->vn and v(n-1)-->vn

I'm really not sure wheather this algorithm is correct, i was trying to prove this by induction and got a bit stuck at the base, which got me thinking maybe the algorithm is flawed.

Any suggestions would be much appreciated.

$\endgroup$
  • 2
    $\begingroup$ There are (very) efficient algorithms for finding the MST of any graph; why are these not enough? By the way, your graph is known as a fan: it is a path on n vertices with a dominating vertex added. $\endgroup$ – Juho Jan 22 '17 at 9:11
  • $\begingroup$ I'm thinking maybe because of this special form I might find a better algorithm than kruskal and prim. $\endgroup$ – wannabe programmer Jan 22 '17 at 9:35
  • $\begingroup$ You could start by making a list of all spanning trees. How do they look? $\endgroup$ – Yuval Filmus Jan 22 '17 at 9:59
  • $\begingroup$ I'm not sure how to answer this question... $\endgroup$ – wannabe programmer Jan 22 '17 at 10:46
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Jan 22 '17 at 21:46
2
$\begingroup$

No, that recursive algorithm is wrong. It was a nice attempt to improve established algorithms on specialized graphs, though.

Here is a counterexample with $n=3$. All edges weigh 2 except that the rightmost two edges, $v_0\rightarrow v_3$ and $v_2\rightarrow v_3$ weigh 1. The recursive algorithm will pick only one edge from the rightmost two edges while an MST must include both of them.

By the way, I cannot understand clearly the description of the algorithm in the case of $n=1$ and in the case of $n=2$. Fortunately (or unfortunately), that does not affect my answer since my counterexample depends only on the "else" clause of the algorithm, which is described clearly.

$\endgroup$

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.