Answer to Question #289868 in C++ for Rukia

Question

Implement the following algorithm for finding the Minimum Spanning Tree in an undirected weighted graph. You must implement the disjoint set yourself. You must take input from the user.

MST-KRUSKAL(G,w):
A = ∅
For each vertex v ∈ G.V:
    MAKE-SET(v)
sort the edges of G,E into non decreasing order by weight w
For each edge (u, v) ∈ G.E taken in nondecreasing order by weight 
    if FIND-SET(u) ≠ FIND-SET(v):       
    A = A ∪ {(u, v)}
    UNION(u, v)
return A

sample input

V

E

u v weight(u,v)

6

9

0 1 4

1 2 5

0 3 10

1 3 3

1 5 6

1 4 7

2 4 1

3 5 9

4 5 8

Sample output:

MST

2 - 4

1 - 3

0 - 1

1 - 2

1 - 5

Weight:1+3+4+5+6 = 19

sample input:

4

5

0 1 10

0 2 6

0 3 5

1 3 15

2 3 4

sample output

MST

2 – 3

0 – 3

0 – 1

Weight: 4+5+10 = 19

Answer 1

Dear Rukia, your question requires a lot of work, which neither of our experts is ready to perform for free. We advise you to convert it to a fully qualified order and we will try to help you. Please click the link below to proceed: Submit order