To implement Kruskal’s algorithm.

import java.io.*;
import java.util.*;
class Graph
{

int i,n; //no of nodes
int noe; //no edges in the graph
int graph_edge[][]=new int[100][4];
int tree[][]=new int [10][10];
int sets[][]=new int[100][10];
int top[]=new int[100];
int cost=0;

int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println("I/O Error");
}
return ne;
}/*end getNumber*/

void read_graph()
{
System.out.print("Enter the no. of nodes in the undirected weighted graph ::");
n=getNumber();

noe=0;

System.out.println("Enter the weights for the following edges ::\n");
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
System.out.print(" < "+i+" , "+j+" > ::");
int w;
w=getNumber();
if(w!=0)
{
noe++;
graph_edge[noe][1]=i;
graph_edge[noe][2]=j;
graph_edge[noe][3]=w;
}
}
}
}

void sort_edges()
{
/**** Sort the edges using bubble sort in increasing order**************/

for(int i=1;i<=noe-1;i++)
{
for(int j=1;j<=noe-i;j++)
{
if(graph_edge[j][3]>graph_edge[j+1][3])
{
int t=graph_edge[j][1];
graph_edge[j][1]=graph_edge[j+1][1];
graph_edge[j+1][1]=t;

t=graph_edge[j][2];
graph_edge[j][2]=graph_edge[j+1][2];
graph_edge[j+1][2]=t;

t=graph_edge[j][3];
graph_edge[j][3]=graph_edge[j+1][3];
graph_edge[j+1][3]=t;
}
}
}
}

void algorithm()
{
// ->make a set for each node
for(int i=1;i<=n;i++)
{
sets[i][1]=i;
top[i]=1;
}

System.out.println("\nThe algorithm starts ::\n\n");

for(i=1;i<=noe;i++)
{
int p1=find_node(graph_edge[i][1]);
int p2=find_node(graph_edge[i][2]);

if(p1!=p2)
{
System.out.print("The edge included in the tree is ::");
System.out.print("< "+graph_edge[i][1]+" , ");
System.out.println(graph_edge[i][2]+" > ");;
cost=cost+graph_edge[i][3];

tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];

// Mix the two sets

for(int j=1;j<=top[p2];j++)
{
top[p1]++;
sets[p1][top[p1]]=sets[p2][j];
}
top[p2]=0;
}
else
{
System.out.println("Inclusion of the edge ");
System.out.print(" < "+graph_edge[i][1]+" , ");
System.out.println(graph_edge[i][2]+"> forms a cycle so it is removed\n\n");
}
}

System.out.println("Cost of the spanning tree : "+cost);
}

int find_node(int n)
{
for(int i=1;i<=noe;i++)
{
for(int j=1;j<=top[i];j++)
{
if(n==sets[i][j])
return i;
}
}
return -1;
}
}

class Kruskal1
{
public static void main(String args[])
{
Graph obj=new Graph();
obj.read_graph();
obj.sort_edges();
obj.algorithm();
}
}

/*
Enter the no. of nodes in the undirected weighted graph ::6
Enter the weights for the following edges ::

< 1 , 2 > ::3
< 1 , 3 > ::1
< 1 , 4 > ::6
< 1 , 5 > ::0
< 1 , 6 > ::0
< 2 , 3 > ::5
< 2 , 4 > ::0
< 2 , 5 > ::3
< 2 , 6 > ::0
< 3 , 4 > ::5
< 3 , 5 > ::6
< 3 , 6 > ::4
< 4 , 5 > ::0
< 4 , 6 > ::2
< 5 , 6 > ::6

The algorithm starts ::


The edge included in the tree is ::< 1 , 3 >
The edge included in the tree is ::< 4 , 6 >
The edge included in the tree is ::< 1 , 2 >
The edge included in the tree is ::< 2 , 5 >
The edge included in the tree is ::< 3 , 6 >
Inclusion of the edge
< 2 , 3> forms a cycle so it is removed


Inclusion of the edge
< 3 , 4> forms a cycle so it is removed


Inclusion of the edge
< 1 , 4> forms a cycle so it is removed


Inclusion of the edge
< 3 , 5> forms a cycle so it is removed


Inclusion of the edge
< 5 , 6> forms a cycle so it is removed


Cost of the spanning tree : 13
*/

To implement prim’s algorithm.

import java.io.*;
import java.util.*;

class Graph
{

int weight[][]=new int[20][20];
int visited[]=new int[20];
int d[]=new int[20];
int p[]=new int[20];
int v,e;

int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println("I/O Error");
}
return ne;
}/*end getNumber*/

