Untitled

mail@pastecode.io avatarunknown
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();
	}

}