Ex.

No: 1(a) IMPLEMENTATION OF RECURSIVE FUNCTION

Date: FOR TREE TRAVERSAL

AIM:

To write the java program to implement the Tree Traversal using recursive function.

ALGORITHM:

Inorder(tree)
1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-subtree)
Preorder(tree)
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree)
Preorder(tree)
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree)

PROGRAM:
// Java program for different tree traversals
/* Class containing left and right child of current
node and key value*/
class Node {
int key;
Node left, right;

public Node(int item)

{
key = item;
left = right = null;
}
}

class BinaryTree {
// Root of Binary Tree
Node root;

BinaryTree() { root = null; }

/* Given a binary tree, print its nodes according to the

"bottom-up" postorder traversal. */
void printPostorder(Node node)
{
if (node == null)
return;

// first recur on left subtree

printPostorder(node.left);

// then recur on right subtree

printPostorder(node.right);

// now deal with the node

System.out.print(node.key + " ");
}

/* Given a binary tree, print its nodes in inorder*/

void printInorder(Node node)
{
if (node == null)
return;

/* first recur on left child */

printInorder(node.left);

/* then print the data of node */

System.out.print(node.key + " ");

/* now recur on right child */

printInorder(node.right);
}

/* Given a binary tree, print its nodes in preorder*/

void printPreorder(Node node)
{
if (node == null)
return;

/* first print data of node */

 System.out.print(node.key + " ");

/* then recur on left subtree */

printPreorder(node.left);

/* now recur on right subtree */

printPreorder(node.right);
}

// Wrappers over above recursive functions

void printPostorder() { printPostorder(root); }
void printInorder() { printInorder(root); }
void printPreorder() { printPreorder(root); }

// Driver method
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);

System.out.println(
"Preorder traversal of binary tree is ");
tree.printPreorder();

System.out.println(
"\nInorder traversal of binary tree is ");
tree.printInorder();

System.out.println(
"\nPostorder traversal of binary tree is ");
tree.printPostorder();
}
}
OUTPUT

Preorder traversal of binary tree is

12453
Inorder traversal of binary tree is
42513
Postorder traversal of binary tree is
45231

RESULT:

Thus, the implementation of tree traversal using java program was written and executed
successfully.
Ex.No:1(b) IMPLEMENTATION OF RECURSIVE FUNCTION
Date: FOR FIBONACCI

AIM:

To write the java program to implement the Fibonacci series using recursive function.

ALGORITHM:

1: Procedure Recursive_Fibonacci(n)
2: int f0, f1
3: f0 := 0
4: f1 := 1
5: if(n <= 1):
return n
6: return Recursive_Fibonacci(n-1) + Recursive_Fibonacci(n-2)
7: END Recursive_Fibonacci

PROGRAM

import java.util.Scanner;
//Using Recursion
public class FibonacciCalc{
public static int fibonacciRecursion(int n){
if(n == 0)
{
return 0;
}
if(n == 1 || n == 2)
{
return 1;
}
return fibonacciRecursion(n-2) + fibonacciRecursion(n-1);
}
public static void main(String args[]) {
int maxNumber = 10;
System.out.print("Fibonacci Series of "+maxNumber+" numbers: ");
for(int i = 0; i < maxNumber; i++)
{
System.out.print(fibonacciRecursion(i) +" ");
}
}
}

.
OUTPUT:
Fibonacci Series of 10 numbers: 0 1 1 2 3 5 8 13 21 34

RESULT:
Thus, the implementation of Fibonacci series using java program was written and
executed successfully.
Ex.No.2(a) IMPLEMENTATION OF ITERATIVE FUNCTION
Date: FOR FIBONACCI

AIM:

To write the java program to implement the Fibonacci series using iterative function.

ALGORITHM:

