HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Kruskal's algorithm in Java

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
javakruskalalgorithm

Problem

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.java

package 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, 
     * null is returned.
     * 
     * @param graph         the graph.
     * @param weightFuntion the weight function over the edges of 
     *                      graph.
     * @return              the list of edges comprising a minimum-spanning 
     *                      tree, or null if an error occurred.
     */
    public List 
        findMinimumSpanningTree(final List graph,
                                final WeightFunction weightFuntion);
}


KruskalMSTFinder.java

```
package 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> map;
private final Set edgeSet;
private final List edgeList;

public KruskalMSTFinder() {
this.map = new HashMap<>();
this.edgeSet = new LinkedHashSet<>();
this.edgeList = new ArrayList<>();
}

@Override
public List
findMinimumSpanningTree(final List graph,
final WeightFunction weightFunction) {
try {
prepareEdgeList(

Solution

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.

Context

StackExchange Code Review Q#75249, answer score: 3

Revisions (0)

No revisions yet.