CODEWITHSUNDEEP
javasetkruskals-algorithm
acasla
acasla

Reputation: 141

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

I have to implement Kruskal's Algorithm in Java.

I have the part that I get the edges ordered by weight, but I am a little lost when I have to think the structure to save the sets of each tree.

I thought in having a vector of sets, where each sets represents a tree. But I don't know what to do if I have to union two trees. Delete both elements from the vector and add a new combined one?

Is there an structure that would make it easier?

What I need is:

Upvotes: 0

Views: 486

Answers (1)

Evan VanderZee
Evan VanderZee

Reputation: 867

The disjoint-set data structure that is referenced in the Wikipedia article you linked to in your question is the type of structure you need. I'll suppose that you have a Vertex class in your implementation and give an example of what the "simple approach" might look like in Java, using an ArrayList<Vertex> to represent a set of vertices that form a connected component.

You would modify your Vertex class to look 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 already satisfies the part of the algorithm that involves adding an element to a set, since the constructor takes care of creating the new component and adding the vertex to its own component.

To check whether two vertices u and v are in the same component you would use

if (u.getComponent() == v.getComponent()) {
    // they are in the same component
} else {
    // the components are different
}

and when you find that u and v are not in the same component, you could union the components with code like the 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();
}
for (Vertex aVtx : smaller) {
    aVtx.setComponent(larger);
}
larger.addAll(smaller);

I think that's all you would really need to implement Kruskal's algorithm correctly, but I have not addressed your comments about a major set. If you wish to keep track of all of the components so that you can see what they look like at any point in the algorithm, this could be accomplished with a HashSet<ArrayList<Vertex>> majorSet. As you constructed each vertex you could add the component to majorSet, and when you unite two components you would remove smaller from majorSet. You could iterate over majorSet.values() in the standard fashion.

Upvotes: 1

Related Questions