1. Procedure Iterative_Fibonacci(n):
2. int f0, f1, fib
3. f0 = 0
4. f1 = 1
5. display f0, f1
6. for int i := 1 to n:
7. fib := f0 + f1
8. f0 := f1
9. f1 := fib
10. display fib
11. END for loop
12. END Iterative_Fibonacci

PROGRAM:

import java.util.*;
class Main{
public static void main(String ...a){
int first = 0, second = 1, result, i;
Scanner sc= new Scanner(System.in);
System.out.print("Enter number- ");
int n= sc.nextInt();
System.out.println("fibonacci series is: ");
for (i = 0; i < n; i++)
{
if (i <= 1)
result = i;
else
{
result = first + second;
first = second;
second = result;
}
System.out.println(result);
}
 }

OUTPUT:
ENTER NUMBER:6
FIBONACCI SERIES IS
0
1
1
2
3
5

RESULT:

Thus, the implementation of iterative function for Fibonacci series using java program was
written and executed successfully.
Ex.No.2(b) IMPLEMENTATION OF ITERATIVE FUNCTION FOR INORDER
Date: TREE TRAVERSEL

AIM:

To write the java program to implement the In order tree traversal using iterative function.

ALGORITHM:

iterative algorithm to perform inorder traversal:

1. Start with the node equals root
2. Store the node in the stack and visit it's left child.
3. Repeat step 2 while node is not NULL, if it's NULL then pop it's parent (i.e. the last node in
stack) and print it.
4. Now move to node's right child and repeat step 1
5. Repeat whole procedure while node is not NULL and stack is not empty

PROGRAM:

import java.util.Stack;
class Node
{
int data;
Node left, right;
// Function to create a new binary tree node having a given key
public Node(int key)
{
data = key;
left = right = null;
}
}

class Main
{
// Iterative function to perform inorder traversal on the tree
public static void inorderIterative(Node root)
{
// create an empty stack
Stack<Node> stack = new Stack<>();

// start from the root node (set current node to the root node)
Node curr = root;

// if the current node is null and the stack is also empty, we are done
while (!stack.empty() || curr != null)
{
 // if the current node exists, push it into the stack (defer it)
// and move to its left child
if (curr != null)
{
stack.push(curr);
curr = curr.left;
}
else {
// otherwise, if the current node is null, pop an element from
// the stack, print it, and finally set the current node to its
// right child
curr = stack.pop();
System.out.print(curr.data + " ");

curr = curr.right;
}
}
}

public static void main(String[] args)

{
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(6);
root.right.left.left = new Node(7);
root.right.left.right = new Node(8);
inorderIterative(root);
}
}

OUTPUT:

42175836
RESULT:

Thus, the implementation of iterative function for in order traversal using java program was
written and executed successfully.
Ex.No:2(c) IMPLEMENTATION OF ITERATIVE FUNCTION
Date: FOR PREORDER TREE TRAVERSEL

AIM:

To write the java program to implement the pre order tree traversal using iterative function.

ALGORITHM:

1. Start with node equal to root node

2. Store the node in the stack, print it and visit it's left child.

3. Repeat step 2 while node is not NULL, if it's NULL then pop it's parent (i.e. the last node in
stack).

4. Now move to node's right child and repeat step 2

5. Repeat whole procedure while node is not NULL and stack is not empty

PROGRAM:

import java.util.Stack;
// Data structure to store a binary tree node
class Node
{
int data;
Node left, right;

// Function to create a new binary tree node having a given key

public Node(int key)
{
data = key;
left = right = null;
}
}

class Main
{
// Iterative function to perform preorder traversal on the tree
public static void preorderIterative(Node root)
{
// return if the tree is empty
if (root == null) {
return;
}
 // create an empty stack and push the root node
Stack<Node> stack = new Stack<>();
stack.push(root);

// loop till stack is empty

while (!stack.empty())
{
// pop a node from the stack and print it
Node curr = stack.pop();

System.out.print(curr.data + " ");

// push the right child of the popped node into the stack
if (curr.right != null) {
stack.push(curr.right);
}

// push the left child of the popped node into the stack
if (curr.left != null) {
stack.push(curr.left);
}

// the right child must be pushed first so that the left child
// is processed first (LIFO order)
}
}

public static void main(String[] args)

{

Node root = new Node(1);

root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(6);
root.right.left.left = new Node(7);
root.right.left.right = new Node(8);

preorderIterative(root);
}
}
OUTPUT:

12435786

RESULT:

Thus, the implementation of iterative function for Pre order traversal using java program was
written and executed successfully.
Ex.No:2(d) IMPLEMENTATION OF ITERATIVE FUNCTION
Date: FOR POST ORDER TREE TRAVERSEL

AIM:

To write the java program to implement the Post order tree traversal using iterative function.

ALGORITHM:

1. Start with the root node.

2. Store the node in the stack, and visit it's left child.

3. Repeat step 1 while node is not NULL, if it's NULL:

- Pick the top most node from the stack.

- If it's right child is NULL, then print the node and set prev pointer to this node

- If it's not NULL, check whether the right child is equal to prev pointer, if it is then print
the node, else repeat step 1 with the right child

- In this step, if you print the node then current is made equal to NULL and this sub-loop is
repeated until stack is not empty and current is NULL

4. Since the root node remains in the stack till the end, the terminating condition is until stack is
empty

PROGRAM:

import java.util.Stack;
class Node
{
int data;
Node left, right;
// Function to create a new binary tree node having a given key
public Node(int key)
{
data = key;
left = right = null;
}
}
class Main
{
// Iterative function to perform postorder traversal on the tree
public static void postorderIterative(Node root)
{
// return if the tree is empty
if (root == null) {
return;
}

// create an empty stack and push the root node

Stack<Node> stack = new Stack<>();
stack.push(root);

// create another stack to store postorder traversal

Stack<Integer> out = new Stack<>();

// loop till stack is empty

while (!stack.empty())
{
// pop a node from the stack and push the data into the output stack
Node curr = stack.pop();
out.push(curr.data);

// push the left and right child of the popped node into the stack
if (curr.left != null) {
stack.push(curr.left);
}

if (curr.right != null) {
stack.push(curr.right);
}
}
// print postorder traversal
while (!out.empty()) {
System.out.print(out.pop() + " ");
}
}

public static void main(String[] args)

{
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(6);
root.right.left.left = new Node(7);
 root.right.left.right = new Node(8);

postorderIterative(root);
}
}

OUTPUT:

42785631

RESULT:

Thus, the implementation of iterative function for Postorder traversal using java program was
written and executed successfully.
Ex.No:3a IMPLEMENTATION OF MERGE SORT
Date:

AIM:

To write a java program to implement merge sort.

ALGORITHM:

1. If the list has only one element, return the list and terminate.
2. Split the list into two halves that are as equal in length as possible
3. Using recursion, sort both lists using mergesort.
4. Merge the two sorted lists and return the result.
5. Stop the program.

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

SAMPLE INPUT AND OUTPUT:

RESULT:
Thus the implementation of merge sort using java program was written and executed
successfully.
Ex.No:3b IMPLEMENTATION OF QUICK SORT
Date:

AIM:
To write a java program to implement quick sort.

ALGORITHM:
1. Divide by choosing any element in the subarray array[p..r].This is called pivot.
2. Rearrange the elements in array[p..r] so that all elements in array[p..r] that are less
than or equal to the pivot are to its left and all elements that are greater than the pivot are to
its right.This is called partitioning.
3. Choose the rightmost element in the subarray, array[r], as the pivot.
4. Conquer by recursively sorting the subarrays array[p..q-1] and array[q+1..r] .
5. Combine the elements that are sorted.
6. All elements to the left of the pivot, in array[p..q-1], are less than or equal to the
pivot and are sorted, and all elements to the right of the pivot, in array[q+1..r], are greater
than the pivot and are sorted.

PROGRAM:

import java.io.*;
public class MyQuickSort {
private int array[];
private int length;
public void sort(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
}
private void quickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
i++;
j--;
}
}
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}

