Prim's algorithm's implementation in java

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted, undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

Example run

Image	U	possible edges	V \ U	Description
	{}		{A,B,C,D,E,F,G}	This is our original weighted graph. The numbers near the edges indicate their weight.
	{D}	{D,A} = 5 V {D,B} = 9 {D,E} = 15 {D,F} = 6	{A,B,C,E,F,G}	Vertex D has been arbitrarily chosen as a starting point. Vertices A, B, E and F are connected to D through a single edge. A is the vertex nearest to D and will be chosen as the second vertex along with the edge AD.
	{A,D}	{D,B} = 9 {D,E} = 15 {D,F} = 6 V {A,B} = 7	{B,C,E,F,G}	The next vertex chosen is the vertex nearest to either D or A. B is 9 away from D and 7 away from A, E is 15, and F is 6. F is the smallest distance away, so we highlight the vertex F and the edge DF.
	{A,D,F}	{D,B} = 9 {D,E} = 15 {A,B} = 7 V {F,E} = 8 {F,G} = 11	{B,C,E,G}	The algorithm carries on as above. Vertex B, which is 7 away from A, is highlighted.
	{A,B,D,F}	{B,C} = 8 {B,E} = 7 V {D,B} = 9 cycle {D,E} = 15 {F,E} = 8 {F,G} = 11	{C,E,G}	In this case, we can choose between C, E, and G. C is 8 away from B, E is 7 away fromB, and G is 11 away from F. E is nearest, so we highlight the vertex E and the edge BE.
	{A,B,D,E,F}	{B,C} = 8 {D,B} = 9 cycle {D,E} = 15 cycle {E,C} = 5 V {E,G} = 9 {F,E} = 8 cycle {F,G} = 11	{C,G}	Here, the only vertices available are C and G.C is 5 away from E, and G is 9 away from E.C is chosen, so it is highlighted along with the edge EC.
	{A,B,C,D,E,F}	{B,C} = 8 cycle {D,B} = 9 cycle {D,E} = 15 cycle {E,G} = 9 V {F,E} = 8 cycle {F,G} = 11	{G}	Vertex G is the only remaining vertex. It is 11 away from F, and 9 away from E. E is nearer, so we highlight G and the edge EG.
	{A,B,C,D,E,F,G}	{B,C} = 8 cycle {D,B} = 9 cycle {D,E} = 15 cycle {F,E} = 8 cycle {F,G} = 11 cycle	{}	Now all the vertices have been selected and the minimum spanning tree is shown in green. In this case, it has weight 39.

Implementation:

import java.io.*;
class Tnode
{
int prev;
int len;
char label;
boolean vis;
public Tnode(char lab)
 {
   label = lab;
   prev=-1;
   len=100000;
   vis=false;
 }
}

class graph
{
  public final int MAX = 20;
  public int nverts,i,min;
  public Tnode vlist[];
  public int adj[][];  
  public graph()
  {
   nverts = 0;
   adj = new int[MAX][MAX];
   vlist = new Tnode[MAX];
   for(int i=0;i<MAX;i++)
 {
for(int j=0;j<MAX;j++)
adj[i][j] = 0;
 }
  }
  public void addver(char lab)
  {
    vlist[nverts++] = new Tnode(lab);
  }
  public void addedge(int start,int end,int cost)
  {
    adj[start][end] = cost;
adj[end][start] = cost;
  }
  public int getind(char l)
  {
    for(int i=0;i<nverts;i++)
      if(vlist[i].label==l)
      return i;
    return (MAX+1);
  }
  public void brfs(int src)
  {
 int k,c=0,minicost=0;
 vlist[src].len=0;
 vlist[src].vis=true;
k=src;
while(c<nverts){
for(i=0;i<nverts;i++)
{
if((adj[k][i]!=0)&&(vlist[i].vis==false))
{
if(adj[k][i]<vlist[i].len)
{
vlist[i].prev=k;
vlist[i].len=adj[k][i];
}
}
}
k=0;
min=100000;
for(i=0;i<nverts;i++)
{
if((vlist[i].vis==false)&&(vlist[i].len<min))
{
min=vlist[i].len;
k=i;
}
}
vlist[k].vis=true;
c++;
 }
 for(i=0;i<nverts;i++)
{
if(vlist[i].prev!=-1)
{
System.out.print("\n vertex" +vlist[i].label+"is connected to"+vlist[vlist[i].prev].label);
minicost=minicost+vlist[i].len;
}
}
System.out.println("\nMinimum cost=" +minicost);
}
}
class Prims
{
  public static void main(String args[])throws IOException
  {
    graph gr = new graph();
char c;
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(isr);
    System.out.println("Enter the number of vertices");
    int n = Integer.parseInt(br.readLine());
String t;
System.out.println("Enter the labels for the vertices");
for(int i=0;i<n;i++)
{
t = br.readLine();
c = t.charAt(0);
gr.addver(c);
}
System.out.println("Enter the number of edges");
int edg = Integer.parseInt(br.readLine());
System.out.println("Enter the vertices which you need to connect");
for(int j=0;j<edg;j++)
{
System.out.println("Enter the first vertex");
t = br.readLine();
c = t.charAt(0);
int start = gr.getind(c);
System.out.println("Enter the second vertex");
t = br.readLine();
c = t.charAt(0);
int end = gr.getind(c);
System.out.println("Enter the cost");
int cost = Integer.parseInt(br.readLine());
gr.addedge(start,end, cost);
}
System.out.println("Enter the source vertex");
t = br.readLine();
c = t.charAt(0);
int src = gr.getind(c);
gr.brfs(src);
  }
}