Daa lab all programs

Manual 👇👇

All programs are well executed no error will come if error comes comment below...

1. Write a java program to implement the backtracking algorithm for the sum of subsets problem.

Save as: Main.java

import java.util.*;
public class Main
{
  static int w[], x[], i, j, s = 0, k = 1, r = 0, m, n;
  void read ()
  {
    Scanner s = new Scanner (System.in);
      System.out.println ("Plaese enter the number of values");
      n = s.nextInt ();
      w = new int[n + 1];
      x = new int[n + 1];
      System.out.println ("Plaese enter the corresponding weights");
    for (i = 1; i <= n; i++)
      {
  System.out.println ("Please enter the weight");
  w[i] = s.nextInt ();
  r += w[i];
  x[i] = 0;
      }
    System.out.println ("Please enter the total sum");
    m = s.nextInt ();
  }
  void sumOfSubset (int s, int k, int r)
  {
    if (s + w[k] == m)
      {
  x[i] = 1;
  System.out.println ("Possible Solutions are");
  for (i = 1; i <= n; i++)
    System.out.print (" " + x[i]);
  System.out.println ();
      }
    else if (s + w[k] + w[k + 1] <= m)
      {
  x[k] = 1;
  sumOfSubset (s + w[k], k + 1, r - w[k]);
      }
    if ((s + r - w[k] >= m) && (s + w[k + 1] <= m))
      {
  x[k] = 0;
  sumOfSubset (s, k + 1, r - w[k]);
      }
  }
  public static void main (String args[])
  {
    Main ss = new Main ();
    ss.read ();
    ss.sumOfSubset (s, k, r);
  }
}
import java.util.*;
public class Main
{
  static int w[], x[], i, j, s = 0, k = 1, r = 0, m, n;
  void read ()
  {
    Scanner s = new Scanner (System.in);
      System.out.print("Please enter the number of values: ");
      n = s.nextInt();
      w = new int[n + 1];
      x = new int[n + 1];
    for (i = 1; i <= n; i++)
      {
  System.out.print("Please enter the weight "+i+": ");
  w[i] = s.nextInt();
  r += w[i];
  x[i] = 0;
      }
    System.out.print("Please enter the total sum: ");
    m = s.nextInt ();
  }
  void sumOfSubset (int s, int k, int r)
  {
    if (s + w[k] == m)
      {
  x[i] = 1;
  System.out.println ("Possible Solutions are");
  for (i = 1; i <= n; i++)
    System.out.print (" " + x[i]);
  System.out.println ();
      }
    else if (s + w[k] + w[k + 1] <= m)
      {
  x[k] = 1;
  sumOfSubset (s + w[k], k + 1, r - w[k]);
      }
    if ((s + r - w[k] >= m) && (s + w[k + 1] <= m))
      {
  x[k] = 0;
  sumOfSubset (s, k + 1, r - w[k]);
      }
  }
  public static void main (String args[])
  {
    Main ss = new Main ();
    ss.read ();
    ss.sumOfSubset (s, k, r);
  }
}
/*output 
Please enter the number of values: 5
Please enter the weight 1: 12
Please enter the weight 2: 1
Please enter the weight 3: 3
Please enter the weight 4: 5
Please enter the weight 5: 6
Please enter the total sum: 2
*/import java.util.*;
public class Main
{
  static int w[], x[], i, j, s = 0, k = 1, r = 0, m, n;
  void read ()
  {
    Scanner s = new Scanner (System.in);
      System.out.println ("Plaese enter the number of values");
      n = s.nextInt ();
      w = new int[n + 1];
      x = new int[n + 1];
      System.out.println ("Plaese enter the corresponding weights");
    for (i = 1; i <= n; i++)
      {
  System.out.println ("Please enter the weight");
  w[i] = s.nextInt ();
  r += w[i];
  x[i] = 0;
      }
    System.out.println ("Please enter the total sum");
    m = s.nextInt ();
  }
  void sumOfSubset (int s, int k, int r)
  {
    if (s + w[k] == m)
      {
  x[i] = 1;
  System.out.println ("Possible Solutions are");
  for (i = 1; i <= n; i++)
    System.out.print (" " + x[i]);
  System.out.println ();
      }
    else if (s + w[k] + w[k + 1] <= m)
      {
  x[k] = 1;
  sumOfSubset (s + w[k], k + 1, r - w[k]);
      }
    if ((s + r - w[k] >= m) && (s + w[k + 1] <= m))
      {
  x[k] = 0;
  sumOfSubset (s, k + 1, r - w[k]);
      }
  }
  public static void main (String args[])
  {
    Main ss = new Main ();
    ss.read ();
    ss.sumOfSubset (s, k, r);
  }
}
import java.util.*;
public class Main
{
  static int w[], x[], i, j, s = 0, k = 1, r = 0, m, n;
  void read ()
  {
    Scanner s = new Scanner (System.in);
      System.out.print("Please enter the number of values: ");
      n = s.nextInt();
      w = new int[n + 1];
      x = new int[n + 1];
    for (i = 1; i <= n; i++)
      {
  System.out.print("Please enter the weight "+i+": ");
  w[i] = s.nextInt();
  r += w[i];
  x[i] = 0;
      }
    System.out.print("Please enter the total sum: ");
    m = s.nextInt ();
  }
  void sumOfSubset (int s, int k, int r)
  {
    if (s + w[k] == m)
      {
  x[i] = 1;
  System.out.println ("Possible Solutions are");
  for (i = 1; i <= n; i++)
    System.out.print (" " + x[i]);
  System.out.println ();
      }
    else if (s + w[k] + w[k + 1] <= m)
      {
  x[k] = 1;
  sumOfSubset (s + w[k], k + 1, r - w[k]);
      }
    if ((s + r - w[k] >= m) && (s + w[k + 1] <= m))
      {
  x[k] = 0;
  sumOfSubset (s, k + 1, r - w[k]);
      }
  }
  public static void main (String args[])
  {
    Main ss = new Main ();
    ss.read ();
    ss.sumOfSubset (s, k, r);
  }
}
/*output 
Please enter the number of values: 5
Please enter the weight 1: 12
Please enter the weight 2: 1
Please enter the weight 3: 3
Please enter the weight 4: 5
Please enter the weight 5: 6
Please enter the total sum: 2
*/import java.util.*;
public class Main
{
  static int w[], x[], i, j, s = 0, k = 1, r = 0, m, n;
  void read ()
  {
    Scanner s = new Scanner (System.in);
      System.out.println ("Plaese enter the number of values");
      n = s.nextInt ();
      w = new int[n + 1];
      x = new int[n + 1];
      System.out.println ("Plaese enter the corresponding weights");
    for (i = 1; i <= n; i++)
      {
  System.out.println ("Please enter the weight");
  w[i] = s.nextInt ();
  r += w[i];
  x[i] = 0;
      }
    System.out.println ("Please enter the total sum");
    m = s.nextInt ();
  }
  void sumOfSubset (int s, int k, int r)
  {
    if (s + w[k] == m)
      {
  x[i] = 1;
  System.out.println ("Possible Solutions are");
  for (i = 1; i <= n; i++)
    System.out.print (" " + x[i]);
  System.out.println ();
      }
    else if (s + w[k] + w[k + 1] <= m)
      {
  x[k] = 1;
  sumOfSubset (s + w[k], k + 1, r - w[k]);
      }
    if ((s + r - w[k] >= m) && (s + w[k + 1] <= m))
      {
  x[k] = 0;
  sumOfSubset (s, k + 1, r - w[k]);
      }
  }
  public static void main (String args[])
  {
    Main ss = new Main ();
    ss.read ();
    ss.sumOfSubset (s, k, r);
  }
}
import java.util.*;
public class Main
{
  static int w[], x[], i, j, s = 0, k = 1, r = 0, m, n;
  void read ()
  {
    Scanner s = new Scanner (System.in);
      System.out.print("Please enter the number of values: ");
      n = s.nextInt();
      w = new int[n + 1];
      x = new int[n + 1];
    for (i = 1; i <= n; i++)
      {
  System.out.print("Please enter the weight "+i+": ");
  w[i] = s.nextInt();
  r += w[i];
  x[i] = 0;
      }
    System.out.print("Please enter the total sum: ");
    m = s.nextInt ();
  }
  void sumOfSubset (int s, int k, int r)
  {
    if (s + w[k] == m)
      {
  x[i] = 1;
  System.out.println ("Possible Solutions are");
  for (i = 1; i <= n; i++)
    System.out.print (" " + x[i]);
  System.out.println ();
      }
    else if (s + w[k] + w[k + 1] <= m)
      {
  x[k] = 1;
  sumOfSubset (s + w[k], k + 1, r - w[k]);
      }
    if ((s + r - w[k] >= m) && (s + w[k + 1] <= m))
      {
  x[k] = 0;
  sumOfSubset (s, k + 1, r - w[k]);
      }
  }
  public static void main (String args[])
  {
    Main ss = new Main ();
    ss.read ();
    ss.sumOfSubset (s, k, r);
  }
}
/*output 
Please enter the number of values: 5
Please enter the weight 1: 12
Please enter the weight 2: 1
Please enter the weight 3: 3
Please enter the weight 4: 5
Please enter the weight 5: 6
Please enter the total sum: 2
*/import java.util.*;
public class Main
{
  static int w[], x[], i, j, s = 0, k = 1, r = 0, m, n;
  void read ()
  {
    Scanner s = new Scanner (System.in);
      System.out.println ("Plaese enter the number of values");
      n = s.nextInt ();
      w = new int[n + 1];
      x = new int[n + 1];
      System.out.println ("Plaese enter the corresponding weights");
    for (i = 1; i <= n; i++)
      {
  System.out.println ("Please enter the weight");
  w[i] = s.nextInt ();
  r += w[i];
  x[i] = 0;
      }
    System.out.println ("Please enter the total sum");
    m = s.nextInt ();
  }
  void sumOfSubset (int s, int k, int r)
  {
    if (s + w[k] == m)
      {
  x[i] = 1;
  System.out.println ("Possible Solutions are");
  for (i = 1; i <= n; i++)
    System.out.print (" " + x[i]);
  System.out.println ();
      }
    else if (s + w[k] + w[k + 1] <= m)
      {
  x[k] = 1;
  sumOfSubset (s + w[k], k + 1, r - w[k]);
      }
    if ((s + r - w[k] >= m) && (s + w[k + 1] <= m))
      {
  x[k] = 0;
  sumOfSubset (s, k + 1, r - w[k]);
      }
  }
  public static void main (String args[])
  {
    Main ss = new Main ();
    ss.read ();
    ss.sumOfSubset (s, k, r);
  }
}
import java.util.*;
public class Main
{
  static int w[], x[], i, j, s = 0, k = 1, r = 0, m, n;
  void read ()
  {
    Scanner s = new Scanner (System.in);
      System.out.print("Please enter the number of values: ");
      n = s.nextInt();
      w = new int[n + 1];
      x = new int[n + 1];
    for (i = 1; i <= n; i++)
      {
  System.out.print("Please enter the weight "+i+": ");
  w[i] = s.nextInt();
  r += w[i];
  x[i] = 0;
      }
    System.out.print("Please enter the total sum: ");
    m = s.nextInt ();
  }
  void sumOfSubset (int s, int k, int r)
  {
    if (s + w[k] == m)
      {
  x[i] = 1;
  System.out.println ("Possible Solutions are");
  for (i = 1; i <= n; i++)
    System.out.print (" " + x[i]);
  System.out.println ();
      }
    else if (s + w[k] + w[k + 1] <= m)
      {
  x[k] = 1;
  sumOfSubset (s + w[k], k + 1, r - w[k]);
      }
    if ((s + r - w[k] >= m) && (s + w[k + 1] <= m))
      {
  x[k] = 0;
  sumOfSubset (s, k + 1, r - w[k]);
      }
  }
  public static void main (String args[])
  {
    Main ss = new Main ();
    ss.read ();
    ss.sumOfSubset (s, k, r);
  }
}
/*output 
Please enter the number of values: 5
Please enter the weight 1: 12
Please enter the weight 2: 1
Please enter the weight 3: 3
Please enter the weight 4: 5
Please enter the weight 5: 6
Please enter the total sum: 2
*/