private void exchangeNumbers(int i, int j) {

int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

public static void main(String a[]){

MyQuickSort sorter = new MyQuickSort();

int[] input = {24,2,45,20,56,75,2,56,99,53,12};
sorter.sort(input);
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
}
}
SAMPLE INPUT AND OUTPUT:

RESULT:
Thus the implementation of quick sort using java program was written and executed
successfully.
Ex.No:4 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.

PROGRAM :
import java.util.*;
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;
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(current.left==null && current.right==null)
{
if(current==root)
{
root = null;
}
if(isLeftChild ==true)
{
parent.left = null;
}
Else
{
parent.right = null;
}
}
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;
}
Else
{
parent.right = current.right;
}
}
else if(current.left!=null && current.right!=null)
{
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;
while(current!=null)
{
successsorParent = successsor;
successsor = current;
current = current.left;
}
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)
{
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);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;
left = null;
right = null;
}
}
SAMPLE INPUT AND OUTPUT:

RESULT:
Thus, the implementation of Binary Search Tree was written and executed successfully.
Ex.No:5 IMPLEMENTATION OF RED BLACK TREE
Date:

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.

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;
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 );
}
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
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;
}
}
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)
{
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)
{
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);
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)
{
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);
} while (ch == 'Y'|| ch == 'y');
}
}

