Java structure for set of sets that have to union? (for Kruskal's Algorithm) -

i have implement kruskal's algorithm in java.

i have part edges ordered weight, little lost when have think structure save sets of each tree.

i thought in having vector of sets, each sets represents tree. don't know if have union 2 trees. delete both elements vector , add new combined one?

is there structure make easier?

what need is:

• iterate on sets major set
• add element 1 of sets, or
• create new set , add major set
• union 2 of sets (of course, deleting singular versions)

the disjoint-set data structure referenced in wikipedia article linked in question type of structure need. i'll suppose have vertex class in implementation , give example of "simple approach" might in java, using arraylist<vertex> represent set of vertices form connected component.

you modify vertex class like

public class vertex {      // other data members     private arraylist<vertex> component;      public vertex(/* arguments */) {         // other initialization         component = new arraylist<>();         component.add(this);     }      // other methods      public arraylist<vertex> getcomponent() {         return component;     }      public void setcomponent(arraylist<vertex> updatedcomponent) {         component = updatedcomponent;     } } 

this satisfies part of algorithm involves adding element set, since constructor takes care of creating new component , adding vertex own component.

to check whether 2 vertices u , v in same component use

if (u.getcomponent() == v.getcomponent()) {     // in same component } else {     // components different } 

and when find u , v not in same component, union components code following.

arraylist<vertex> larger; arraylist<vertex> smaller; if (u.getcomponent().size() < v.getcomponent().size()) {     larger = v.getcomponent();     smaller = u.getcomponent(); } else {     larger = u.getcomponent();     smaller = v.getcomponent(); } (vertex avtx : smaller) {     avtx.setcomponent(larger); } larger.addall(smaller); 

i think that's need implement kruskal's algorithm correctly, have not addressed comments major set. if wish keep track of of components can see @ point in algorithm, accomplished hashset<arraylist<vertex>> majorset. constructed each vertex add component majorset, , when unite 2 components remove smaller majorset. iterate on majorset.values() in standard fashion.