I'm trying to find a minimum spanning tree for this graph below using Krusal's and Prim's algorithm. This is what I got for each algorithm:

Krusal: visited= {(ck),(kf),(ib),(bf),(da),(ig),(ae),(di),(ah),(kg),(al),(ej)}. Total Weight=81

Prim: visited={(ck),(kf),(bf),(ib),(ig),(di),(da),(ae),(ah),(al),(ej),(fl)}. Total Weight=89

I know that the total weight should be the same, but they are not the same. Could you guys help me out? Thanks!

enter image description here

  • 1
    $\begingroup$ You have a cycle in Prim case: (fb),(bi),(id),(da),(al),(lf) $\endgroup$ – Virtuoz Jul 18 '15 at 16:41
  • 1
    $\begingroup$ You have a cycle in Kruscal case: (kf),(fb),(bi),(ig),(gk) $\endgroup$ – Virtuoz Jul 18 '15 at 16:49
  • $\begingroup$ That is not a cycle in Krusal. $\endgroup$ – Miriam Jul 19 '15 at 2:46

Your Answer

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

Browse other questions tagged or ask your own question.