2.Write a java program to implement the backtracking algorithm for the Hamiltonian Circuits problem.

Save as: Main.java

import java.util.*;
public class Main
{
  final int V = 5;
  int path[];
  boolean isSafe (int v, int graph[][], int path[], int pos)
  {
    if (graph[path[pos - 1]][v] == 0)
      return false;
    for (int i = 0; i < pos; i++)
      if (path[i] == v)
  return false;
    return true;
  }
  boolean hamCycleUtil (int graph[][], int path[], int pos)
  {
    if (pos == V)
      {
  if (graph[path[pos - 1]][path[0]] == 1)
    return true;
  else
    return false;
      }
    for (int v = 1; v < V; v++)
      {
  if (isSafe (v, graph, path, pos))
    {
      path[pos] = v;
      if (hamCycleUtil (graph, path, pos + 1) == true)
        return true;
      path[pos] = -1;
    }
      }
    return false;
  }
  int hamCycle (int graph[][])
  {
    path = new int[V];
    for (int i = 0; i < V; i++)
      path[i] = -1;
    path[0] = 0;
    if (hamCycleUtil (graph, path, 1) == false)
      {
  System.out.println ("\nSolution does not exist");
  return 0;
      }

printSolution (path);
    return 1;
  }
  void printSolution (int path[])
  {
    System.out.println ("Solution Exists: Following" +
      " is one Hamiltonian Cycle");
    for (int i = 0; i < V; i++)
      System.out.print (" " + path[i] + " ");
    System.out.println (" " + path[0] + " ");
  }
  public static void main (String args[])
  {
    Main m = new Main ();
    int graph1[][] = { {0, 1, 0, 1, 0},
    {1, 0, 1, 1, 1},
    {0, 1, 0, 0, 1},
    {1, 1, 0, 0, 1},
    {0, 1, 1, 1, 0},
    };
    m.hamCycle (graph1);
    int graph2[][] = { {0, 1, 0, 1, 0},
    {1, 0, 1, 1, 1},
    {0, 1, 0, 0, 1},
    {1, 1, 0, 0, 0},
    {0, 1, 1, 0, 0},
    };
    m.hamCycle (graph2);
  }
}
/*output
Solution Exists: Following is one Hamiltonian Cycle
 0  1  2  4  3  0

Solution does not exist

3. Write a java program to implement greedy algorithm for job sequencing with deadlines.

Save as:

import java.util.*;
class job
{
int p,d,v;    
job()
{
p=0;
d=0;
v=0;
}
job(int x,int y,int z)
{
p=x;
d=y;
v=z;
}
}
public class Main
// class js
{
static int n; 
static int out(job jb[],int x)
{
for(int i=0;i<n;++i)
if(jb[i].p==x)
return i;
return 0;
}
public static void main(String args[])
{
Scanner scr=new Scanner(System.in);
System.out.print("Enter the number of jobs: ");
n=scr.nextInt();
int max=0; 
job jb[]=new job[n];
for(int i=0;i<n;++i)
{
System.out.print("Enter profit and deadline(p"+i+" "+"d"+i+"): ");
int p=scr.nextInt();
int d=scr.nextInt();
if(max<d)
max=d;   
jb[i]=new job(p,d,0); 
}
for(int i=0;i<=n-2;++i)
{
 for(int j=i;j<=n-1;++j)
 {
   if(jb[i].d>jb[j].d)
   {
     job temp=jb[i];
     jb[i]=jb[j];
     jb[j]=temp;
   }
 }
}
System.out.println("The jobs are as follows ");
for(int i=0;i<n;++i)
System.out.println("Job "+i+" Profit = "+jb[i].p+" Deadline = "+jb[i].d);
int count;
int hold[]=new int[max];
for(int i=0;i<max;++i)
hold[i]=0;
for(int i=0;i<n;++i)
{
count=0;
  for(int j=0;j<n;++j)
  {
    
   if(count<jb[j].d && jb[j].v==0 && count<max && jb[j].p>hold[count])
   { 
     int ch=0;
     
  if(hold[count]!=0)
     {
  ch=out(jb,hold[count]);
     jb[ch].v=0;
  }
  
  hold[count]=jb[j].p;
  jb[j].v=1;
     ++count;
  
  }
  
  } 
}
int profit=0;
for(int i=0;i<max;++i)
profit+=hold[i];
System.out.println("The maximum profit is "+profit);

}
}
/*output
Enter the number of jobs: 4
Enter profit and deadline(p0 d0): 32 4
Enter profit and deadline(p1 d1): 56 7
Enter profit and deadline(p2 d2): 12 9
Enter profit and deadline(p3 d3): 34 2
The jobs are as follows 
Job 0 Profit = 34 Deadline = 2
Job 1 Profit = 32 Deadline = 4
Job 2 Profit = 56 Deadline = 7
Job 3 Profit = 12 Deadline = 9
The maximum profit is 134

4.Write a java program to implement Dijkstra’s algorithm for the Single source shortest path problem.

Save as:

import java.util.*;
import java.io.*;
class Main
{
  static final int V = 9;
  int minDistance (int dist[], Boolean sptSet[])
  {
    int min = Integer.MAX_VALUE, min_index = -1;

for (int v = 0; v < V; v++)
      if (sptSet[v] == false && dist[v] <= min)
  {
    min = dist[v];
    min_index = v;
  }

return min_index;
  }
  void printSolution (int dist[], int n)
  {
    System.out.println ("Vertex   Distance from Source");
    for (int i = 0; i < V; i++)
      System.out.println (i + " tt " + dist[i]);
  }
  void dijkstra (int graph[][], int src)
  {
    int dist[] = new int[V];
    Boolean sptSet[] = new Boolean[V];
    for (int i = 0; i < V; i++)
      {
  dist[i] = Integer.MAX_VALUE;
  sptSet[i] = false;
      }
    dist[src] = 0;
    for (int count = 0; count < V - 1; count++)
      {
  int u = minDistance (dist, sptSet);
  sptSet[u] = true;
  for (int v = 0; v < V; v++)
    if (!sptSet[v] && graph[u][v] != 0 &&
        dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])
      dist[v] = dist[u] + graph[u][v];
      }
    printSolution (dist, V);
  }
  public static void main (String[]args)
  {
    int graph[][] = new int[][]{ {0, 4, 0, 0, 0, 0, 0, 8, 0},
    {4, 0, 8, 0, 0, 0, 0, 11, 0},
    {0, 8, 0, 7, 0, 4, 0, 0, 2},
    {0, 0, 7, 0, 9, 14, 0, 0, 0},
    {0, 0, 0, 9, 0, 10, 0, 0, 0},
    {0, 0, 4, 14, 10, 0, 2, 0, 0},
    {0, 0, 0, 0, 0, 2, 0, 1, 6},
    {8, 11, 0, 0, 0, 0, 1, 0, 7},
    {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };
    Main t = new Main ();
    t.dijkstra (graph, 0);
  }
}
/*output
Vertex   Distance from Source
0 tt 0
1 tt 4
2 tt 12
3 tt 19
4 tt 21
5 tt 11
6 tt 9
7 tt 8
8 tt 14
*/

