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

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