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