SAMPLE INPUT AND OUTPUT:

RESULT:
Thus, the implementation of red black tree was written and executed successfully.
Ex.No:6 IMPLEMENTATION OF HEAP
Date:

AIM:
To write a java program for implement a heap.

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).

PROGRAM :
import java.util.Scanner;
class Heap
{
private int[] heapArray;
private int maxSize;
private int heapSize;
public Heap(int mx)
{
maxSize = mx;
heapSize = 0;
heapArray = new int[maxSize];
}
public boolean isEmpty()
{
return heapSize == 0;
}
public boolean insert(int ele)
{
if (heapSize + 1 == maxSize)
return false;
heapArray[++heapSize] = ele;
int pos = heapSize;
while (pos != 1 && ele > heapArray[pos/2])
{
heapArray[pos] = heapArray[pos/2];
pos /=2;
}
heapArray[pos] = ele;
return true;
}
public int remove()
{
int parent, child;
int item, temp;
if (isEmpty() )
throw new RuntimeException("Error : Heap empty!");
item = heapArray[1];
temp = heapArray[heapSize--];
parent = 1;
child = 2;
while (child <= heapSize)
{
if (child < heapSize && heapArray[child] < heapArray[child + 1])
child++;
if (temp >= heapArray[child])
break;
heapArray[parent] = heapArray[child];
parent = child;
child *= 2;
}
heapArray[parent] = temp;
return item;
}
public void displayHeap()
{
System.out.print("\nHeap array: ");
for(int i = 1; i <= heapSize; i++)
System.out.print(heapArray[i] +" ");
System.out.println("\n");
}
}
public class HeapTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Heap Test\n\n");
System.out.println("Enter size of heap");
Heap h = new Heap(scan.nextInt() )
char ch;
do
{
System.out.println("\nHeap Operations\n");
System.out.println("1. insert ");
System.out.println("2. delete item with max key ");
System.out.println("3. check empty");
boolean chk;
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
chk = h.insert( scan.nextInt() );
if (chk)
System.out.println("Insertion successful\n");
else
System.out.println("Insertion failed\n");
break;
case 2 :
System.out.println("Enter integer element to delete");
if (!h.isEmpty())
h.remove();
else
System.out.println("Error. Heap is empty\n");
break;
case 3 :
System.out.println("Empty status = "+ h.isEmpty());
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
h.displayHeap();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
SAMPLE INPUT AND OUTPUT:

RESULT:
Thus, the implementation of Heap using java program was written and executed and
successfully.
Ex.No:7 FIBONACCI HEAP IMPLEMENTATION
Date:

AIM:
To write a java program for Fibonacci heap implementation.

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.

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;
}
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);
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 :
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');
}
}

