in Algorithms edited by
7,445 views
25 votes
25 votes

What is the weight of a minimum spanning tree of the following graph?

  1. $29$
  2. $31$
  3. $38$
  4. $41$
in Algorithms edited by
7.4k views

3 Answers

23 votes
23 votes
Best answer

Apply Prim's algorithm, start from $A$ as shown in figure below.

Add all the weights in the given figure which will be equal to $31$.

Correct Answer: $B$

edited by

4 Comments

Can we backtrack in a prims algorithm??

I mean if we can't move ahead on any edge, then can we backtrack?
0
0

@techbd123

Can you please see my above comment.

0
0

@`JEET
 

Please check it.

1
1
4 votes
4 votes
Solution: B

The minimum spanning tree is

AC,AD,BG,EI,BD,FH,HI,IJ,GH.

1 comment

answer is 31
0
0
1 vote
1 vote

Use kruskals algorithm

31 is the answer

Answer:

Related questions