SOLUTION: Is it B? I want to check my answer.
Which is the cost of the minimum spanning tree of the weighted graph using Kruskal's Algorithm?
A. 28
B. 30
C. 31
D. 40
t
Algebra.Com
Question 1161148: Is it B? I want to check my answer.
Which is the cost of the minimum spanning tree of the weighted graph using Kruskal's Algorithm?
A. 28
B. 30
C. 31
D. 40
the question is provided in the link here: https://i.imgur.com/zzzvcG9.png
Answer by Theo(13342) (Show Source): You can put this solution on YOUR website!
i get 28 using kruskal.
i also used prim and got the same answer.
using kruskal i did the following:
i looked for the link with a weight of 1.
that was link AB.
i then looked for a link with a weight of 2.
that was link DF.
it was not connected to node A or B, so i drew it separate.
i then looked for a link with a weight of 3.
that was link EH.
it was not connected to node A or B or D or F, so i drew it separate.
i then looked for a link with a weight of 4.
that was link HG.
it was connected to node H, so i drew it connected there.
so far my nodes were ABDFEHG
i then looked for a link with a weight of 5.
that was link BG.
it was connected to node B, so i drew it connected there.
i then looked for a link with a weight of 6.
that was link AC.
it was connected to node A so i drew it connected there.
i then looked for a link with a a weight of 7.
that was link CD.
it was connected to node C, so i drew it connected there.
i then looked for a link with a weight of 8.
that was link BD.
it was connected to node B and D forming a cycle (closed loop) so i rejected it.
i then looked for a link with a weight of 9.
that was link CE.
it was connected to node C and E forming a cycle, so i rejected it.
i then looked for a link with a weight of 10.
that was link GF.
it was connected to node G and F forming a cycle, so i rejected it.
i then looked for a link with a weight of 11.
that was link EF.
that was connected to node E and F forming a cycle, so i rejected it.
that was the end of it.
my spanning tree was, starting from node E.
EH with a weight of 3.
HG with a weight of 4.
BG with a weight of 5
AB with a weight of 1
AC with a weight of 6
CD with a weight of 7
DF with a weight of 2
there were all 8 nodes from the weighted graph.
there were 7 links connected them.
the spanning tree had a total weight of 28. *****
that, i believe, should be your answer.
here's my diagram of what i drew.
it pays to string them out and leave enough space for the one that aren't connected initially so you can see the actual paths clearly.
check your paths again, and draw them out to see why you got 30 rather than 28.
if you get a link that connects to two nodes that you already drew, that forms a cycle and need to be rejected.
here's some references you might find helpful for both kruskal and prin.
https://www.youtube.com/watch?v=4ZlRH0eK-qQ
https://www.tutorialspoint.com/data_structures_algorithms/spanning_tree.htm
https://www.tutorialspoint.com/data_structures_algorithms/kruskals_spanning_tree_algorithm.htm
https://www.tutorialspoint.com/data_structures_algorithms/prims_spanning_tree_algorithm.htm
prim and kruskal will get the same answer for this problem.
since this was the first time i had to do a problem like this, i had many trials and errors until i gelled on the right procedure.
check it out and verify that 28 should be the correct answer.
let me know if you still think otherwise.
RELATED QUESTIONS
Is it B? I want to check my answer.
Which is the cost of the minimum spanning tree of... (answered by MathLover1)
Is it A? I want to check my answer.
Which is the cost of a minimum spanning tree of... (answered by MathLover1)
Is it A? I want to check my answers.
Which is the cost of a minimum spanning tree of... (answered by MathLover1,ikleyn)
Which is the cost of a minimum spanning tree of the weighted graph using Kurskal's... (answered by MathLover1,ikleyn)
Is it D? I want to check my answer.
Which graph below is a tree graph?
A.
B.... (answered by jim_thompson5910)
Is it B? I want to check my answer.
Use graph coloring to find the minimum number of... (answered by ikleyn)
Is it A? I want to check my answer.
Use graph coloring to find the minimum number of... (answered by ikleyn)
Is it D? I want to check my answer.
Which graph below has an EULER PATH?
A.
B.
(answered by MathLover1)
Is it A? I want to check my answers.
Which graph below has an EULER CIRCUIT?
C.... (answered by solver91311,jim_thompson5910,math_helper)