Ex.

No:1a IMPLEMENTATION OF MERGE SORT ANALYSIS

Date:

AIM:
To write a java program to implement merge sort analysis.
ALGORITHM:
1. If it is only one element in the list it is already sorted return.
2. Divide the list recursively into two halves until it can no more be divided.
3. Merge the smaller lists into new list in sorted order.
4. Stop the Program.

1
PROGRAM:
import java.util.Scanner;
public class MergeSort
{
public static void sort(int[] a, int low, int high)
{
int N = high - low;
if (N <= 1)
return;
int mid = low + N/2;
sort(a, low, mid);
sort(a, mid, high);
int[] temp = new int[N];
int i = low, j = mid;
for (int k = 0; k < N; k++)
{
if (i == mid)
temp[k] = a[j++];
else if (j == high)
temp[k] = a[i++];
else if (a[j]<a[i])
temp[k] = a[j++];
else
temp[k] = a[i++];
}
for (int k = 0; k < N; k++)
a[low + k] = temp[k];
}
public static void main(String[] args)
{
Scanner scan = new Scanner( System.in );

2
 System.out.println("Merge Sort Test\n");
int n, i;
System.out.println("Enter number of integer elements");
n = scan.nextInt();
int arr[] = new int[ n ];
System.out.println("\nEnter "+ n +" integer elements");
for (i = 0; i < n; i++)
arr[i] = scan.nextInt();
sort(arr, 0, n);
System.out.println("\nElements after sorting ");
for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}

RESULT:
Thus the java program to implement Merge Sort was written, executed and verified
successfully.

3
Ex.No:1 b IMPLEMENTATION OF QUICK SORT ANALYSIS
Date:

AIM:
To write a java program to implement quick sort analysis.
ALGORITHM:
1. Choose an element, called pivot, from the list. Generally pivot can be the middle index
element
2. Reorder the list so that all elements with values less than the pivot come before the pivot
3. All elements with values greater than the pivot come after it (equal values can go either
way). After this partitioning, the pivot is in its final position. This is called the partition operation.
4. Recursively apply the above steps to the sub-list of elements with smaller values and
separately the sub-list of elements with greater values.
5. Stop the Program.

4
PROGRAM:
import java.util.Scanner;
/** Class QuickSort **/
public class QuickSort
{
/** Quick Sort function **/
public static void sort(int[] arr)
{
quickSort(arr, 0, arr.length - 1);
}
/** Quick sort function **/
public static void quickSort(int arr[], int low, int high)
{
int i = low, j = high;
int temp;
int pivot = arr[(low + high) / 2];
/** partition **/
while (i <= j)
{
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j)
{
/** swap **/
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

5
 i++;
j--;
} }
/** recursively sort lower half **/
if (low < j)
quickSort(arr, low, j);
/** recursively sort upper half **/
if (i < high)
quickSort(arr, i, high);
}
/** Main method **/
public static void main(String[] args)
{
Scanner scan = new Scanner( System.in );
System.out.println("Quick Sort Test\n");
int n, i;
/** Accept number of elements **/
System.out.println("Enter number of integer elements");
n = scan.nextInt();
/** Create array of n elements **/
int arr[] = new int[ n ];
/** Accept elements **/
System.out.println("\nEnter "+ n +" integer elements");
for (i = 0; i < n; i++)
arr[i] = scan.nextInt();
/** Call method sort **/
sort(arr);
/** Print sorted Array **/
System.out.println("\nElements after sorting ");

6
 for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();
} }

RESULT:
Thus the java program to implement quick sort was written, executed and verified
successfully.

7
 Ex.No:2 IMPLEMENTATION OF BINARY SEARCH TREE
Date:

AIM:
To write a java program for implementing Binary Search Tree.
ALGORITHM:
1. Read the search element from the user
2. Compare, the search element with the value of root node in the tree.
3. If both are matching, then display "Given node found" and terminate the function
4. If both are not matching, then check whether search element is smaller or larger than that
node value.
5. If search element is smaller, then continue the search process in left subtree.
6. If search element is larger, then continue the search process in right subtree.
7. Repeat the same until we found exact element or we completed with a leaf node
8. If we reach to the node with search value, then display "Element is found" and terminate
the function.
9. If we reach to a leaf node and it is also not matching, then display "Element not found"
and terminate the function.

