I have this Java implementation of Kruskal's algorithm. It solves a tiny problem instance correctly, yet I am not quite sure, whether my implementation is correct.The code as follows:MSTFinder.javapackage net.coderodde.graph.mst;import java.util.List;import net.coderodde.graph.UndirectedGraphEdge;import net.coderodde.graph.UndirectedGraphNode;import net.coderodde.graph.WeightFunction;public interface MSTFinder {    /**     * Computes the minimum-spanning tree and returns it in the form of a list     * of undirected edges. If an error occurred during the computation,      * <code>null</code> is returned.     *      * @param graph         the graph.     * @param weightFuntion the weight function over the edges of      *                      <code>graph</code>.     * @return              the list of edges comprising a minimum-spanning      *                      tree, or <code>null</code> if an error occurred.     */    public List<UndirectedGraphEdge>         findMinimumSpanningTree(final List<UndirectedGraphNode> graph,                                final WeightFunction weightFuntion);}KruskalMSTFinder.javapackage net.coderodde.graph.mst.support;import java.util.ArrayList;import java.util.Collections;import java.util.HashMap;import java.util.LinkedHashSet;import java.util.List;import java.util.Map;import java.util.Set;import net.coderodde.graph.UndirectedGraphEdge;import net.coderodde.graph.UndirectedGraphNode;import net.coderodde.graph.WeightFunction;import net.coderodde.graph.mst.MSTFinder;public class KruskalMSTFinder implements MSTFinder {    private final Map<UndirectedGraphNode,                       DisjointSet<UndirectedGraphNode>> map;    private final Set<UndirectedGraphEdge> edgeSet;    private final List<UndirectedGraphEdge> edgeList;    public KruskalMSTFinder() {        this.map = new HashMap<>();        this.edgeSet = new LinkedHashSet<>();        this.edgeList = new ArrayList<>();    }    @Override    public List<UndirectedGraphEdge>         findMinimumSpanningTree(final List<UndirectedGraphNode> graph,                                final WeightFunction weightFunction) {        try {            prepareEdgeList(graph, weightFunction);            final List<UndirectedGraphEdge> minimumSpanningTree = new ArrayList<>();            for (final UndirectedGraphEdge edge : edgeList) {                final UndirectedGraphNode u = edge.firstNode();                final UndirectedGraphNode v = edge.secondNode();                DisjointSet<UndirectedGraphNode> us = map.get(u);                DisjointSet<UndirectedGraphNode> vs = map.get(v);                us = us.find(us);                vs = vs.find(vs);                if (us != vs) {                    minimumSpanningTree.add(edge);                    us.union(vs);                }            }            clearAll();            return minimumSpanningTree;        } catch (final Exception e) {            clearAll();            return null;        }    }    private void clearAll() {        map.clear();        edgeSet.clear();        edgeList.clear();    }    private void prepareEdgeList(final List<UndirectedGraphNode> graph,                                 final WeightFunction weightFunction) {        for (final UndirectedGraphNode node : graph) {            map.put(node, new DisjointSet<>());            for (final UndirectedGraphNode neighbor : node) {                edgeSet.add(                        new UndirectedGraphEdge(node,                                                 neighbor,                                                 weightFunction                                                        .get(node, neighbor)));            }        }        edgeList.addAll(edgeSet);        Collections.<UndirectedGraphEdge>sort(edgeList);    }}DisjointSet.javapackage net.coderodde.graph.mst.support;public class DisjointSet<E> {    private DisjointSet<E> parent;    private int rank;    public DisjointSet() {        this.parent = this;        this.rank = 0;    }    public DisjointSet<E> find(final DisjointSet<E> set) {        return getRoot(set);    }    public void union(final DisjointSet<E> otherSet) {        final DisjointSet<E> otherRoot = getRoot(otherSet);        final DisjointSet<E> thisRoot = getRoot(this);        if (otherRoot == thisRoot) {            return;        }        if (otherRoot.rank < thisRoot.rank) {            otherRoot.parent = thisRoot.parent;        } else if (otherRoot.rank > thisRoot.rank) {            thisRoot.parent = otherRoot.parent;        } else {            thisRoot.parent = otherRoot.parent;            otherRoot.rank = thisRoot.rank + 1;        }    }    private DisjointSet<E> getRoot(final DisjointSet<E> set) {        if (set.parent == set) {            return set;        }        return getRoot(set.parent);    }}WeightFunction.javapackage net.coderodde.graph;import java.util.HashMap;import java.util.Map;public class WeightFunction {    private final Map<UndirectedGraphNode,                   Map<UndirectedGraphNode, Double>> map;    public WeightFunction() {        this.map = new HashMap<>();    }    public void put(final UndirectedGraphNode u,                     final UndirectedGraphNode v,                    final double weight) {        putImpl(u, v, weight);        putImpl(v, u, weight);    }    public double get(final UndirectedGraphNode u,                       final UndirectedGraphNode v) {        return map.get(u).get(v);    }    private void putImpl(final UndirectedGraphNode u,                          final UndirectedGraphNode v,                         final double weight) {        if (!map.containsKey(u)) {            map.put(u, new HashMap<>());        }        map.get(u).put(v, weight);    }}UndirectedGraphNode.javapackage net.coderodde.graph;import java.util.Iterator;import java.util.LinkedHashSet;import java.util.Set;public class UndirectedGraphNode implements Iterable<UndirectedGraphNode> {    private final String id;    private final Set<UndirectedGraphNode> neighbors;    public UndirectedGraphNode(final String id) {        this.id = id;        this.neighbors = new LinkedHashSet<>();    }    public void connectTo(final UndirectedGraphNode other) {        this.neighbors.add(other);        other.neighbors.add(this);    }    public boolean isConnectedTo(final UndirectedGraphNode queryNode) {        return this.neighbors.contains(queryNode);    }    public void disconnectFrom(final UndirectedGraphNode neighbor) {        this.neighbors.remove(neighbor);        neighbor.neighbors.remove(this);    }    public boolean equals(final Object obj) {        if (!(obj instanceof UndirectedGraphNode)) {            return false;        }        return ((UndirectedGraphNode) obj).id.equals(this.id);    }    @Override    public int hashCode() {        return this.id.hashCode();    }    @Override    public Iterator<UndirectedGraphNode> iterator() {        return new NeighborIterator();    }    @Override    public String toString() {        return [UndirectedGraphNode  + id + ];    }    public String getId() {        return id;    }    private class NeighborIterator implements Iterator<UndirectedGraphNode> {        private final Iterator<UndirectedGraphNode> iterator =                 UndirectedGraphNode.this.neighbors.iterator();        @Override        public boolean hasNext() {            return iterator.hasNext();        }        @Override        public UndirectedGraphNode next() {            return iterator.next();        }    }}UndirectedGraphEdge.javapackage net.coderodde.graph;public class UndirectedGraphEdge implements Comparable<UndirectedGraphEdge> {    private final UndirectedGraphNode u;    private final UndirectedGraphNode v;    private final double weight;    public UndirectedGraphEdge(final UndirectedGraphNode u,                                final UndirectedGraphNode v,                               final double weight) {        this.u = u;        this.v = v;        this.weight = weight;    }     public UndirectedGraphNode firstNode() {        return u;    }    public UndirectedGraphNode secondNode() {        return v;    }    public String toString() {        return [UndirectedGraphEdge between  + u.getId() +  and  +                 v.getId() + ];    }    public int hashCode() {        return u.hashCode() ^ v.hashCode();    }    @Override    public boolean equals(final Object obj) {        if (!(obj instanceof UndirectedGraphEdge)) {            return false;        }        final UndirectedGraphEdge edge = (UndirectedGraphEdge) obj;        if (this.u.equals(edge.u) && this.v.equals(edge.v)) {            return true;        }        return this.u.equals(edge.v) && this.v.equals(edge.u);    }    /**     * Sorts a sequence of edges into descending order by edge weight.     *      * @param o the other edge to compare against.     * @return a negative value if the input edge has larger weight,     *         a positive value if the input edge has smaller weight, and     *         the value zero if the two weights are equal.     */    @Override    public int compareTo(final UndirectedGraphEdge o) {        return Double.compare(this.weight, o.weight);    }}Demo.javapackage net.coderodde.graph;import java.util.ArrayList;import java.util.List;import java.util.Random;import net.coderodde.graph.mst.MSTFinder;import net.coderodde.graph.mst.support.KruskalMSTFinder;public class Demo {    private static final int SIZE = 100000;    private static final float EDGE_LOAD_FACTOR = 15.0f;    public static void main(final String... args) {        final List<UndirectedGraphNode> graph = new ArrayList<>();        // This graph is from English-language Wikipedia-article on         // Kruskal's algorithm:        final UndirectedGraphNode a = new UndirectedGraphNode(A);        final UndirectedGraphNode b = new UndirectedGraphNode(B);        final UndirectedGraphNode c = new UndirectedGraphNode(C);        final UndirectedGraphNode d = new UndirectedGraphNode(D);        final UndirectedGraphNode e = new UndirectedGraphNode(E);        graph.add(a);        graph.add(b);        graph.add(c);        graph.add(d);        graph.add(e);        final WeightFunction wf = new WeightFunction();        a.connectTo(e);        a.connectTo(b);        b.connectTo(e);        e.connectTo(c);        b.connectTo(c);        c.connectTo(d);        e.connectTo(d);        wf.put(a, e, 1.0);        wf.put(a, b, 3.0);        wf.put(b, e, 4.0);        wf.put(e, c, 6.0);        wf.put(b, c, 5.0);        wf.put(c, d, 2.0);        wf.put(e, d, 7.0);        final MSTFinder finder = new KruskalMSTFinder();        final List<UndirectedGraphEdge> mst =                 finder.findMinimumSpanningTree(graph, wf);        for (final UndirectedGraphEdge edge : mst) {            System.out.println(edge +   +                     wf.get(edge.firstNode(), edge.secondNode()));        }        System.out.println(MST done.);        final long seed = System.currentTimeMillis();        System.out.println(Seed:  + seed);        final Random rnd = new Random(seed);        final Pair<List<UndirectedGraphNode>, WeightFunction> data =                createRandomGraph(SIZE, EDGE_LOAD_FACTOR, rnd);        System.out.println(Graph constructed.);        final long ta = System.currentTimeMillis();        final List<UndirectedGraphEdge> tree =                finder.findMinimumSpanningTree(data.first, data.second);        System.out.println(                Time:  + (System.currentTimeMillis() - ta) +  ms.);    }    public static final class Pair<F, S> {        public final F first;        public final S second;        public Pair(final F first, final S second) {            this.first = first;            this.second = second;        }    }    public static <E> E choose(final List<E> list, final Random rnd) {        if (list.isEmpty()) {            return null;        }        return list.get(rnd.nextInt(list.size()));    }    private static Pair<List<UndirectedGraphNode>, WeightFunction>            createRandomGraph(final int size,                               final float edgeLoadFactor,                              final Random rnd) {        final List<UndirectedGraphNode> graph = new ArrayList<>(size);        final WeightFunction wf = new WeightFunction();        for (int i = 0; i < size; ++i) {            graph.add(new UndirectedGraphNode( + i));        }        int edges = (int)(Math.min(1.0f, edgeLoadFactor) * size);        while (edges > 0) {            final UndirectedGraphNode u = choose(graph, rnd);            final UndirectedGraphNode v = choose(graph, rnd);            u.connectTo(v);            wf.put(u, v, 10.0 * rnd.nextDouble() - 5.0);            --edges;        }        return new Pair(graph, wf);    }}So what do you think?
Kruskal's algorithm in Java
java;algorithm;tree;graph
KruskalMSTFinder.java was not nice to read for me.map, edgeSet and edgeList are defined as fields. They are initialized in prepareEdgeList-Method and reset in the clearAll-Method. Both are called within the findMinimumSpanningTree-Method.So map, edgeSet and edgeList defined as local Variables would do the same job. Now it is not Threadsafe! Thread one could clear the fields, while Thread two would like to prepare it.Just define them as local Variables and let prepareEdgeList, prepareEdgeSet and prepareEdgeMap return a prepared map, edgeList and edgeSet.