SAMPLE INPUT AND OUTPUT:

RESULT:
Thus, the implementation of Fibonacci Heap using java program was written and
executed and successfully.
Ex.No:8 DEPTH FIRST SEARCH IMPLEMENTATION
Date:

AIM:
To write a java program to implement Graph Traversals using Depth First Search tree
algorithm.

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.

PROGRAM :

package org.arpit.java2blog;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class DepthFirstSearchExampleNeighbourList
{
static class Node
{
int data;
boolean visited;
List<Node> neighbours;
Node(int data)
{
this.data=data;
this.neighbours=new ArrayList<>();
}
public void addneighbours(Node neighbourNode)
{
this.neighbours.add(neighbourNode);
}
public List<Node> getNeighbours()
{
return neighbours;
}
public void setNeighbours(List<Node> neighbours)
{
this.neighbours = neighbours;
}
}
public void dfs(Node node)
{
System.out.print(node.data + " ");
List<Node> neighbours=node.getNeighbours();
for (int i = 0; i < neighbours.size(); i++)
{
Node n=neighbours.get(i);
if(n!=null && !n.visited)
{
dfs(n);
n.visited=true;
}
}
}
public void dfsUsingStack(Node node)
{
Stack<Node> stack=new Stack<Node>();
stack.add(node);
node.visited=true;
while (!stack.isEmpty())
{
Node element=stack.pop();
System.out.print(element.data + " ");
List<Node> neighbours=element.getNeighbours();
for (int i = 0; i < neighbours.size(); i++)
{
Node n=neighbours.get(i);
if(n!=null && !n.visited)
{
stack.add(n);
n.visited=true;
}
}
}
}
public static void main(String arg[])
{
Node node40 =new Node(40);
Node node10 =new Node(10);
Node node20 =new Node(20);
Node node30 =new Node(30);
Node node60 =new Node(60);
Node node50 =new Node(50);
Node node70 =new Node(70);
node40.addneighbours(node10);
node40.addneighbours(node20);
node10.addneighbours(node30);
node20.addneighbours(node10);
node20.addneighbours(node30);
node20.addneighbours(node60);
node20.addneighbours(node50);
node30.addneighbours(node60);
node60.addneighbours(node70);
node50.addneighbours(node70);
DepthFirstSearchExampleNeighbourList dfsExample = new
DepthFirstSearchExampleNeighbourList();
System.out.println("The DFS traversal of the graph using stack ");
dfsExample.dfsUsingStack(node40);
System.out.println();
node40.visited=false;
node10.visited=false;
node20.visited=false;
node30.visited=false;
node60.visited=false;
node50.visited=false;
node70.visited=false;
System.out.println("The DFS traversal of the graph using recursion ");
dfsExample.dfs(node40);
}
}

SAMPLE INPUT AND OUTPUT:

RESULT:
Thus, the implementation of Depth First Search using java program was written and
executed and successfully.
Ex.No:9 BREADTH FIRST SEARCH IMPLEMENTATION
Date:

AIM:
To write a java program to implement Graph Traversals using Breadth First Search
tree algorithm.

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.

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);
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");
}
scanner.close();
}
}
SAMPLE INPUT AND OUTPUT:

RESULT:
Thus, the implementation of Breadth First Search using java program was written and
executed and successfully.
Ex.No:10 IMPLEMENTATION OF KRUSKAL ALGORITHM
Date:

AIM:
To write a java program to implement Spanning tree implementation using kruskal’s
algorithm.

ALGORITHM:
1. Create a graph F (a set of trees), 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.

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)
{
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;
} 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();
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>
{
@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];
}
}
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;
}
i++;
}
stack.pop();
}
return cyclepresent;
}