5. Write a java program that implements Prim's algorithm to generate minimum cost spanning tree.

Save as:

import java.util.*;
import java.io.*;
class Main
{
  private static final int V = 5;
  int minKey (int key[], Boolean mstSet[])
  {
    int min = Integer.MAX_VALUE, min_index = -1;
    for (int v = 0; v < V; v++)
      if (mstSet[v] == false && key[v] < min)
  {
    min = key[v];
    min_index = v;
  }

return min_index;
  }
  void printMST (int parent[], int n, int graph[][])
  {
    System.out.println ("Edge   Weight");
    for (int i = 1; i < V; i++)
      System.out.println (parent[i] + " - " + i + "    " +
        graph[i][parent[i]]);
  }
  void primMST (int graph[][])
  {
    int parent[] = new int[V];
    int key[] = new int[V];
    Boolean mstSet[] = new Boolean[V];
    for (int i = 0; i < V; i++)
      {
  key[i] = Integer.MAX_VALUE;
  mstSet[i] = false;
      }
    key[0] = 0;
    parent[0] = -1;
    for (int count = 0; count < V - 1; count++)
      {
  int u = minKey (key, mstSet);
  mstSet[u] = true;
  for (int v = 0; v < V; v++)
    if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v])
      {
        parent[v] = u;
        key[v] = graph[u][v];
      }
      }
    printMST (parent, V, graph);
  }

