To find Minimum Cost Spanning Tree of a given connected undirected graph using Prims algorithm.

In This Post we are find Minimum Cost Spanning Tree of a given connected undirected graph using Prim’s algorithm.

7] To find Minimum Cost Spanning Tree of a given connected undirected graph using Prim’s algorithm.

PROGRAM :-

import java.util.Scanner;

public class Prims {

    public static void main(String[] args) {

        int w[][] = new int[10][10];

        int n, i, j, s, k = 0;

        int min;

        int sum = 0;

        int u = 0, v = 0;

        int flag = 0;

        int sol[] = new int[10];

        System.out.println("Enter the number of vertices");

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();

        for (i = 1; i <= n; i++)

            sol[i] = 0;

        System.out.println("Enter the weighted graph");

        for (i = 1; i <= n; i++)

            for (j = 1; j <= n; j++)

                w[i][j] = sc.nextInt();

        System.out.println("Enter the source vertex");

        s = sc.nextInt();

        sol[s] = 1;

        k = 1;

        while (k <= n - 1)

        {

            min = 99;

            for (i = 1; i <= n; i++)

                for (j = 1; j <= n; j++)

                    if (sol[i] == 1 && sol[j] == 0)

                        if (i != j && min > w[i][j])

                        {

                            min = w[i][j];

                            u = i;

                            v = j;

                        }

            sol[v] = 1;

            sum = sum + min;

            k++;

            System.out.println(u + "->" + v + "=" + min);

        }

        for (i = 1; i <= n; i++)

            if (sol[i] == 0)

                flag = 1;

        if (flag == 1)

            System.out.println("No spanning tree");

        else

            System.out.println("The cost of minimum spanning tree is" + sum);

        sc.close();

    }

}