SAMPLE INPUT AND OUTPUT:

RESULT:
Thus, the implementation of Kruskal Algorithm for spanning tree was written and
executed and successfully.
Ex.No:11 IMPLEMENTATION OF PRIM’s ALGORITHM
Date:

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.Assign key value as 0 for the first vertex so that it is picked first.
3. 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.

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

SAMPLE INPUT AND OUTPUT:

RESULT:
Thus, the implementation of Prim’s Algorithm for spanning tree was written and
executed and successfully.
Ex.No:12 IMPLEMENTATION OF DIJKSTRA’s ALGORITHM
Date:

AIM:
To write a java program to implement Dijkstra 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.
Repeating of steps 4 to 7 until there aren't any nodes left with a permanent
distance, which neighbours still have temporary distance

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;
}
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;
}
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");
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)
{
System.out.println("Wrong Input Format");
}
scan.close();
}
}
SAMPLE INPUT AND OUTPUT:

RESULT:
Thus, the implementation of Dijkstra Algorithm for finding shortest path was written
and executed and successfully.
Ex.No:13 IMPLEMENTATION OF BELLMAN FORD ALGORITHM
Date:

AIM:
To write a java program to implement bellman 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.After all
vertices have their path lengths we check if a negative cycle is present

PROGRAM :
importjava.util.Scanner;
public class BellmanFord
{
privateint distances[];
privateintnumberofvertices;
public static final int MAX_VALUE = 999;

publicBellmanFord(intnumberofvertices)
{
this.numberofvertices = numberofvertices;
distances = new int[numberofvertices + 1];
}

public void BellmanFordEvaluation(int source, intadjacencymatrix[][])

{
for (int node = 1; node <= numberofvertices; node++)
{
distances[node] = MAX_VALUE;
}

distances[source] = 0;
for (int node = 1; node <= numberofvertices - 1; node++)
{
for (intsourcenode = 1; sourcenode<= numberofvertices; sourcenode++)
{
for (intdestinationnode = 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];
}
}
}
}

for (intsourcenode = 1; sourcenode<= numberofvertices; sourcenode++)

{
for (intdestinationnode = 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)

{
intnumberofvertices = 0;
int source;
Scanner scanner = new Scanner(System.in);

System.out.println("Enter the number of vertices");

numberofvertices = scanner.nextInt();

intadjacencymatrix[][] = new int[numberofvertices + 1][numberofvertices + 1];

System.out.println("Enter the adjacency matrix");
for (intsourcenode = 1; sourcenode<= numberofvertices; sourcenode++)
{
for (intdestinationnode = 1; destinationnode<= numberofvertices; destinationnode++)
{
adjacencymatrix[sourcenode][destinationnode] = scanner.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();

BellmanFordbellmanford = new BellmanFord(numberofvertices);

bellmanford.BellmanFordEvaluation(source, adjacencymatrix);
scanner.close();
}
}

SAMPLE INPUT AND OUTPUT:

RESULT:
Thus, the implementation of Bellman Ford Algorithm for finding shortest path was
written and executed and successfully.
Ex.No:14 IMPLEMENTATION OF MATRIX CHAINDate:
MULTIPILICATION

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 parethesization.
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.

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++)
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);
}
}
SAMPLE INPUT AND OUTPUT:

RESULT:
Thus, the implementation of Matrix Chain Multiplication was written and executed
and successfully.
Ex.No:15 IMPLEMENTATION OF ACTIVITY SELECTION
Date:

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

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);
}
SAMPLE INPUT AND OUTPUT:

RESULT:
Thus, the implementation of Activity Selection was written and executed and
successfully.
Ex.No:16 IMPLEMENTATION OF HUFFMAN CODING
Date:

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.

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;
}
}
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);
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());
}
}
SAMPLE INPUT AND OUTPUT:

RESULT:
Thus, the implementation of Huffman coding was written and executed
andsuccessfully