void creategraph()
{
int i,j,a,b,w;
System.out.print("\nEnter number of vertices : ");
v=getNumber();
System.out.print("\nEnter number of edges : ");
e=getNumber();

for (i=1;i<=v;i++)
for (j=1;j<=v;j++)
weight[i][j]=0;

for (i=1;i<=v;i++)
{
 p[i] = visited[i] =0;
 d[i] = 32767;
}

for (i=1;i<=e;i++)
{
 System.out.print("\nEnter edge a,b and weight w : ");
 a=getNumber();
 b=getNumber();
 w=getNumber();
 weight[a][b]=weight[b][a]=w;
}
}
void PrimAlgorithm()
{
creategraph();
int current, totalvisited, mincost,i;
current=1; d[current]=0;
totalvisited =1;
visited[current]=1;

while(totalvisited!=v)
{
 for (i=1;i<=v;i++)
 {
if(weight[current][i]!=0)
if(visited[i]==0)
if(d[i]>weight[current][i])
{
d[i] = weight[current][i];
p[i] = current;
}
 }
mincost= 32767;
for (i=1;i<=v;i++)
{
if(visited[i] ==0)
if (d[i] <mincost)
{
mincost = d[i];
current = i;
}
}
visited[current] = 1;
totalvisited++;
} /*end of while loop */
mincost =0;
for (i=1;i<=v;i++)
mincost += d[i];
System.out.println("\nMinimum cost = "+mincost);
System.out.println("\nMinimum span tree is");

for (i=1;i<=v;i++)
System.out.println("\nvertex "+i+" is connected to "+p[i]);
}   /*end of prim */
}



class Prim
{
public static void main(String args[])
{
Graph g=new Graph();
g.PrimAlgorithm();
}
}

/*
Enter number of vertices : 6

Enter number of edges : 9

Enter edge a,b and weight w : 1 2 6

Enter edge a,b and weight w : 1 3 3

Enter edge a,b and weight w : 2 3 2

Enter edge a,b and weight w : 2 4 5

Enter edge a,b and weight w : 3 5 4

Enter edge a,b and weight w : 3 4 3

Enter edge a,b and weight w : 4 5 2

Enter edge a,b and weight w : 4 6 3

Enter edge a,b and weight w : 5 6 5

Minimum cost = 13

Minimum span tree is

vertex 1 is connected to 0

vertex 2 is connected to 3

vertex 3 is connected to 1

vertex 4 is connected to 3

vertex 5 is connected to 4

vertex 6 is connected to 4
*/

To implement breadth first search algorithm

import java.io.*;
import java.util.*;
//--------------------------------------------------------------------------------
class Nodetype
{
int info;
   Arctype arcptr;
   Nodetype nextnode;
   Nodetype(int i)
{
info=i;
arcptr=null;
nextnode=null;
}
}
//--------------------------------------------------------------------------------
class Arctype
{

   Nodetype nodeptr;
   Arctype nextarc;
   Arctype()
{
nodeptr=null;
nextarc=null;
}
}
//--------------------------------------------------------------------------------



class Queue
{
/*array is used to hold queue elements*/
/*two integer variables are used for front and rear pointers*/
int items[]=new int[10];
int front,rear;

Queue()
{/*create queue*/
front=0;
rear=-1;
}/*end createqueue*/


void insert(int e)
{/*if queue is not full insert new element at rear end of queue*/
if(rear==9)
System.out.println("Queue overflow");
else
items[++rear]=e;
}/*end insert*/

int empty()
{/*Return 1 if queue is empty and 0 otherwise*/
return(rear<front? 1:0);
}/*end empty*/

int remove()
{/*if queue is not empty remove one element from front */

int x=0;
if(empty()==1)
{
System.out.println("Queue Underflow");
return 0;
}
else
{
x=items[front++];
return x;
}
/*end else*/
}/*end rem*/
}
//-------------------------------------------------------------------------------