8
PROGRAM:
public class BinarySearchTree
{
public static Node root;
public BinarySearchTree()
{
this.root = null;
}
public boolean find(int id)
{
Node current = root;
while(current!=null)
{
if(current.data==id)
{
return true;
}
else if(current.data>id)
{
current = current.left;
}
Else
{
current = current.right;
}
}
return false;
}
public boolean delete(int id)
{
Node parent = root;

9
Node current = root;
boolean isLeftChild = false;
while(current.data!=id)
{
parent = current;
if(current.data>id)
{
isLeftChild = true;
current = current.left;
}
Else
{
isLeftChild = false;
current = current.right;
}
if(current ==null)
{
return false;
}
}
//if i am here that means we have found the node
//Case 1: if node to be deleted has no children
if(current.left==null && current.right==null)
{
if(current==root)
{
root = null;
}
if(isLeftChild ==true)
{
parent.left = null;

10
}
Else
{
parent.right = null;
}
}
//Case 2 : if node to be deleted has only one child
else if(current.right==null)
{
if(current==root)
{
root = current.left;
}
else if(isLeftChild)
{
parent.left = current.left;
}
Else
{
parent.right = current.left;
}
}
else if(current.left==null)
{
if(current==root)
{
root = current.right;
}
else if(isLeftChild)
{
parent.left = current.right;

11
}
Else
{
parent.right = current.right;
}
}
else if(current.left!=null && current.right!=null)
{
//now we have found the minimum element in the right sub tree
Node successor = getSuccessor(current);
if(current==root)
{
root = successor;
}
else if(isLeftChild)
{
parent.left = successor;
}
Else
{
parent.right = successor;
}
successor.left = current.left;
}
return true;
}
public Node getSuccessor(Node deleleNode)
{
Node successsor =null;
Node successsorParent =null;
Node current = deleleNode.right;

12
while(current!=null)
{
successsorParent = successsor;
successsor = current;
current = current.left;
}
//check if successor has the right child, it cannot have left child for sure
// if it does have the right child, add it to the left of successorParent.
// successsorParent
if(successsor!=deleleNode.right)
{
successsorParent.left = successsor.right;
successsor.right = deleleNode.right;
}
return successsor;
}
public void insert(int id)
{
Node newNode = new Node(id);
if(root==null)
{
root = newNode;
return;
}
Node current = root;
Node parent = null;
while(true)
{
parent = current;
if(id<current.data)
{

13
current = current.left;
if(current==null)
{
parent.left = newNode;
return;
}
}
Else
{
current = current.right;
if(current==null)
{
parent.right = newNode;
return;
}
}
}
}
public void display(Node root)
{
if(root!=null)
{
display(root.left);
System.out.print(" " + root.data);
display(root.right);
}
}
public static void main(String arg[])
{
BinarySearchTree b = new BinarySearchTree();
b.insert(3);

14
b.insert(8);
b.insert(1);
b.insert(4);
b.insert(6);
b.insert(2);
b.insert(10);
b.insert(9);
b.insert(20);
b.insert(25);
b.insert(15);
b.insert(16);
System.out.println("Original Tree : ");
b.display(b.root);
System.out.println("");
System.out.println("Check whether Node with value 4 exists : " + b.find(4));
System.out.println("Delete Node with no children (2) : " + b.delete(2));
b.display(root);
System.out.println("\n Delete Node with one child (4) : " + b.delete(4));
b.display(root);
System.out.println("\n Delete Node with Two children (10) : " + b.delete(10));
b.display(root);
}
}
class Node
{
int data;
Node left;
Node right;
public Node(int data)
{
this.data = data;

15
 left = null;
right = null;
}
}

RESULT:
Thus the implementation of Binary Search tree was written, executed and verified
successfully.

16
Ex.No:3
Date: RED-BLACK TREE IMPLEMENTATION

AIM:
To write a java program to implement Red-Black Tree.
ALGORITHM:
1. Check whether tree is Empty.
2. If tree is Empty then insert the newNode as Root node with color Black and exit from
the operation.
3. If tree is not Empty then insert the newNode as a leaf node with Red color.
4. If the parent of newNode is Black then exit from the operation.
5. If the parent of newNode is Red then check the color of parent node's sibling of
newNode.
6. If it is Black or NULL node then make a suitable Rotation and Recolor it.
7. If it is Red colored node then perform Recolor and Recheck it. Repeat the same until
tree becomes Red Black Tree.

