Constructing The Minimum Spanning Tree for a Graph using Kruskal’s Algorithm

Kruskal’s algorithm is a minimum-spanning-tree algorithm where the algorithm finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph at each step.

//To Construct the minimum spanning tre for a graph using Kruskal's Algorithm
import java.io.*;
class edge {
    int u, v, cost;
}
class kruskal {
    edge E[];
    int n, t[][], p[], e;
    void getdata() throws IOException {
        BufferedReader o = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter number of vertices: ");
        n = Integer.parseInt(o.readLine());
        System.out.println("Enter number of Edges: ");
        e = Integer.parseInt(o.readLine());

        E = new edge[20];
        t = new int[n][3];
        p = new int[n + 1];

        for (int i = 1; i <= n; i++)
            p[i] = -1;
        for (int i = 1; i <= e; i++) {
            edge x = new edge();
            System.out.print("Source " + i + ":-\t");
            x.u = Integer.parseInt(o.readLine());
            System.out.print("Destin " + i + ":-\t");
            x.v = Integer.parseInt(o.readLine());
            System.out.print("Weight " + i + ":-\t");
            x.cost = Integer.parseInt(o.readLine());
            E[i] = x;
            System.out.println();
        }
    }
    void sort() {
        edge t = new edge();
        for (int i = 1; i <= e - 1; i++)
            for (int j = 1; j <= e - i; j++)
                if (E[j].cost > E[j + 1].cost) {
                    t = E[j];
                    E[j] = E[j + 1];
                    E[j + 1] = t;
                }
        System.out.println("The sorted array is: ");
        for (int i = 1; i <= e; i++)
            System.out.println("An edge is :(" + E[i].u + "," + E[i].v + ") and cost :" + E[i].cost);
    }
    void union(int i, int j) {
        p[i] = j;
    }
    int find(int i) {
        while (p[i] > 0)
            i = p[i];
        return i;
    }
    int greedykruskal() {
        int mincost, u, v, min, j, k;
        int i = 1;
        int q = 1;
        mincost = 0;
        System.out.println("Edges selected are: ");
        while (i <= n - 1) {
            u = E[q].u;
            v = E[q].v;
            min = E[q].cost;
            j = find(u);
            k = find(v);
            if (j != k) {
                mincost = mincost + min;
                t[i][1] = u;
                t[i][2] = v;
                System.out.println("An edge(" + u + "," + v + ") with cost:" + min);
                i++;
                union(j, k);
            }

            q++;
        }
        if (i <= n - 1) {
            System.out.println("A spanning tree cannot be formed ");
            return 0;
        } else
            return mincost;
    }
}
class testkruskal {
    public static void main(String args[]) throws IOException {
        kruskal ob = new kruskal();
        ob.getdata();
        ob.sort();
        int m = ob.greedykruskal();
        System.out.println("Minimum cost is : " + m);
    }
}

/*-----------------------------------OUTPUT-------------------------
 
Enter number of vertices: 5

Enter number of Edges: 7

Source 1:- 1

Destin 1:- 3

Weight 1:- 13


Source 2:- 1

Destin 2:- 5

Weight 2:- 2


Source 3:- 1

Destin 3:- 2

Weight 3:- 11


Source 4:- 2

Destin 4:- 3

Weight 4:- 15


Source 5:- 2

Destin 5:- 4

Weight 5:- 8


Source 6:- 2

Destin 6:- 5

Weight 6:- 12


Source 7:- 4

Destin 7:- 5

Weight 7:- 14


The sorted array is: 
An edge is :(1,5) and cost :2
An edge is :(2,4) and cost :8
An edge is :(1,2) and cost :11
An edge is :(2,5) and cost :12
An edge is :(1,3) and cost :13
An edge is :(4,5) and cost :14
An edge is :(2,3) and cost :15

Edges selected are: 
An edge(1,5) with cost:2
An edge(2,4) with cost:8
An edge(1,2) with cost:11
An edge(1,3) with cost:13
Minimum cost is : 34
Process Exit...

*/

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.