class Operations
{
Nodetype graph=null;

void insertnode(int x)
{
/*insert new node at the end of linked graph*/

Nodetype node=new Nodetype(x);
Nodetype temp;
temp=graph;
if(temp==null)
graph=node;
else
{
while(temp.nextnode!=null)
temp=temp.nextnode;
temp.nextnode=node;
}
}/*end insertnode*/


void insertarc(int i)
{
/*insert new node at the end of linked graph*/
int x,ans;
Nodetype temp1,temp2;
Arctype temp3=null;

temp1=searchnode(i);
do
{
System.out.print("\nEnter adjacent node for node "+i+ " : ");
x=getNumber();
temp2=searchnode(x);
if (temp2!=null)
{
Arctype node=new Arctype();
node.nodeptr=temp2;
node.nextarc=null;

if (temp1.arcptr==null)
temp1.arcptr=node;
else
{
temp3=temp1.arcptr;
while (temp3.nextarc!=null)
temp3=temp3.nextarc;
temp3.nextarc=node;
}
}
System.out.print("\nContinue to add adjacent node for "+i+"(1/0)?");
ans=getNumber();
}while(ans==1);

System.out.print("\nNode "+i+ "is connected to : ");
temp3=temp1.arcptr;
do
{
System.out.print(" "+(temp3.nodeptr).info);
temp3=temp3.nextarc;
}while (temp3!=null);

}/*end insertarc*/


Nodetype searchnode(int x)
{
/*search an element in linked graph and return its location*/
int i=1;
Nodetype q;
if(graph==null)
{
System.out.println("\nList is empty");
return null;
}
else
{
q=graph;
do
{
if(q.info==x)
break;
i++;
q=q.nextnode;
}
while(q!=null);
if(q==null)
{
System.out.println("\nNode not found");
return null;
}
else
return q;
}
}/*end searchnode*/

int  adjacent(int u,int i)
{
int x,ans;
Nodetype temp1,temp2;
Arctype temp3=null;
temp1=searchnode(u);
temp3=temp1.arcptr;
do
{
if ((temp3.nodeptr).info==i)
return 1;
else
temp3=temp3.nextarc;
}while (temp3!=null);
return 0;
}/*end adjacent*/

void creategraph()
{
int i,n=0,x,ans1,initial_node;
System.out.println("Enter no. of nodes : ");
n=getNumber();
for(i=1;i<=n;i++)
insertnode(i);
for(i=1;i<=n;i++)
insertarc(i);
System.out.println("\nEnter the initial node for BFS traversal:");
initial_node=getNumber();
BFS(initial_node,n);
}/*end creategraph*/

void BFS (int initial_node,int n)
{
Queue q=new Queue();
int u,i;
u = initial_node;
int visited[]=new int[n+1];

visited[initial_node]=1;
System.out.println("\nBFS traversal for given graph is : ");
System.out.print(initial_node);
q.insert(initial_node);
while(q.empty()==0)
{
u = q.remove();
 for (i=1;i<=n;i++)
{
if((adjacent(u,i)==1) && (visited[i]==0))
{
 q.insert(i);
 visited[i]=1;
 System.out.print(" "+i);
}
 }
}
} /* end of BFS function    */


int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println("I/O Error");
}
return ne;
}

}
//-------------------------------------------------------------------------------

class Graph_Linked
{
public static void main(String args[])
{
Operations L =new Operations();
L.creategraph();
}
}

/*
Enter no. of nodes :
9

Enter adjacent node for node 1 : 2

Continue to add adjacent node for 1(1/0)?1

Enter adjacent node for node 1 : 3

Continue to add adjacent node for 1(1/0)?0

Node 1is connected to :  2 3
Enter adjacent node for node 2 : 1

Continue to add adjacent node for 2(1/0)?1

Enter adjacent node for node 2 : 4

Continue to add adjacent node for 2(1/0)?1

Enter adjacent node for node 2 : 5

Continue to add adjacent node for 2(1/0)?0

Node 2is connected to :  1 4 5
Enter adjacent node for node 3 : 1

Continue to add adjacent node for 3(1/0)?1

Enter adjacent node for node 3 : 5

Continue to add adjacent node for 3(1/0)?0

Node 3is connected to :  1 5
Enter adjacent node for node 4 : 2

Continue to add adjacent node for 4(1/0)?1

Enter adjacent node for node 4 : 6

Continue to add adjacent node for 4(1/0)?1

Enter adjacent node for node 4 : 7

Continue to add adjacent node for 4(1/0)?0

Node 4is connected to :  2 6 7
Enter adjacent node for node 5 : 2

Continue to add adjacent node for 5(1/0)?1

Enter adjacent node for node 5 : 3

Continue to add adjacent node for 5(1/0)?1

Enter adjacent node for node 5 : 8

Continue to add adjacent node for 5(1/0)?0

Node 5is connected to :  2 3 8
Enter adjacent node for node 6 : 4

Continue to add adjacent node for 6(1/0)?1

Enter adjacent node for node 6 : 9

Continue to add adjacent node for 6(1/0)?0

Node 6is connected to :  4 9
Enter adjacent node for node 7 : 4

Continue to add adjacent node for 7(1/0)?0

Node 7is connected to :  4
Enter adjacent node for node 8 : 5

Continue to add adjacent node for 8(1/0)?0

Node 8is connected to :  5
Enter adjacent node for node 9 : 6

Continue to add adjacent node for 9(1/0)?0

Node 9is connected to :  6
Enter the initial node for BFS traversal:
1

BFS traversal for given graph is :
1 2 3 4 5 6 7 8 9
*/