17
PROGRAM:
import java.util.Scanner;
class RedBlackNode
{
RedBlackNode left, right;
int element;
int color;
public RedBlackNode(int theElement)
{
this( theElement, null, null );
}
public RedBlackNode(int theElement, RedBlackNode lt, RedBlackNode rt)
{
left = lt;
right = rt;
element = theElement;
color = 1;
}
}
class RBTree
{
private RedBlackNode current;
private RedBlackNode parent;
private RedBlackNode grand;
private RedBlackNode great;
private RedBlackNode header;
private static RedBlackNode nullNode;
static
{
nullNode = new RedBlackNode(0);
nullNode.left = nullNode;

18
nullNode.right = nullNode;
}
static final int BLACK = 1;
static final int RED = 0;
public RBTree(int negInf)
{
header = new RedBlackNode(negInf);
header.left = nullNode;
header.right = nullNode;
}
public boolean isEmpty()
{
return header.right == nullNode;
}
public void makeEmpty()
{
header.right = nullNode;
}
public void insert(int item )
{
current = parent = grand = header;
nullNode.element = item;
while (current.element != item)
{
great = grand;
grand = parent;
parent = current;
current = item < current.element ? current.left : current.right;
if (current.left.color == RED && current.right.color == RED)
handleReorient( item );
}

19
if (current != nullNode)
return;
current = new RedBlackNode(item, nullNode, nullNode);
if (item < parent.element)
parent.left = current;
else
parent.right = current;
handleReorient( item );
}
private void handleReorient(int item)
{
current.color = RED;
current.left.color = BLACK;
current.right.color = BLACK;
if (parent.color == RED)
{
grand.color = RED;
if (item < grand.element != item < parent.element)
parent = rotate( item, grand );
current = rotate(item, great );
current.color = BLACK;
}
header.right.color = BLACK;
}
private RedBlackNode rotate(int item, RedBlackNode parent)
{
if(item < parent.element)
return parent.left = item < parent.left.element ? rotateWithLeftChild(parent.left) :
rotateWithRightChild(parent.left) ;
else

20
return parent.right = item < parent.right.element ? rotateWithLeftChild(parent.right) :
rotateWithRightChild(parent.right);
}
private RedBlackNode rotateWithLeftChild(RedBlackNode k2)
{
RedBlackNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
private RedBlackNode rotateWithRightChild(RedBlackNode k1)
{
RedBlackNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
public int countNodes()
{
return countNodes(header.right);
}
private int countNodes(RedBlackNode r)
{
if (r == nullNode)
return 0;
else
{
int l = 1;
l += countNodes(r.left);
l += countNodes(r.right);
return l;

21
}
}
public boolean search(int val)
{
return search(header.right, val);
}
private boolean search(RedBlackNode r, int val)
{
boolean found = false;
while ((r != nullNode) && !found)
{
int rval = r.element;
if (val < rval)
r = r.left;
else if (val > rval)
r = r.right;
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}
public void inorder()
{
inorder(header.right);
}
private void inorder(RedBlackNode r)
{

22
if (r != nullNode)
{
inorder(r.left);
char c = 'B';
if (r.color == 0)
c = 'R';
System.out.print(r.element +""+c+" ");
inorder(r.right);
}
}
public void preorder()
{
preorder(header.right);
}
private void preorder(RedBlackNode r)
{
if (r != nullNode)
{
char c = 'B';
if (r.color == 0)
c = 'R';
System.out.print(r.element +""+c+" ");
preorder(r.left);
preorder(r.right);
}
}
public void postorder()
{
postorder(header.right);
}
private void postorder(RedBlackNode r)

23
{
if (r != nullNode)
{
postorder(r.left);
postorder(r.right);
char c = 'B';
if (r.color == 0)
c = 'R';
System.out.print(r.element +""+c+" ");
}
}
}
public class RedBlackTree
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of RedBlack Tree */
RBTree rbt = new RBTree(Integer.MIN_VALUE);
System.out.println("Red Black Tree Test\n");
char ch;
do
{
System.out.println("\nRed Black Tree Operations\n");
System.out.println("1. insert ");
System.out.println("2. search");
System.out.println("3. count nodes");
System.out.println("4. check empty");
System.out.println("5. clear tree");
int choice = scan.nextInt();
switch (choice)

24
{
case 1 :
System.out.println("Enter integer element to insert");
rbt.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to search");
System.out.println("Search result : "+ rbt.search( scan.nextInt() ));
break;
case 3 :
System.out.println("Nodes = "+ rbt.countNodes());
break;
case 4 :
System.out.println("Empty status = "+ rbt.isEmpty());
break;
case 5 :
System.out.println("\nTree Cleared");
rbt.makeEmpty();
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
System.out.print("\nPost order : ");
rbt.postorder();
System.out.print("\nPre order : ");
rbt.preorder();
System.out.print("\nIn order : ");
rbt.inorder();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);

25
}
while (ch == 'Y'|| ch == 'y');
}
}

RESULT:
Thus the java program to implement Red Black Tree was executed and verified
successfully.

26
 Ex.No:4 HEAP IMPLEMENTATION
Date:

AIM:
To write a java program for heap implementation.
ALGORITHM:
1. Call the buildMaxHeap() function on the list. Also referred to as heapify(), this builds
a heap from a list in O(n) operations.
2. Swap the first element of the list with the final element. Decrease the considered
range of the list by one.
3. Call the siftDown() function on the list to sift the new first element to its appropriate
index in the heap.
4. Go to step (2) unless the considered range of the list is one element.
5. The buildMaxHeap() operation is run once, and is O(n) in performance. The
siftDown() function is O(log n), and is called n times. Therefore, the performance of
this algorithm is O(n + n log n) = O(n log n).

27
PROGRAM:

import java.io.*;
class Node
{
private int iData;
public Node(int key)
{ iData = key; }
public int getKey()
{ return iData; }
public void setKey(int id)
{ iData = id; }
}
class Heap
{
private Node[] heapArray;
private int maxSize;
private int currentSize;
public Heap(int mx)
{
maxSize = mx;
currentSize = 0;
heapArray = new Node[maxSize];
}
public boolean isEmpty()
{ return currentSize==0; }
public boolean insert(int key)
{
if(currentSize==maxSize)
return false;
Node newNode = new Node(key);
heapArray[currentSize] = newNode;
28
trickleUp(currentSize++);
return true;
}
public void trickleUp(int index)
{
int parent = (index-1) / 2;
Node bottom = heapArray[index];
while( index > 0 &&
heapArray[parent].getKey() < bottom.getKey() )
{
heapArray[index] = heapArray[parent];
index = parent;
parent = (parent-1) / 2;
}
heapArray[index] = bottom;
}
public Node remove()
{
Node root = heapArray[0];
heapArray[0] = heapArray[--currentSize];
trickleDown(0);
return root;
}
public void trickleDown(int index)
{
int largerChild;
Node top = heapArray[index];
while(index < currentSize/2)
{
int leftChild = 2*index+1;
int rightChild = leftChild+1;

29
 if(rightChild < currentSize && // (rightChild exists?)
heapArray[leftChild].getKey() <
heapArray[rightChild].getKey())
largerChild = rightChild;
else
largerChild = leftChild;
if( top.getKey() >= heapArray[largerChild].getKey() )
break;
heapArray[index] = heapArray[largerChild];
index = largerChild;
}
heapArray[index] = top;
}
public boolean change(int index, int newValue)
{
if(index<0 || index>=currentSize)
return false;
int oldValue = heapArray[index].getKey();
heapArray[index].setKey(newValue);
if(oldValue < newValue)
trickleUp(index);
else
trickleDown(index);
return true;
}
public void displayHeap()
{
System.out.print("heapArray: ");
for(int m=0; m<currentSize; m++)
if(heapArray[m] != null)
System.out.print( heapArray[m].getKey() + " ");

30
 else
System.out.print( "-- ");
System.out.println();
int nBlanks = 32;
int itemsPerRow = 1;
int column = 0;
int j = 0;
String dots = "...............................";
System.out.println(dots+dots);
while(currentSize > 0)
{
if(column == 0)
for(int k=0; k<nBlanks; k++)
System.out.print(' ');
System.out.print(heapArray[j].getKey());
if(++j == currentSize)
break;

if(++column==itemsPerRow)
{
nBlanks /= 2;
itemsPerRow *= 2;
column = 0;
System.out.println();
}
else
for(int k=0; k<nBlanks*2-2; k++)
System.out.print(' ');
}
System.out.println("\n"+dots+dots);
}

31
 }
class HeapApp
{
public static void main(String[] args) throws IOException
{
int value, value2;
Heap theHeap = new Heap(31);
boolean success;
theHeap.insert(70);
theHeap.insert(40);
theHeap.insert(50);
theHeap.insert(20);
theHeap.insert(60);
theHeap.insert(100);
theHeap.insert(80);
theHeap.insert(30);
theHeap.insert(10);
theHeap.insert(90);
while(true)
{
System.out.print("Enter first letter of ");
System.out.print("show, insert, remove, change: ");
int choice = getChar();
switch(choice)
{
case 's':
theHeap.displayHeap();
break;
case 'i':
System.out.print("Enter value to insert: ");
value = getInt();

32
 success = theHeap.insert(value);
if( !success )
System.out.println("Can't insert; heap full");
break;
case 'r':
if( !theHeap.isEmpty() )
theHeap.remove();
else
System.out.println("Can't remove; heap empty");
break;
case 'c':
System.out.print("Enter current index of item: ");
value = getInt();
System.out.print("Enter new key: ");
value2 = getInt();
success = theHeap.change(value, value2);
if( !success )
System.out.println("Invalid index");
break;
default:
System.out.println("Invalid entry\n");
}
}
}
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}

33
 public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
}

