implementing kruskals algorithm in java

Question

im able to run this code for some input. but in some cases i get the wrong spanning tree. for eg: if i give the input as follows while executing the program :

Enter no.of vertices: 5 Enter no.of edges: 8

    Enter the vertices and the weight of edge 1:
    1
    3
    10

 Enter the vertices and the weight of edge 2:
1
4
100
 Enter the vertices and the weight of edge 3:
3
5
64
 Enter the vertices and the weight of edge 4:
1
2
13
 Enter the vertices and the weight of edge 5:
3
2
20
 Enter the vertices and the weight of edge 6:
2
5
5
 Enter the vertices and the weight of edge 7:
4
3
80
 Enter the vertices and the weight of edge 8:
4
5
40
MINIMUM SPANNING TREE :
2-5
1-3
4-5
MINIMUM COST = 55

expected o/p :

 MINIMUM SPANNING TREE :
    2-5
    1-3
    1-2
    4-5
    MINIMUM COST = 68

kindly help me out to rectify my mistake... pls tel me wat changes shud i make in the code.. plssss

the code is as follows :

import java.io.*;  
class Edge
{
 int v1,v2,wt;   // wt is the weight of the edge
}
class kruskalsalgo
{
public static void main(String args[])throws IOException 
{ 
int i,j,mincost=0;
BufferedReader br=new BufferedReader( new InputStreamReader(System.in));
System.out.println(" Enter no.of vertices:");
int v=Integer.parseInt(br.readLine());
System.out.println(" Enter no.of edges:");
int e=Integer.parseInt(br.readLine());
 Edge ed[]=new Edge[e+1];
for(i=1;i<=e;i++)
{
 ed[i]=new Edge();
 System.out.println(" Enter the vertices and the weight of edge "+(i)+ ":"); 
 ed[i].v1=Integer.parseInt(br.readLine());
 ed[i].v2=Integer.parseInt(br.readLine());
 ed[i].wt=Integer.parseInt(br.readLine());
}
for(i=1;i<=e;i++)      // sorting the edges in ascending order
 for(j=1;j<=e-1;j++)
{
 if(ed[j].wt>ed[j+1].wt)
 {
   Edge t=new Edge();
    t=ed[j];
    ed[j]=ed[j+1];
    ed[j+1]=t;
}
}

int visited[]=new int[v+1];       // array to check whether the vertex is visited or not
for(i=1;i<=v;i++)
 visited[i]=0;
System.out.println("MINIMUM SPANNING TREE :");


for(i=1;i<=e;i++)
{ 
 if(i>v)
  break;
else if( visited[ed[i].v1]==0 || visited[ed[i].v2]==0)
 {
    System.out.println(ed[i].v1+ "-"+ ed[i].v2);
    visited[ed[i].v1]=visited[ed[i].v2]=1;
    mincost+=ed[i].wt;
 }
}
System.out.println("MINIMUM COST = " +mincost);
}
}

Answer 1

Here's a proper implementation of Kruskal's algorithm in Java when your graph is stored as an edge list. For Kruskal's algorithm to work properly you will need a data structure called a union find (also called disjoint set) which supports quickly unifying sets together. The algorithm works by first sorting all the edges by weight in ascending order and then joining together nodes which do not yet belong to the same node group. The idea behind this is that if two nodes belong to the same group then including the current edge would cause a cycle in our minimum spanning tree which is disallowed. I hope this helps review the code below it is well documented.

Code was taken from my Github algorithm repo.

/**
 * An implementation of Kruskal's MST algorithm using an edge list.
 * @author William Fiset
 **/

// Union find data structure 
class UnionFind {

  private int[] id, sz;

  public UnionFind(int n) {
    id = new int[n];
    sz = new int[n];
    for (int i = 0; i < n; i++) {
      id[i] = i;
      sz[i] = 1;
    }
  }

  public int find(int p) {
    int root = p;
    while (root != id[root])
      root = id[root];
    while (p != root) { // Do path compression
      int next = id[p];
      id[p] = root;
      p = next;
    }
    return root;
  }

  public boolean connected(int p, int q) {
    return find(p) == find(q);
  }

  public int size(int p) {
    return sz[find(p)];
  }

  public void union(int p, int q) {
    int root1 = find(p);
    int root2 = find(q);
    if (root1 == root2) return;
    if (sz[root1] < sz[root2]) {
      sz[root2] += sz[root1];
      id[root1] = root2;
    } else {
      sz[root1] += sz[root2];
      id[root2] = root1;
    }
  }

}