public static void main (String[]args)
  {
    Main t = new Main ();
    int graph[][] = new int[][]{ {0, 2, 0, 6, 0},
    {2, 0, 3, 8, 5},
    {0, 3, 0, 0, 7},
    {6, 8, 0, 0, 9},
    {0, 5, 7, 9, 0},
    };
    t.primMST (graph);
  }
}
//Write a java program that implements Prim's algorithm to generate minimum cost spanning tree.
import java.util.*;
import java.io.*;
class Main
{
  private static final int V = 5;
  int minKey (int key[], Boolean mstSet[])
  {
    int min = Integer.MAX_VALUE, min_index = -1;
    for (int v = 0; v < V; v++)
      if (mstSet[v] == false && key[v] < min)
  {
    min = key[v];
    min_index = v;
  }

6. Write a java program that implements Kruskal's algorithm to generate minimum cost spanning tree

Save as:

import java.util.*;
import java.io.*;
class Main
{
  class Edge implements Comparable < Edge >
  {
    int src, dest, weight;
    public int compareTo (Edge compareEdge)
    {
      return this.weight - compareEdge.weight;
    }
  };
  class subset
  {
    int parent, rank;
  };
  int V, E;
  Edge edge[];
  Main (int v, int e)
  {
    V = v;
    E = e;
    edge = new Edge[E];
    for (int i = 0; i < e; ++i)
      edge[i] = new Edge ();
  }
  int find (subset subsets[], int i)
  {
    if (subsets[i].parent != i)
      subsets[i].parent = find (subsets, subsets[i].parent);
    return subsets[i].parent;
  }
  void Union (subset subsets[], int x, int y)
  {
    int xroot = find (subsets, x);
    int yroot = find (subsets, y);
    if (subsets[xroot].rank < subsets[yroot].rank)
      subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
      subsets[yroot].parent = xroot;
    else
      {
  subsets[yroot].parent = xroot;
  subsets[xroot].rank++;
      }
  }
  void KruskalMST ()
  {
    Edge result[] = new Edge[V];
    int e = 0, i = 0;
    for (i = 0; i < V; ++i)
      result[i] = new Edge ();
    Arrays.sort (edge);
    subset subsets[] = new subset[V];
    for (i = 0; i < V; ++i)
      subsets[i] = new subset ();
    for (int v = 0; v < V; ++v)
      {
  subsets[v].parent = v;
  subsets[v].rank = 0;
      }
    i = 0;
    while (e < V - 1)
      {
  Edge next_edge = new Edge ();
  next_edge = edge[i++];

int x = find (subsets, next_edge.src);
  int y = find (subsets, next_edge.dest);
  if (x != y)
    {
      result[e++] = next_edge;
      Union (subsets, x, y);
    }
      }
    System.out.println ("Following are the edges in " +
      "the constructed MST");
    for (i = 0; i < e; ++i)
      System.out.println (result[i].src + " -- " +
        result[i].dest + " == " + result[i].weight);
  }
  public static void main (String[]args)
  {
    int V = 4;
    int E = 5;
    Main graph = new Main (V, E);
    graph.edge[0].src = 0;
    graph.edge[0].dest = 1;
    graph.edge[0].weight = 10;

graph.edge[1].src = 0;
    graph.edge[1].dest = 2;
    graph.edge[1].weight = 6;

graph.edge[2].src = 0;
    graph.edge[2].dest = 3;
    graph.edge[2].weight = 5;

graph.edge[3].src = 1;
    graph.edge[3].dest = 3;
    graph.edge[3].weight = 15;

graph.edge[4].src = 2;
    graph.edge[4].dest = 3;
    graph.edge[4].weight = 4;

graph.KruskalMST ();
  }
}
/*output
Following are the edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
*//*Write a java program that implements Kruskal's algorithm to generate minimum cost
spanning tree*/
import java.util.*;
import java.io.*;
class Main
{
  class Edge implements Comparable < Edge >
  {
    int src, dest, weight;
    public int compareTo (Edge compareEdge)
    {
      return this.weight - compareEdge.weight;
    }
  };
  class subset
  {
    int parent, rank;
  };
  int V, E;
  Edge edge[];
  Main (int v, int e)
  {
    V = v;
    E = e;
    edge = new Edge[E];
    for (int i = 0; i < e; ++i)
      edge[i] = new Edge ();
  }
  int find (subset subsets[], int i)
  {
    if (subsets[i].parent != i)
      subsets[i].parent = find (subsets, subsets[i].parent);
    return subsets[i].parent;
  }
  void Union (subset subsets[], int x, int y)
  {
    int xroot = find (subsets, x);
    int yroot = find (subsets, y);
    if (subsets[xroot].rank < subsets[yroot].rank)
      subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
      subsets[yroot].parent = xroot;
    else
      {
  subsets[yroot].parent = xroot;
  subsets[xroot].rank++;
      }
  }
  void KruskalMST ()
  {
    Edge result[] = new Edge[V];
    int e = 0, i = 0;
    for (i = 0; i < V; ++i)
      result[i] = new Edge ();
    Arrays.sort (edge);
    subset subsets[] = new subset[V];
    for (i = 0; i < V; ++i)
      subsets[i] = new subset ();
    for (int v = 0; v < V; ++v)
      {
  subsets[v].parent = v;
  subsets[v].rank = 0;
      }
    i = 0;
    while (e < V - 1)
      {
  Edge next_edge = new Edge ();
  next_edge = edge[i++];

graph.edge[1].src = 0;
    graph.edge[1].dest = 2;
    graph.edge[1].weight = 6;

graph.edge[2].src = 0;
    graph.edge[2].dest = 3;
    graph.edge[2].weight = 5;

graph.edge[3].src = 1;
    graph.edge[3].dest = 3;
    graph.edge[3].weight = 15;

graph.edge[4].src = 2;
    graph.edge[4].dest = 3;
    graph.edge[4].weight = 4;

graph.KruskalMST ();
  }
}
/*output
Following are the edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
*/

7. Write a java program to implement Floyd's algorithm for the all pairs shortest path problem.

Save as:

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
  final static int INF = 99999, V = 4;

void floydWarshall (int graph[][])
  {
    int dist[][] = new int[V][V];
    int i, j, k;
    for (i = 0; i < V; i++)
      for (j = 0; j < V; j++)
    dist[i][j] = graph[i][j];
    for (k = 0; k < V; k++)
      {
  for (i = 0; i < V; i++)
    {
      for (j = 0; j < V; j++)
        {
    if (dist[i][k] + dist[k][j] < dist[i][j])
      dist[i][j] = dist[i][k] + dist[k][j];
        }
    }
      }
    printSolution (dist);
  }

void printSolution (int dist[][])
  {
    System.out.println ("Following matrix shows the shortest " +
      "distances between every pair of vertices");
    for (int i = 0; i < V; ++i)
      {
  for (int j = 0; j < V; ++j)
    {
      if (dist[i][j] == INF)
        System.out.print ("INF ");
      else
        System.out.print (dist[i][j] + "   ");
    }
  System.out.println ();
      }
  }
  public static void main (String[]args)
  {
    int graph[][] = { {0, 5, INF, 10},
    {INF, 0, 3, INF},
    {INF, INF, 0, 1},
    {INF, INF, INF, 0}
    };
    Main a = new Main ();
    a.floydWarshall (graph);
  }
}

/*output
Following matrix shows the shortest distances between every pair of vertices
0   5   8   9   
INF 0   3   4   
INF INF 0   1   
INF INF INF 0

8. Write a java program to implement Dynamic Programming algorithm for the 0/1 Knapsack problem.

Save as:

9. Write a java program to implement Dynamic Programming algorithm for the Optimal Binary Search Tree Problem.

Save as:

public class Main
{
  static int optimalSearchTree (int keys[], int freq[], int n)
  {
    int cost[][] = new int[n + 1][n + 1];
    for (int i = 0; i < n; i++)
        cost[i][i] = freq[i];
    for (int L = 2; L <= n; L++)
      {
  for (int i = 0; i <= n - L + 1; i++)
    {
      int j = i + L - 1;
        cost[i][j] = Integer.MAX_VALUE;
      for (int r = i; r <= j; r++)
        {
    int c = ((r > i) ? cost[i][r - 1] : 0)
      + ((r < j) ? cost[r + 1][j] : 0) + sum (freq, i, j);
    if (c < cost[i][j])
        cost[i][j] = c;
        }
    }
      }
    return cost[0][n - 1];
  }
  static int sum (int freq[], int i, int j)
  {
    int s = 0;
    for (int k = i; k <= j; k++)
      {
  if (k >= freq.length)
    continue;
  s += freq[k];
      }
    return s;
  }

public static void main (String[]args)
  {

int keys[] = { 10, 12, 20 };
    int freq[] = { 34, 8, 50 };
    int n = keys.length;
    System.out.println ("Cost of Optimal BST is "
      + optimalSearchTree (keys, freq, n));
  }

}
/*output
Cost of Optimal BST is 142
*/

Daa lab all programs

1. Write a java program to implement the backtracking algorithm for the sum of subsets problem.

Save as: Main.java

2.Write a java program to implement the backtracking algorithm for the Hamiltonian Circuits problem.

Save as: Main.java

3. Write a java program to implement greedy algorithm for job sequencing with deadlines.

Save as:

4.Write a java program to implement Dijkstra’s algorithm for the Single source shortest path problem.

Save as:

5. Write a java program that implements Prim's algorithm to generate minimum cost spanning tree.

Save as:

6. Write a java program that implements Kruskal's algorithm to generate minimum cost spanning tree

Save as:

7. Write a java program to implement Floyd's algorithm for the all pairs shortest path problem.

Save as:

8. Write a java program to implement Dynamic Programming algorithm for the 0/1 Knapsack problem.

Save as:

9. Write a java program to implement Dynamic Programming algorithm for the Optimal Binary Search Tree Problem.

Save as:

0 Comments

Menu Footer Widget

Daa lab all programs

1. Write a java program to implement the backtracking algorithm for the sum of subsets problem.

Save as: Main.java

2.Write a java program to implement the backtracking algorithm for the Hamiltonian Circuits problem.

Save as: Main.java

3. Write a java program to implement greedy algorithm for job sequencing with deadlines.

Save as:

4.Write a java program to implement Dijkstra’s algorithm for the Single source shortest path problem.

Save as:

5. Write a java program that implements Prim's algorithm to generate minimum cost spanning tree.

Save as:

6. Write a java program that implements Kruskal's algorithm to generate minimum cost spanning tree

Save as:

7. Write a java program to implement Floyd's algorithm for the all pairs shortest path problem.

Save as:

8. Write a java program to implement Dynamic Programming algorithm for the 0/1 Knapsack problem.

Save as:

9. Write a java program to implement Dynamic Programming algorithm for the Optimal Binary Search Tree Problem.

Save as:

You may like these posts

0 Comments

Follow Us

Menu Footer Widget