RESULT:
Thus the heap implementation was written, executed and verified successfully.

34
 Ex.No:5 FIBONACCI HEAP IMPLEMENTATION
Date:

AIM:
To write a java program for Fibonacci heap implement.
ALGORITHM:
1. Call the buildMinHeap() function on the list.
2. insert(x) inserts a node x into the heap.
3. minimum() returns the node in the heap with minimum key.
4. extractMin() deletes the node with minimum key from the heap.
5. union(H) merge heap H and create a new one.
6. decreaseKey(x,k) assigns to node x within the heap the new key value k, which is
assumed to be no greater than its current key value.
7. delete(x) deletes node x from the heap.

35
PROGRAM:
importjava.util.*;
classFibonacciHeapNode
{
FibonacciHeapNode child, left, right, parent;
int element;
publicFibonacciHeapNode(int element)
{
this.right = this;
this.left = this;
this.element = element;
}
}
classFibonacciHeap
{
privateFibonacciHeapNode root;
privateint count;
publicFibonacciHeap()
{
root = null;
count = 0;
}
publicbooleanisEmpty()
{
return root == null;
}
public void clear()
{
root = null;
count = 0;
}

36
public void insert(int element)
{
FibonacciHeapNode node = new FibonacciHeapNode(element);
node.element = element;
if (root != null)
{
node.left = root;
node.right = root.right;
root.right = node;
node.right.left = node;
if (element <root.element)
root = node;
}
else
root = node;
count++;
}
public void display()
{
System.out.print("\nHeap = ");
FibonacciHeapNodeptr = root;
if (ptr == null)
{
System.out.print("Empty\n");
return;
}
do
{
System.out.print(ptr.element +" ");
ptr = ptr.right;
} while (ptr != root &&ptr.right != null);

37
System.out.println();
}
}
public class FibonacciHeapTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("FibonacciHeap Test\n\n");
FibonacciHeapfh = new FibonacciHeap();
charch;
do
{
System.out.println("\nFibonacciHeap Operations\n");
System.out.println("1. insert element ");
System.out.println("2. check empty");
System.out.println("3. clear");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter element");
fh.insert(scan.nextInt() );
break;
case 2 :
System.out.println("Empty status = "+ fh.isEmpty());
break;
case 3 :
fh.clear();
break;
default :

38
 System.out.println("Wrong Entry \n ");
break;
}
fh.display();
System.out.println("\nDo you want to continue (Type y or n)\n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}

RESULT:
Thus the Fibonacci heap implementation was written, executed and verified successfully.

39
Ex.No:6a
Date: GRAPH TRAVERSALS (DEPTH FIRST SEARCH)

AIM:
To write a java program to implement graph traversal by using depth first search.
ALGORITHM:
1. Start at some node, and is now our current node.
2. State that our current node is „visited‟.
3. Now look at all nodes adjacent to our current node.
4. If we see an adjacent node that has not been „visited‟, add it to the stack.
5. Then pop of the top node on the stack and traverse to it.
6. And go back to step 1.

40
PROGRAM:
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;
public class DFS
{
private Stack<Integer> stack;

public DFS()
{
stack = new Stack<Integer>();
}

public void dfs(int adjacency_matrix[][], int source)

{
int number_of_nodes = adjacency_matrix[source].length - 1;

int visited[] = new int[number_of_nodes + 1];

int element = source;
int i = source;
System.out.print(element + "\t");
visited[source] = 1;
stack.push(source);
while (!stack.isEmpty())
{
element = stack.peek();
i = element;
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{

41
 stack.push(i);
visited[i] = 1;
element = i;
i = 1;
System.out.print(element + "\t");
continue;
}
i++;
}
stack.pop();
}
}
public static void main(String...arg)
{
int number_of_nodes, source;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
number_of_nodes = scanner.nextInt();
int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
System.out.println("Enter the adjacency matrix");
for (int i = 1; i <= number_of_nodes; i++)
for (int j = 1; j <= number_of_nodes; j++)
adjacency_matrix[i][j] = scanner.nextInt();
System.out.println("Enter the source for the graph");
source = scanner.nextInt();
System.out.println("The DFS Traversal for the graph is given by ");
DFS dfs = new DFS();
dfs.dfs(adjacency_matrix, source);

42
 }catch(InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}
scanner.close();
}
}

