3.a) Write a program to find minimum cost spanning tree using Prims Algorithm.
AIM:
Write a java program that implements Prim’s algorithm to generate minimum cost spanning tree.
DESCRIPTION:
Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted
undirected graph. This means it finds a subset of the edges that forms a tree that includes every
vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by
building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the
cheapest possible connection from the tree to another vertex.
PROGRAM:
import java.util.InputMismatchException;
import java.util.Scanner;
public class Prims {
private boolean unsettled[];
private boolean settled[];
private int numberofvertices;
private int adjacencyMatrix[][];
private int key[];
public static final int INFINITE = 999;
private int parent[];
public Prims(int numberofvertices) {
this.numberofvertices = numberofvertices;
unsettled = new boolean[numberofvertices + 1];
settled = new boolean[numberofvertices + 1];
adjacencyMatrix = new int[numberofvertices + 1][numberofvertices + 1];
key = new int[numberofvertices + 1];
parent = new int[numberofvertices + 1];
}
public int getUnsettledCount(boolean unsettled[]) {
int count = 0;
for (int index = 0; index < unsettled.length; index++) {
if (unsettled[index]) {
count++;
}
}
return count;
}
public void primsAlgorithm(int adjacencyMatrix[][]) {
int evaluationVertex;
for (int source = 1; source <= numberofvertices; source++) {
for (int destination = 1; destination <= numberofvertices; destination++) {
this.adjacencyMatrix[source][destination] = adjacencyMatrix[source][destination];
}
}
for (int index = 1; index <= numberofvertices; index++) {
key[index] = INFINITE;
}
key[1] = 0;
unsettled[1] = true;
parent[1] = 1;
while (getUnsettledCount(unsettled) != 0) {
evaluationVertex = getMimumKeyVertexFromUnsettled(unsettled);
unsettled[evaluationVertex] = false;
settled[evaluationVertex] = true;
evaluateNeighbours(evaluationVertex);
}
}
private int getMimumKeyVertexFromUnsettled(boolean[] unsettled2) {
int min = Integer.MAX_VALUE;
int node = 0;
for (int vertex = 1; vertex <= numberofvertices; vertex++) {
if (unsettled[vertex] == true && key[vertex] < min) {
node = vertex;
min = key[vertex];
}
}
return node;
}
public void evaluateNeighbours(int evaluationVertex) {
for (int destinationvertex = 1; destinationvertex <= numberofvertices; destinationvertex++)
{
if (settled[destinationvertex] == false) {
if (adjacencyMatrix[evaluationVertex][destinationvertex] != INFINITE) {
if (adjacencyMatrix[evaluationVertex][destinationvertex] < key[destinationvertex])
{
key[destinationvertex] = adjacencyMatrix[evaluationVertex][destinationvertex];
parent[destinationvertex] = evaluationVertex;
}
unsettled[destinationvertex] = true;
}
}
}
}
public void printMST() {
System.out.println("SOURCE : DESTINATION = WEIGHT");
for (int vertex = 2; vertex <= numberofvertices; vertex++) {
System.out.println(parent[vertex] + "\t:\t" + vertex + "\t=\t" +
adjacencyMatrix[parent[vertex]][vertex]);
}
}
public static void main(String... arg) {
int adjacency_matrix[][];
int number_of_vertices;
Scanner scan = new Scanner(System.in);
try {
System.out.println("Enter the number of vertices");
number_of_vertices = scan.nextInt();
adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
System.out.println("Enter the Weighted Matrix for the graph");
for (int i = 1; i <= number_of_vertices; i++) {
for (int j = 1; j <= number_of_vertices; j++) {
adjacency_matrix[i][j] = scan.nextInt();
if (i == j) {
adjacency_matrix[i][j] = 0;
continue;
}
if (adjacency_matrix[i][j] == 0) {
adjacency_matrix[i][j] = INFINITE;
}
}
}
Prims prims = new Prims(number_of_vertices);
prims.primsAlgorithm(adjacency_matrix);
prims.printMST();
} catch (InputMismatchException inputMismatch) {
System.out.println("Wrong Input Format");
}
scan.close();
}
}
OUTPUT:
$javac Prims.java
$java Prims
Enter the number of vertices
5
Enter the Weighted Matrix for the graph
04005
40361
03062
06607
51270
SOURCE : DESTINATION = WEIGHT
1:2=4
5:3=2
2:4=6
2:5=1
b) Write a program to find minimum cost spanning tree using Kruskal’s Algorithm.
AIM:
Write a java program that implements Kruskal’s algorithm to generate minimum cost
spanning tree.
DESCRIPTION:
Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least
possible weight that connects any two trees in the forest.[1] It is a greedy algorithm in graph
theory as it finds a minimum spanning tree for a connected weighted graph adding increasing
cost arcs at each step.[1] This means it finds a subset of the edges that forms a tree that includes
every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not
connected, then it finds a minimum spanning forest (a minimum spanning tree for each
connected component).
PROGRAM:
import java.util.*;
import java.lang.*;
import java.io.*;
class Graph {
// A class to represent a graph edge
class Edge implements Comparable<Edge> {
int src, dest, weight;
// Comparator function used for sorting edges based on their weight
public int compareTo(Edge compareEdge) {
return this.weight - compareEdge.weight;
}
}
// A class to represent a subset for union-find
class subset {
int parent, rank;
}
int V, E; // V-> no. of vertices & E->no.of edges
Edge edge[]; // collection of all edges
// Creates a graph with V vertices and E edges
Graph(int v, int e) {
V = v;
E = e;
edge = new Edge[E];
for (int i = 0; i < e; ++i)
edge[i] = new Edge();
}
// A utility function to find set of an element i (uses path compression technique)
int find(subset subsets[], int i) {
// find root and make root as parent of i (path compression)
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// A function that does union of two sets of x and y (uses union by rank)
void Union(subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
// Attach smaller rank tree under root of high rank tree (Union by Rank)
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++;
}
}
// The main function to construct MST using Kruskal's algorithm
void KruskalMST() {
Edge result[] = new Edge[V]; // This will store the resultant MST
int e = 0; // An index variable, used for result[]
int i = 0; // An index variable, used for sorted edges
for (i = 0; i < V; ++i)
result[i] = new Edge();
// Step 1: Sort all the edges in non-decreasing order of their weight
Arrays.sort(edge);
// Allocate memory for creating V subsets
subset subsets[] = new subset[V];
for (i = 0; i < V; ++i)
subsets[i] = new subset();
// Create V subsets with single elements
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
i = 0; // Index used to pick next edge
// Number of edges to be taken is equal to V-1
while (e < V - 1) {
// Step 2: Pick the smallest edge and increment the index for next iteration
Edge next_edge = new Edge();
next_edge = edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
// If including this edge doesn't cause cycle, include it in result and increment
// the index of result for next edge
if (x != y) {
result[e++] = next_edge;
Union(subsets, x, y);
}
// Else discard the next_edge
}
// print the contents of result[] to display the built MST
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);
}
// Driver Program
public static void main(String[] args) {
int V = 4; // Number of vertices in graph
int E = 5; // Number of edges in graph
Graph graph = new Graph(V, E);
// add edge 0-1
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = 10;
// add edge 0-2
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 6;
// add edge 0-3
graph.edge[2].src = 0;
graph.edge[2].dest = 3;
graph.edge[2].weight = 5;
// add edge 1-3
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 15;
// add edge 2-3
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
4. Write a program to implement 0/1 Knapsack problem using Dynamic Programming
method.
AIM:
Write a java program to implement Dynamic Programming algorithm for the 0/1 Knapsack
problem.
DESCRIPTION:
Given weights and values of n items, put these items in a knapsack of capacity W to get the
maximum total value in the knapsack. In other words, given two integer arrays Val[0..n-1] and
wt[0..n-1] which represent values and weights associated with n items respectively. Also given
an integer W which represents knapsack capacity, find out the maximum value subset of val[]
such that sum of the weights of this subset is smaller than or equal to W. You cannot break an
item, either pick the complete item, or don’t pick it (0-1 property).
PROGRAM:
import java.util.Scanner;
public class Knapsack_DP {
static int max(int a, int b) {
return (a > b) ? a : b;
}
static int knapSack(int W, int wt[], int val[], int n) {
int i, w;
int[][] K = new int[n + 1][W + 1];
// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number of items: ");
int n = sc.nextInt();
System.out.println("Enter the items weights: ");
int[] wt = new int[n];
for (int i = 0; i < n; i++)
wt[i] = sc.nextInt();
System.out.println("Enter the items values: ");
int[] val = new int[n];
for (int i = 0; i < n; i++)
val[i] = sc.nextInt();
System.out.println("Enter the maximum capacity: ");
int W = sc.nextInt();
System.out.println("The maximum value that can be put in a knapsack of capacity W is: " +
knapSack(W, wt, val, n));
sc.close();
}
}
OUTPUT:
$ javac Knapsack_DP.java
$ java Knapsack_DP
Enter the number of items:
5
Enter the items weights:
01 56 42 78 12
Enter the items values:
50 30 20 10 50
Enter the maximum capacity:
150
The maximum value that can be put in a knapsack of capacity W is: 15
