Untitled
unknownplain_text
25 days ago
14 kB
5
Indexable
Never
Prims algo
package prims;
import java.util.Scanner;
public class Prims_algo {
int n;
int a[][]=new int[10][10];
void read_adjacency_matrix()
{
System.out.println("***PRIMS ALGORITHM***");
System.out.println("enter number of nodes");
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
System.out.println("enter the cost adjacency matrix");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
a[i][j]=scan.nextInt();
}
}
scan.close();
}
void find_minimum_spanning_tree()
{
int min,u=0,v=0,k=0,count=0,cost=0,i,j;
int visited[]=new int[20];
int t[][]=new int[20][3];
visited[1]=1;
while(count!=(n-1))
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(visited[i]==1 && visited[j]==0 && min>a[i][j])
{
min=a[i][j];
u=i;
v=j;
}
}
}
if(min==999)
break;
t[k][0]=u;
t[k][1]=v;
t[k][2]=min;
visited[v]=1;
cost+=min;
k++;
count++;
}
if(count==n-1)
{
System.out.println("the min cost spanning tree with edjes is");
System.out.println("*************");
System.out.println("Edge"+"\t"+"Weight");
System.out.println("*************");
for(i=0;i<k;i++)
System.out.println(t[i][0]+"->"+t[i][1]+"\t"+t[i][2]);
System.out.println("**************");
System.out.println("cost of spanning tree="+cost);
System.out.println("*************");
}
else
System.out.println("spanning tree does not exist");
}
}
Prim.java
package prims;
public class prim {
public static void main(String[] args) {
Prims_algo p = new Prims_algo();
p.read_adjacency_matrix();
p.find_minimum_spanning_tree();
}
}
Knapsackdp
import java .util.*;
public class knapsackDP {
public void solve(int[] wt,int[] val,int W,int N){
int i,j;
int sol[][]=new int[N+1][W+1];
int selected[]=new int[N+1];
for (i=0;i<=N;i++){
for(j=0;j<=W;j++){
if(i==0 || j==0)
sol[i][j]=0;
else if(wt[i]>j)
sol[i][j]=sol[i-1][j];
else
sol[i][j]=Math.max(sol[i-1][j],(sol[i-1][j-wt[i]]+val[i]));
}
}
System.out.println("The profit table is: ");
for(i=0;i<=N;i++){
for(j=0;j<=W;j++){
System.out.print(sol[i][j]+" ");
}
System.out.println();
}
System.out.println("The optimal profit obtained is "+sol[N][W]);
i=N;
j=W;
while(i>0 && j>0){
if(sol[i][j]!=sol[i-1][j]){
selected[i]=1;
j=j-wt[i];
}
i--;
}
System.out.println("\nItems selected: ");
for(i=1;i<=N;i++){
if (selected[i]==1)
System.out.print(i+" ");
}
System.out.println();
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
knapsackDP ks=new knapsackDP();
System.out.println("******KANPSACK PROBLEM-DYNAMIC PROGRAMMING******");
System.out.println("Enter the number of elements: ");
int n=sc.nextInt();
int wt[]=new int[n+1];
int val[]=new int[n+1];
System.out.println("\nEnter weight for " +n+ " elements: ");
for (int i=1; i<=n;i++)
wt[i]=sc.nextInt();
System.out.println("\nEnter profit value for " +n+ " elements: ");
for (int i=1; i<=n;i++)
val[i]=sc.nextInt();
System.out.println("\nEnter knapsack weight: ");
int W=sc.nextInt();
sc.close();
ks.solve(wt,val,W,n);
}
}
Dijkstra
import java.util.Scanner;
public class Dijkstra
{
int n,src;
int a[][]=new int[10][10];
void read_cost_adjacency_matrix()
{
System.out.println("***DIJKSTRA'S ALGORITHM***");
System.out.println("Enter no.of nodes: ");
Scanner sobj=new Scanner(System.in);
n=sobj.nextInt();
System.out.println("Enter the cost adjacency matrix: ");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
a[i][j]=sobj.nextInt();
}
}
System.out.println("Enter the source vertex: ");
src=sobj.nextInt();
sobj.close();
}
void find_short_distance_path()
{
int i,j,v,min,u=0;
int d[]=new int[10];
int p[]=new int[10];
int s[]=new int[10];
for(i=1;i<=n;i++)
{
d[i]=a[src][i];
p[i]=src;
s[i]=0;
}
s[src]=1;
d[src]=0;
for(i=1;i<n;i++)
{
for(j=1,min=999;j<=n;j++)
{
if(s[j]==0 && d[j]<min)
{
min=d[j];
u=j;
}
}
s[u]=1;
for(v=1;v<=n;v++)
{
if(s[v]==0 && d[u]+a[u][v]<d[v])
{
d[v]=d[u]+a[u][v];
p[v]=u;
}
}
}
System.out.println("The shortest path and distance is shown below: ");
System.out.println("DEST VERTEX<-(Intermediate vertices)<-SOURCE=DISTANCE ");
for(j=1;j<=n;j++)
{
if(d[i]==999)
System.out.println(j+"<-"+src+"="+d[j]);
else if(d[i]==0)
System.out.println(j+"<-"+src+"="+d[j]);
else
{
i=j;
while(i!=src)
{
System.out.println(i+"<-");
i=p[i];
}
System.out.println(i+"="+d[j]);
}
}
}
public static void main(String[] args) {
Dijkstra ob=new Dijkstra();
ob.read_cost_adjacency_matrix();
ob.find_short_distance_path();
}
}
Fractional knapsack
import java.util.Scanner;
public class FractionalKnapsack {
double weight[];
double profit[];
double ratio[];
double cap;
int nItems;
FractionalKnapsack()
{
Scanner scan=new Scanner(System.in);
System.out.println("***KNAPSACK PROBLEM-GREEDY METHOD***");
System.out.println("Enter the number of items in the store :");
nItems=scan.nextInt();
System.out.println("Enter the weight and profit of the items");
weight = new double[nItems];
profit = new double[nItems];
ratio = new double[nItems];
for(int i=0;i<nItems;++i)
{
weight[i]=scan.nextDouble();
profit[i]=scan.nextDouble();
ratio[i]=profit[i]/weight[i];
}
System.out.println("Enter the capacity of the knapsack");
cap=scan.nextDouble();
scan.close();
}
int getNext()
{
double max=0;
int index=-1;
for(int i=0;i<profit.length;i++)
{
if(ratio[i]>max)
{
max=ratio[i];
index=i;
}
}
return index;
}
void fill()
{
double cW=0,cP=0;
double select[]=new double[nItems];
while(cW<cap)
{
int item=getNext();
if(item==-1)
break;
if(cW+weight[item]<=cap)
{
cW+=weight[item];
cP+=profit[item];
ratio[item]=0;
select[item]=1;
}
else
{
select[item]=(cap-cW)/weight[item];
cP+=(ratio[item]*(cap-cW));
cW+=(cap-cW);
break;
}
}
System.out.println("\nItems Selected Fractio Selected(0/1/Partial)");
System.out.println("*********");
for(int i=0;i<nItems;i++)
System.out.println("\t"+(i+1)+"\t\t"+select[i]);
System.out.println("\nMax Profit="+cP+",Max Weight="+cW);
}
public static void main(String[] args) {
FractionalKnapsack fk= new FractionalKnapsack();
fk.fill();
}
}
Mergesort
import java.util.*;
//import java.util.Random;
public class MergeSort
{
static int max=30000;
public static void main(String[]args)
{
long start,end;
Scanner sc = new Scanner(System.in);
System.out.println("Enter the length of array:");
int n = sc.nextInt();
int a[] = new int[max];
Random r = new Random();
for(int i=0; i<n; i++)
{
a[i] = r.nextInt(100);
}
sc.close();
System.out.println("The array elements to be sorted are:");
for(int i =0; i<n; i++)
{
System.out.println(a[i]+" ");
}
start=System.nanoTime();
mergeSort(a,0,n-1);
end=System.nanoTime();
System.out.println("The sorted elements are:");
for(int i =0; i<n; i++)
{
System.out.println(a[i]+" ");
}
System.out.println("\n Time taken to sort is" +(end-start)+ "ns");
}
static void mergeSort(int a[], int low, int high)
{
if(low < high)
{
int mid = (low + high)/2;
mergeSort(a, low, mid);
mergeSort(a, mid+1, high);
Merge(a, low, mid, high);
}
}
static void Merge(int a[], int low, int mid, int high )
{
int i,j,h,k;
int b[] = new int[max];
i = low;
h=low;
j = mid+1;
while((h <= mid) && (j<= high))
{
if(a[h]< a[j])
{
b[i] = a[h];
h=h+1;
}
else
{
b[i]= a[j];
j=j+1;
}
i=i+1;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i=i+1;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i=i+1;
}
}
for(k=low;k<=high;k++)
{
a[k]=b[k];
}
}
}
Quicksort
import java.util.*;
public class quicksort {
static int max=30000;
public static void main(String[] args) {
int a[]=new int[max];
long start,end;
Scanner sc=new Scanner(System.in);
System.out.println("****QUICK SORT ALGORITHM****");
System.out.println("Enter the no. of elements to be sorted:");
int n=sc.nextInt();
sc.close();
Random random=new Random();
for(int i=0;i<n;i++)
{
a[i]=random.nextInt(100);
}
System.out.println("Array elements to be sorted are:");
for(int i=0;i<n;i++)
{
System.out.println(a[i]+" ");
}
a[n]=9999;
start=System.nanoTime();
qsort(a,0,n-1);
end=System.nanoTime();
System.out.println("\nThe sorted elements are:");
for(int i=0;i<n;i++)
{
System.out.println(a[i]+" ");
}
System.out.println("\n The time taken to sort is " +(end-start)+ " ns");
System.out.println("**************");
}
static void qsort(int a[],int low,int high)
{
int s;
if(low<high)
{
s=partition(a,low,high);
qsort(a,low,s-1);
qsort(a,s+1,high);
}
}
static int partition(int a[],int low,int high)
{
int pivot,i,j;
pivot=a[low];
i=low;
j=high;
while(i<=j)
{
while(a[i]<=pivot)
i++;
while(a[j]>pivot)
j--;
if(i<j)
swap(a,i,j);
}
a[low]=a[j];
a[j]=pivot;
return j;
}
static void swap(int a[],int i,int j)
{
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
Selectionsort
import java.util.*;
public class SelectionSort {
static void sort(int a[],int n){
for(int i=0;i<n-1;i++){
int min=i;
for(int j=i+1;j<n;j++){
if(a[j]<a[min])
min=j;
}
int temp=a[min];
a[min]=a[i];
a[i]=temp;
}
}
public static void main(String[] args) {
//SelectionSort ob=new SelectionSort();
int a[]=new int[50000];
long start,end;
Scanner sc=new Scanner(System.in);
System.out.println("Selection Sort Algorithm");
System.out.println("Enter the number of elements to be sorted: ");
int n = sc.nextInt();
Random r=new Random();
for(int i=0; i<n; i++)
a[i] = r.nextInt(100);
System.out.println("The elements to be sorted are:");
for(int i =0; i<n; i++)
System.out.println(a[i]+" ");
start=System.nanoTime();
sort(a,n);
end=System.nanoTime();
System.out.println("The sorted elements are:");
for(int i =0; i<n; i++)
System.out.println(a[i]+" ");
System.out.println("\n Time taken to sort is"+(end-start)+"ns");
sc.close();
}
}
Kruskal_algo
import java.util.Scanner;
public class kruskal_algo {
int n;
int a[][]=new int [10][10];
void read_cost_adjacency_matrix()
{
System.out.println("***KRUSKAL'S ALGORITHM***");
System.out.println("enter number of nodes");
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
System.out.println("enter the cost adjacency matrix");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
a[i][j]=scan.nextInt();
}
}
scan.close();
}
void find_minimum_spanningtree()
{
int parent[]=new int[10];
int t[][]=new int[10][3];
for(int i=1;i<=n;i++)
{
parent[i]=i;
}
int count=0,sum=0,k=0,u=0,v=0;
while(count!=n-1)
{
int min=999;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]!=0 && a[i][j]<min)
{
min=a[i][j];
u=i;
v=j;
}
}
}
if(min==999)
break;
int i=u;
while(parent[i]!=i)
i=parent[i];
int j=v;
while(parent[j]!=j)
j=parent[j];
if(i!=j)
{
t[k][0]=u;
t[k][1]=v;
t[k][2]=min;
k++;
sum =sum+min;
parent[j]=i;
count++;
}
a[u][v]=a[v][u]=999;
}
if(count==n-1)
{
System.out.println("the min cost spanning tree with edges is");
System.out.println("**********");
System.out.println("Edge"+"\t"+"Weight");
System.out.println("**********");
for(int i=0;i<n-1;i++)
System.out.println(t[i][0]+"->"+t[i][1]+"\t"+t[i][2]);
System.out.println("Cost of the Spanning tree="+sum);
}
else
System.out.println("Spanning tree does not exist");
}
}
kruskal.java
public class kruskal {
public static void main(String[] args) {
kruskal_algo k=new kruskal_algo();
k.read_cost_adjacency_matrix();
k.find_minimum_spanningtree();
}
}
Floyd Algo
import java.lang.*;
import java.util.Scanner;
public class Floyd
{
int d[][]=new int[10][10];
public void dis_path(int n,int a[][])
{
for(int i=0;i<n;i++)
{
for(int j=0; j<n;j++)
{
d[i][j]=a[i][j];
}
}
for(int k=0;k<n;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
d[i][j]=Math.min(d[i][j],(d[i][k]+d[k][j]));
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
System.out.print(d[i][j]+"");
}
System.out.println();
}
}
}
public class Floyed {
public static void main(String[] args)
{
int n;
int a[][]=new int[10][10];
Scanner sobj=new Scanner(System.in);
Floyd f =new Floyd();
System.out.println("****FLOYEDS ALGORITHM****");
System.out.println("Enter the number of nodes:");
n=sobj.nextInt();
System.out.println("Enter the cost adjacency matrix:");
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
a[i][j]=sobj.nextInt();
}
System.out.println("Resultant shortest path matrix is:");
f.dis_path(n, a);
sobj.close();
}
}