RESULT:
Thus the java program to implement depth first search was written and verified successfully.

43
Ex.No:6b
Date: GRAPH TRAVERSALS (BREADTH FIRST SEARCH)

AIM:

To write a program to implement graph traversals by using breadth first search.

ALGORITHM:

1. Define a Queue of size total number of vertices in the graph.

2. Select any vertex as starting point for traversal. Visit that vertex and insert it into the
Queue.
3. Visit all the adjacent vertices of the vertex which is at front of the Queue which is not
visited and insert them into the Queue.
4. When there is no new vertex to be visit from the vertex at front of the Queue then delete
that vertex from the Queue.
5. Repeat step 3 and 4 until queue becomes empty.

44
PROGRAM:
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class BFS
{
private Queue<Integer> queue;
public BFS()
{
queue = new LinkedList<Integer>();
}

public void bfs(int adjacency_matrix[][], int source)

{
int number_of_nodes = adjacency_matrix[source].length - 1;
int[] visited = new int[number_of_nodes + 1];
int i, element;
visited[source] = 1;
queue.add(source);
while (!queue.isEmpty())
{
element = queue.remove();
i = element;
System.out.print(i + "\t");
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
queue.add(i);

45
 visited[i] = 1;
}
i++;
}
}
}
public static void main(String... arg)
{
int number_no_nodes, source;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
number_no_nodes = scanner.nextInt();
int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];
System.out.println("Enter the adjacency matrix");
for (int i = 1; i <= number_no_nodes; i++)
for (int j = 1; j <= number_no_nodes; j++)
adjacency_matrix[i][j] = scanner.nextInt();
System.out.println("Enter the source for the graph");
source = scanner.nextInt();
System.out.println("The BFS traversal of the graph is ");
BFS bfs = new BFS();
bfs.bfs(adjacency_matrix, source);
}
catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input Format");

46
 }
scanner.close();
}
}

RESULT:
Thus the java program to implement graph traversal by using breadth first search was written,
executed and verified successfully.

47
 Ex.No:7a
Date: SPANNING TREE IMPLEMENTATION (KRUSKAL’S ALGORITHM)

