Implementing Algorithms in Java

Question

How can I implement Near array based Prim's algorithm and Disjoint Set based Kruskal's algorithm in java. I have tried but failed. So I can asking for some hints/helps

Answer 1

Hi Nick I am giving pseudocode of both algorithms using which I implemented that algorithm in java.But if you also implement it using pseudocode then that will be helpful in future.

Prim's algorithm:

INPUT :n,c[e(ij)],i,j belonging to {1,...,n}. OUTPUT :p(j) j=2,...,n (pointer of peaks j father in the T tree).

STEPS

1. :(initializations). O={1} (V(1) root of the T tree). P={2,...,n} For every j belonging to P :e(j):=c[e(j1)] , p(j)=1 ( all peaks connected to the root.By definition of the cost function:e(j)=infinite when V(j) does not connect to V(1).).
2. Choose a k for which e(k)<=e(j) for every j belonging to P.In case of tight choose the smaller one. Exchange the O set with the set produced by the union of the O set and {k} . Exchange the P set with the set produced by the difference of the P set and {k} .(P<-P-{k}) If P=0 then stop.
3. For every j belonging to P compare e(j) with c[e(kj)]. If e(j) >c[e(kj)] exchange e(j) <-c(e(kj)).Go back to Step 1.

For Kruskal's

function Kruskal(G = : graph; length: A → R+): set of edges

2 Define an elementary cluster C(v) ← {v}.

3 Initialize a priority queue Q to contain all edges in G, using the weights as keys.

4 Define a forest T ← Ø //T will ultimately contain the edges of the MST

5 // n is total number of vertices

6 while T has fewer than n-1 edges do

7 // edge u,v is the minimum weighted route from u to v

8 (u,v) ← Q.removeMin()

9 // prevent cycles in T. add u,v only if T does not already contain a path between u and v.

10 // the vertices has been added to the tree.

11 Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.

13 if C(v) ≠ C(u) then

14 Add edge (v,u) to T.

15 Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u).

16 return tree T

Answer 2

Here is a Java implementation for Prim's algorithm that I once wrote. Note that for simplification, the input is a map between a node and its edges. While this representation is compact with relation to an adjacency matrix, it is redundant (every edge has to be specified twice - once for every source), and therefore requires careful construction. If you abstract the grpah structure with a new class Graph, you can easily achieve a simpler and better API.

public class MST {
    public static class Edge implements Comparable<Edge>{
        public final String source;
        public final String target;
        public final int weight;

        public Edge(String source, String target, int weight) {
            this.source = source;
            this.target = target;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return weight-o.weight;
        }

        @Override
        public String toString(){
            return "<"+source+"-"+target+">";
        }
    }

    public static Collection<Edge> getMST(Map<String,List<Edge>> g){
        Collection<Edge> res = new LinkedList<Edge>();
        HashSet<String> visitedV = new HashSet<String>();
        String initialVertex = g.keySet().iterator().next();
        visitedV.add(initialVertex);
        PriorityQueue<Edge> edgesQ = new PriorityQueue<Edge>();
        edgesQ.addAll(g.get(initialVertex));
        while (!edgesQ.isEmpty()){
            Edge e = edgesQ.remove();
            if (!visitedV.contains(e.target)){
                res.add(e);
                visitedV.add(e.target);             
                List<Edge> newEdges = g.get(e.target);
                edgesQ.addAll(newEdges);
            }
        }

        if (res.size() < g.size() - 1)
            throw new IllegalArgumentException("The graph is not connected");
        return res;
    }
}