Scribd
Upload
27 views1 page

Prims

The document contains code for implementing Prim's algorithm to find the minimum spanning tree of a weighted undirected graph. It takes in the number of vertices and adjacency matrix as input, finds the minimum cost edge to include at each step starting from a source vertex, and outputs the total cost of the minimum spanning tree.

Uploaded by

Raunak Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
27 views1 page

Prims

The document contains code for implementing Prim's algorithm to find the minimum spanning tree of a weighted undirected graph. It takes in the number of vertices and adjacency matrix as input, finds the minimum cost edge to include at each step starting from a source vertex, and outputs the total cost of the minimum spanning tree.

Uploaded by

Raunak Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 1

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();
}

You might also like