AIM:
To write a java program to implement spanning tree implementation using kruskal‟s
algorithm.
ALGORITHM:
1. Create a graph F, where each vertex in the graph is a separate tree.
2. Create a set S containing all the edges in the graph.
3. While S is nonempty and F is not yet spanning.
3.1. Remove an edge with minimum weight from S.
`3.2. If the removed edge connects two different trees then add it to the forest F,
combining two trees into a single tree.

48
PROGRAM:
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class KruskalAlgorithm
{
private List<Edge> edges;
private int numberOfVertices;
public static final int MAX_VALUE = 999;
private int visited[];
private int spanning_tree[][];
public KruskalAlgorithm(int numberOfVertices)
{
this.numberOfVertices = numberOfVertices;
edges = new LinkedList<Edge>();
visited = new int[this.numberOfVertices + 1];
spanning_tree = new int[numberOfVertices + 1][numberOfVertices + 1];
}
public void kruskalAlgorithm(int adjacencyMatrix[][])
{
boolean finished = false;
for (int source = 1; source <= numberOfVertices; source++)
{
for (int destination = 1; destination <= numberOfVertices; destination++)
{
if (adjacencyMatrix[source][destination] != MAX_VALUE && source != destination)
{

49
Edge edge = new Edge();
edge.sourcevertex = source;
edge.destinationvertex = destination;
edge.weight = adjacencyMatrix[source][destination];
adjacencyMatrix[destination][source] = MAX_VALUE;
edges.add(edge);
}
}
}
Collections.sort(edges, new EdgeComparator());
CheckCycle checkCycle = new CheckCycle();
for (Edge edge : edges)
{
spanning_tree[edge.sourcevertex][edge.destinationvertex] = edge.weight;
spanning_tree[edge.destinationvertex][edge.sourcevertex] = edge.weight;
if (checkCycle.checkCycle(spanning_tree, edge.sourcevertex))
{
spanning_tree[edge.sourcevertex][edge.destinationvertex] = 0;
spanning_tree[edge.destinationvertex][edge.sourcevertex] = 0;
edge.weight = -1;
continue;
}
visited[edge.sourcevertex] = 1;
visited[edge.destinationvertex] = 1;
for (int i = 0; i < visited.length; i++)
{
if (visited[i] == 0)
{
finished = false;
break;

50
}
else
{
finished = true;
}
}
if (finished)
break;
}
System.out.println("The spanning tree is ");
for (int i = 1; i <= numberOfVertices; i++)
System.out.print("\t" + i);
System.out.println();
for (int source = 1; source <= numberOfVertices; source++)
{
System.out.print(source + "\t");
for (int destination = 1; destination <= numberOfVertices; destination++)
{
System.out.print(spanning_tree[source][destination] + "\t");
}
System.out.println();
}
}
public static void main(String... arg)
{
int adjacency_matrix[][];
int number_of_vertices;
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of vertices");
number_of_vertices = scan.nextInt();

51
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] = MAX_VALUE;
}
}
}
KruskalAlgorithm kruskalAlgorithm = new KruskalAlgorithm(number_of_vertices);
kruskalAlgorithm.kruskalAlgorithm(adjacency_matrix);
scan.close();
}
}
class Edge
{
int sourcevertex;
int destinationvertex;
int weight;
}
class EdgeComparator implements Comparator<Edge>

52
{
@Override
public int compare(Edge edge1, Edge edge2)
{
if (edge1.weight < edge2.weight)
return -1;
if (edge1.weight > edge2.weight)
return 1;
return 0;
}
}
class CheckCycle
{
private Stack<Integer> stack;
private int adjacencyMatrix[][];
public CheckCycle()
{
stack = new Stack<Integer>();
}
public boolean checkCycle(int adjacency_matrix[][], int source)
{
boolean cyclepresent = false;
int number_of_nodes = adjacency_matrix[source].length - 1;
adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1];
for (int sourcevertex = 1; sourcevertex <= number_of_nodes; sourcevertex++)
{
for (int destinationvertex = 1; destinationvertex <= number_of_nodes; destinationvertex++)
{
adjacencyMatrix[sourcevertex][destinationvertex] = adjacency_matrix[sourcevertex]
[destinationvertex];
}

53
}
int visited[] = new int[number_of_nodes + 1];
int element = source;
int i = source;
visited[source] = 1;
stack.push(source);
while (!stack.isEmpty())
{
element = stack.peek();
i = element;
while (i <= number_of_nodes)
{
if (adjacencyMatrix[element][i] >= 1 && visited[i] == 1)
{
if (stack.contains(i))
{
cyclepresent = true;
return cyclepresent;
}
}
if (adjacencyMatrix[element][i] >= 1 && visited[i] == 0)
{
stack.push(i);
visited[i] = 1;
adjacencyMatrix[element][i] = 0;// mark as labelled;
adjacencyMatrix[i][element] = 0;
element = i;
i = 1;
continue;
}

54
 i++;
}
stack.pop();
}
return cyclepresent;
}

RESULT:
Thus the Spanning tree implementation using kruskal‟s algorithm was written, executed and
verified successfully.

55
 Ex.No:7b
Date: SPANNING TREE IMPLEMENTATION (PRIM’S ALGORITHM)

AIM:
To write a java program to implement spanning tree implementation using Prim‟s algorithm.
ALGORITHM:
1. Create a set mstSet that keeps track of vertices already included in MST.
2. Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE.
3. Assign key value as 0 for the first vertex so that it is picked first.
4. While mstSet doesn‟t include all vertices
3.1. Pick a vertex u which is not there in mstSet and has minimum key value.
3.2. Include u to mstSet.
3.3. Update key value of all adjacent vertices of u. To update the key values, iterate
through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less
than the previous key value of v, update the key value as weight of u-v.

56
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++;
}
}

57
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;

58
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");

59
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;
}

60
}
}
Prims prims = new Prims(number_of_vertices);
prims.primsAlgorithm(adjacency_matrix);
prims.printMST();
} catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input Format");
}
scan.close();
}
}

RESULT:
Thus the Spanning tree implementation using prim‟s algorithm was written, executed and
verified successfully.

61
EX No:8a SHORTEST PATH ALGORITHMS (DIJKSTRA’S ALGORITHM)
DATE:

AIM:
To write a java program to implement Dijkstra‟s Algorithm.
ALGORITHM:
1. Initialization of all nodes with distance "infinite"; initialization of the starting node with 0

2. Marking of the distance of the starting node as permanent, all other distances as
temporarily.

3. Setting of starting node as active.

4. Calculation of the temporary distances of all neighbour nodes of the active node by
summing up its distance with the weights of the edges.

5. If such a calculated distance of a node is smaller as the current one, update the distance
and set the current node as antecessor. This step is also called update and is Dijkstra's
central idea.

6. Setting of the node with the minimal temporary distance as active. Mark its distance as
permanent.

7. Repeating of steps 4 to 7 until there aren't any nodes left with a permanent distance,
which neighbours still have temporary distances.

62
PROGRAM:
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;
public class DijkstraAlgorithmSet
{
private int distances[];
private Set<Integer> settled;
private Set<Integer> unsettled;
private int number_of_nodes;
private int adjacencyMatrix[][];
public DijkstraAlgorithmSet(int number_of_nodes)
{
this.number_of_nodes = number_of_nodes;
distances = new int[number_of_nodes + 1];
settled = new HashSet<Integer>();
unsettled = new HashSet<Integer>();
adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1];
}
public void dijkstra_algorithm(int adjacency_matrix[][], int source)
{
int evaluationNode;
for (int i = 1; i <= number_of_nodes; i++)
for (int j = 1; j <= number_of_nodes; j++)
adjacencyMatrix[i][j] = adjacency_matrix[i][j];
for (int i = 1; i <= number_of_nodes; i++)
{
distances[i] = Integer.MAX_VALUE;

63
}
unsettled.add(source);
distances[source] = 0;
while (!unsettled.isEmpty())
{
evaluationNode = getNodeWithMinimumDistanceFromUnsettled();
unsettled.remove(evaluationNode);
settled.add(evaluationNode);
evaluateNeighbours(evaluationNode);
}
}
private int getNodeWithMinimumDistanceFromUnsettled()
{
int min ;
int node = 0;
Iterator<Integer> iterator = unsettled.iterator();
node = iterator.next();
min = distances[node];
for (int i = 1; i <= distances.length; i++)
{
if (unsettled.contains(i))
{
if (distances[i] <= min)
{
min = distances[i];
node = i;
}
}
}
return node;
}

64
private void evaluateNeighbours(int evaluationNode)
{
int edgeDistance = -1;
int newDistance = -1;
for (int destinationNode = 1; destinationNode <= number_of_nodes; destinationNode++)
{
if (!settled.contains(destinationNode))
{
if (adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE)
{
edgeDistance = adjacencyMatrix[evaluationNode][destinationNode];
newDistance = distances[evaluationNode] + edgeDistance;
if (newDistance < distances[destinationNode])
{
distances[destinationNode] = newDistance;
}
unsettled.add(destinationNode);
}
}
}
}
public static void main(String... arg)
{
int adjacency_matrix[][];
int number_of_vertices;
int source = 0;
Scanner scan = new Scanner(System.in);
try
{
System.out.println("Enter the number of vertices");

65
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] = Integer.MAX_VALUE;
}
}
}
System.out.println("Enter the source ");
source = scan.nextInt();
DijkstraAlgorithmSet dijkstrasAlgorithm = new DijkstraAlgorithmSet(number_of_vertices);
dijkstrasAlgorithm.dijkstra_algorithm(adjacency_matrix, source);
System.out.println("The Shorted Path to all nodes are ");
for (int i = 1; i <= dijkstrasAlgorithm.distances.length - 1; i++)
{
System.out.println(source + " to " + i + " is "+ dijkstrasAlgorithm.distances[i]);
}
}
catch (InputMismatchException inputMismatch)

66
{
System.out.println("Wrong Input Format");
}
scan.close();
}
}

RESULT:
Thus the java program to implement Dijkstra‟s Algorithm was executed and verified
successfully.

67
 Ex.No:8b SHORTEST PATH ALGORITHMS (BELLMANN FORD ALGORITHM)
Date:

AIM:
To write a java program to implement Bellmann Ford algorithm.
ALGORITHM:
1. Start with the weighted graph
2. Choose the starting vertex and assign infinity path values to all other vertex
3. Visit each edge and relax the path distance if they are inaccurate
4. We need to do this V times because in the worst case the vertex path length might need to
be readjusted V times
5. Notice how the vertex at the top right corner had its path length adjusted
6. After all vertices have their path lengths we check if a negative cycle is present

68
PROGRAM:
import java.util.Scanner;
public class BellmanFord
{
private int distances[];
private int numberofvertices;
public static final int MAX_VALUE = 999;
public BellmanFord(int numberofvertices)
{
this.numberofvertices = numberofvertices;
distances = new int[numberofvertices + 1];
}
public void BellmanFordEvaluation(int source, int adjacencymatrix[][])
{
for (int node = 1; node <= numberofvertices; node++)
{
distances[node] = MAX_VALUE;
}
distances[source] = 0;
for (int node = 1; node <= numberofvertices - 1; node++)
{
for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++)
{
for (int destinationnode = 1; destinationnode <= numberofvertices; destinationnode++)
{
if (adjacencymatrix[sourcenode][destinationnode] != MAX_VALUE)
{
if (distances[destinationnode] > distances[sourcenode]
+ adjacencymatrix[sourcenode][destinationnode])
distances[destinationnode] = distances[sourcenode]
+ adjacencymatrix[sourcenode][destinationnode];

69
 }
}
}
}
for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++)
{
for (int destinationnode = 1; destinationnode <= numberofvertices;
destinationnode++)
{
if (adjacencymatrix[sourcenode][destinationnode] != MAX_VALUE)
{
if (distances[destinationnode] > distances[sourcenode]
+ adjacencymatrix[sourcenode][destinationnode])
System.out.println("The Graph contains negative egde cycle");
}
}
}

for (int vertex = 1; vertex <= numberofvertices; vertex++)

{
System.out.println("distance of source " + source + " to "
+ vertex + " is " + distances[vertex]);
}
}
public static void main(String... arg)
{
int numberofvertices = 0;
int source;
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the number of vertices");
numberofvertices = scanner.nextInt();

70
 int adjacencymatrix[][] = new int[numberofvertices + ][numberofvertices + 1];
System.out.println("Enter the adjacency matrix");
for (int sourcenode = 1; sourcenode <= numberofvertices; ourcenode++)
{
for (int destinationnode = 1; destinationnode <= umberofvertices;
destinationnode++)
{
adjacencymatrix[sourcenode][destinationnode] = canner.nextInt();
if (sourcenode == destinationnode)
{
adjacencymatrix[sourcenode][destinationnode] = 0;
continue;
}
if (adjacencymatrix[sourcenode][destinationnode] == 0)
{
adjacencymatrix[sourcenode][destinationnode] = MAX_VALUE;
}
}
}
System.out.println("Enter the source vertex");
source = scanner.nextInt();
BellmanFord bellmanford = new BellmanFord(numberofvertices);
bellmanford.BellmanFordEvaluation(source, adjacencymatrix);
scanner.close();
}

RESULT:
Thus the java program to implement Bellmann Ford Algorithm was written,
executed and verified successfully.

71
Ex.No:9 MATRIX CHAIN MULTIPLICATION
Date:

AIM:
To write a java program to implement Matrix Chain Multiplication.
ALGORITHM:
1. A chain of matrices to be multiplied is given as input.
2. For a sequence A1,A2,A3,A4 of 4 matrices, there are 5 different orderings=5
different parenthesization.
i) (A1,(A2(A3 A4)))
ii) (A1((A2 A3)A4))
iii) ((A1 A2)(A3 A4))
iv) ((A1(A2 A3))A4)
v) (((A1 A2)A3)A4)
3. Matrix_Multiply(A,B)
If coloumns[A]!=rows[B]
Then error “incomplete dimensions”
Else for i <- 1 to rows[A]
Do for j <- 1 to columns[B]
Do c[I,j] <- 0
For k<- 1 to columns[A]
Do c[i,j]=C[i,j]+A[i,k]+B[i,j]
Return c
4. A parenthesizing of the chain of the matrices is obtained as output.

72
PROGRAM:
public class MatrixChainMulti
{
void matrixchain(int a[])
{
int q;
int n=a.length;
int m[][]=new int[n][n];
int s[][]=new int[n][n];
for (int i=1;i<n;i++)
m[i][i]=0;
for (int l=2;l<n;l++) //l is the length
{
for(int i=1 ;i<n-l+1;i++)
{
int j=i+l-1;
m[i][j]=Integer.MAX_VALUE;
for (int k=i ;k<=j-1;k++)
{
q=m[i][k]+m[k+1][j]+a[i-1]*a[k]*a[j];
if(q<m[i][j])
{
m[i][j]=q;
s[i][j]=k;
}
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)

73
System.out.print(m[i][j]+" ");
System.out.println();
}
print_optimal(s,1,6);
}
void print_optimal(int s[][],int i,int j)
{
if (i==j)
System.out.print("A"+i);
else
{
System.out.print("(");
print_optimal(s,i,s[i][j]);
print_optimal(s,s[i][j]+1,j);
System.out.print(")");
}
}
public static void main(String args[])
{
int a[]={30, 35, 15, 5, 10, 20, 25};//A1:-30x35, A2:- 35x15, A3:- 15x5, A4:- 5x10 , A5:-
10x20, A6:- 20x25
MatrixChainMulti n=new MatrixChainMulti();
n.matrixchain(a);
}
}

RESULT:
Thus the java program to implement Matrix Chain Multiplication was written,
executed and verified successfully.

74
 Ex.No:10a
Date: ACTIVITY SELECTION

AIM:
To write a java program to implement Activity Selection.
ALGORITHM:
1. Sort the activities as per finishing time in ascending order
2. Select the first activity
3. Select the new activity if its starting time is greater than or equal to the previously selected
activity
4.REPEAT step 3 till all activities are checked

75
PROGRAM:
import java.util.*;
import java.lang.*;
import java.io.*;
class ActivitySelection
{
public static void printMaxActivities(int s[], int f[], int n)
{
int i, j;
System.out.print("Following activities are selected : n");
i = 0;
System.out.print(i+" ");
for (j = 1; j < n; j++)
{
if (s[j] >= f[i])
{
System.out.print(j+" ");
i = j;
}
}
}
public static void main(String[] args)
{
int s[] = {1, 3, 0, 5, 8, 5};
int f[] = {2, 4, 6, 7, 9, 9};
int n = s.length;
printMaxActivities(s, f, n);
}

76
RESULT:
Thus the java program to implement activity selection was executed and verified
successfully.

77
 Ex.No:10b
Date: HUFFMAN CODING

AIM:
To write a java program to implement Huffman Coding
ALGORITHM:
1. Sort the message ensemble by decreasing probability.
2. N is the cardinal of the message ensemble (number of different messages).
3. Compute the integer n_0 such as 2<=n_0<=D and (N-n_0)/(D-1) is integer.
4. Select the n_0 least probable messages, and assign them each a digit code.
5. Substitute the selected messages by a composite message summing their probability, and
re-order it.
6. While there remains more than one message, do steps thru 8.
7. Select D least probable messages, and assign them each a digit code.
8. Substitute the selected messages by a composite message summing their probability, and
re-order it.
9. The code of each message is given by the concatenation of the code digits of the aggregate
they've been put in.

78
PROGRAM:
import java.util.*;
abstract class HuffmanTree implements Comparable<HuffmanTree>
{
public final int frequency;
public HuffmanTree(int freq)
{
frequency = freq;
}
public int compareTo(HuffmanTree tree)
{
return frequency - tree.frequency;
}
}
class HuffmanLeaf extends HuffmanTree
{
public final char value;
public HuffmanLeaf(int freq, char val)
{
super(freq);
value = val;
}
}
class HuffmanNode extends HuffmanTree
{
public final HuffmanTree left, right;
public HuffmanNode(HuffmanTree l, HuffmanTree r)
{
super(l.frequency + r.frequency);
left = l;
right = r;

79
}
}
public class HuffmanCode
{
public static HuffmanTree buildTree(int[] charFreqs)
{
PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>();
for (int i = 0; i < charFreqs.length; i++)
if (charFreqs[i] > 0)
trees.offer(new HuffmanLeaf(charFreqs[i], (char)i));
assert trees.size() > 0;
while (trees.size() > 1)
{
HuffmanTree a = trees.poll();
HuffmanTree b = trees.poll();
trees.offer(new HuffmanNode(a, b));
}
return trees.poll();
}
public static void printCodes(HuffmanTree tree, StringBuffer prefix)
{
assert tree != null;
if (tree instanceof HuffmanLeaf)
{
HuffmanLeaf leaf = (HuffmanLeaf)tree;
System.out.println(leaf.value + "\t" + leaf.frequency + "\t" + prefix);
} else if (tree instanceof HuffmanNode)
{
HuffmanNode node = (HuffmanNode)tree;
prefix.append('0');
printCodes(node.left, prefix);

80
prefix.deleteCharAt(prefix.length()-1);
prefix.append('1');
printCodes(node.right, prefix);
prefix.deleteCharAt(prefix.length()-1);
}
}
public static void main(String[] args)
{
String test = "this is an example for huffman encoding";
int[] charFreqs = new int[256];
for (char c : test.toCharArray())
charFreqs[c]++;
HuffmanTree tree = buildTree(charFreqs);
System.out.println("SYMBOL\tWEIGHT\tHUFFMAN CODE");
printCodes(tree, new StringBuffer());
}
}

RESULT:
Thus the java program to implement Huffman Coding was written, executed and verified
successfully.

81