class Edge implements Comparable <Edge> {
  int from, to, cost;
  public Edge(int from, int to, int cost) {
    this.from = from;
    this.to = to;
    this.cost = cost;
  }
  @Override public int compareTo(Edge other) {
    return cost - other.cost;
  }
}

public class KruskalsEdgeList {

  // Given a graph represented as an edge list this method finds
  // the Minimum Spanning Tree (MST) cost if there exists 
  // a MST, otherwise it returns null.
  static Long kruskals(Edge[] edges, int n) {

    if (edges == null) return null;

    long sum = 0L;
    java.util.Arrays.sort(edges);
    UnionFind uf = new UnionFind(n);

    for (Edge edge : edges) {

      // Skip this edge to avoid creating a cycle in MST
      if (uf.connected(edge.from, edge.to))
        continue;

      // Include this edge
      uf.union(edge.from, edge.to);
      sum += edge.cost;

      // Optimization to stop early if we found
      // a MST that includes all the nodes
      if (uf.size(0) == n) break;

    }

    // Make sure we have a MST that includes all the nodes
    if (uf.size(0) != n) return null;

    return sum;

  }

}

Answer 2

You should refer to the actual algorithm: http://en.wikipedia.org/wiki/Kruskal%27s_algorithm You are making a few mistakes in your code. For simplicity you might want to define your

Edge class something like this:

class Edge implements Comparable<Edge>
{
    int v1,v2,wt; 

    Edge(int v1, int v2, int wt)
    {
        this.v1=v1;
        this.v2=v2;
        this.wt=wt;
    }

    @Override
    public int compareTo(Edge o) {
        Edge e1 = (Edge)o;
        if(e1.wt==this.wt)
            return 0;
        return e1.wt < this.wt ? 1 : -1;
    }

    @Override
    public String toString()
    {
        return String.format("Vertex1:%d \t Vertex2:%d \t Cost:%d\n", v1,v2,wt);

    }
}

Here extend comparable so you can use java Collections.sort() on your edges and it will sort ascending for you, and override toString() so you can use it for printing and helps in debugging.

In your visited array, you are only checking if you have visited it at one point but that is not the criteria to make a minimum spanning tree. For example, in your input I can pick edges {1,2,5}, {2,5,5}, {4,5,40}, which would visit every vertex once but not give you your minimum spanning tree.

The algorithm first says to make a a forest of trees. This means for every vertex you should create a set with just itself as a member. Something like this:

HashMap<Integer,Set<Integer>> forest = new HashMap<Integer,Set<Integer>>();
for(Integer vertex : vertices)
{
        //Each set stores the known vertices reachable from this vertex
        //initialize with it self.
    Set<Integer> vs = new HashSet<Integer>();
    vs.add(vertex);
    forest.put(vertex, vs);
}

Now iterate over your edges. Sorting them is good because you can just use it as stack, so pop until you find your min tree or run out of edges. For each edge you want to merge the sets of reachable vertices for the 2 vertices that is joined by the edge. If the sets of reachable vertices is the same for the 2 vertices that make the edge then don't merge because it will form a loop. If they don't, add the edge to your min tree. Stop once you find a set that contains all your vertices. In code it will look something like this:

//sort your edges, you should use existing functionality where possible, saves testing needed
//here edges is your Stack, pop until minimum spanning tree is found.
Collections.sort(edges);
ArrayList<Edge> minSpanTree = new ArrayList<Edge>();
while(true) //while you haven't visited all the vertices at least once
{
    Edge check = edges.remove(0);//pop

    Set<Integer> visited1 = forest.get(check.v1);
    Set<Integer> visited2 = forest.get(check.v2);
    if(visited1.equals(visited2))
        continue;
    minSpanTree.add(check);
    visited1.addAll(visited2);
    for(Integer i : visited1)
    {
        forest.put(i, visited1);
    }
    if(visited1.size()==vertices.length)
        break;
}

So for the following input:

Input: [Vertex1:2 Vertex2:5 Cost:5 , Vertex1:1 Vertex2:3 Cost:10 , Vertex1:1 Vertex2:2 Cost:13 , Vertex1:3 Vertex2:2 Cost:20 , Vertex1:4 Vertex2:5 Cost:40 , Vertex1:3 Vertex2:5 Cost:64 , Vertex1:4 Vertex2:3 Cost:80 , Vertex1:1 Vertex2:4 Cost:100]

You get the min span tree: Output: [Vertex1:2 Vertex2:5 Cost:5 , Vertex1:1 Vertex2:3 Cost:10 , Vertex1:1 Vertex2:2 Cost:13 , Vertex1:3 Vertex2:2 Cost:20 , Vertex1:4 Vertex2:5 Cost:40]

-Niru