3
$\begingroup$

What was the reason to come up with Chu–Liu/Edmonds' algorithm when the input graph is directed instead of using the Prim's or Krushkal's method for finding Minimum spanning tree ? What cases are not covered in using Prim's algo for finding MST for directed input?

$\endgroup$
7
$\begingroup$

Your question was already asked before it seems, but got no explicit examples. I try to give these here.

First note the question only makes sense if we consider a node $u$, and there exist spanning trees starting with $u$. The algorithms of Prim and Kruskal make choices in a greedy way. Once the choice is made, it will not be reconsidered. We show how this choice will go wrong for certain example.

The left picture has two spanning trees, with weight $6+2$ and weight $6+4$. Starting with node $u$ Prim will consider the two edges $4$ and $6$ and choose the lightest one. Now, only one spanning tree remains, not the best one.

The right picture has three spanning trees, with weight $4+2$, weight $6+1$, and weight $6+4$. Kruskal will choose the lightest edge $1$. Now, only one spanning tree remains, not the best one.

enter image description here

$\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.