Exp No : 1a

Implementation of recursive function for tree traversal

Date :
Aim:
To write a program to implement of Recursive function for tree traversal
Algorithm:
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)
Algorithm 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)
Algorithm Postorder(tree)
1. Traverse the left subtree, i.e., call Postorder(left-subtree)
2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.
PROGRAM

#include <iostream>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node {
int data;
struct Node *left, *right;
};
//Utility function to create a new tree node
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
void printPostorder(struct 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
cout << node->data << " ";
}

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

void printInorder(struct Node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
cout << node->data << " ";
/* now recur on right child */
printInorder(node->right);
}

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

void printPreorder(struct Node* node)
{
if (node == NULL)
return;
/* first print data of node */
 cout << node->data << " ";
/* then recur on left subtree */
printPreorder(node->left);
/* now recur on right subtree */
printPreorder(node->right);
}

/* Driver program to test above functions*/

int main()
{
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << "\nPreorder traversal of binary tree is \n";
printPreorder(root);
cout << "\nInorder traversal of binary tree is \n";
printInorder(root);
cout << "\nPostorder traversal of binary tree is \n";
printPostorder(root);
return 0;
}
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 C++ program to implement recursive function for tree traversal was written, executed
and verified successfully
Exp No : 1b
Implementation of recursive function Fibonacci
Date :

Aim:
To write a program to implement of recursive function for Fibonacci
Algorithm:
Step 1: Start the program
Step 2: Enter the number of terms
Step 3: To check the condition i<x call fib procedure
Step 4: To check the condition x==1 or x==0 print x
Step 5: if condition fail recursively call fib

PROGRAM :
#include <iostream>
using namespace std;
int fib(int x) {
if((x==1)||(x==0)) {
return(x);
}else {
return(fib(x-1)+fib(x-2));
}
}
int main() {
int x , i=0;
cout << "Enter the number of terms of series : ";
cin >> x;
cout << "\nFibonnaci Series : ";
while(i < x) {
cout << " " << fib(i);
i++;
}
return 0;
}
 OUTPUT:

Enter the number of terms of series : 15

Fibonnaci Series : 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

RESULT:
Thus the C++ program to implement recursive function for Fibonacci was written, executed and
verified successfully
Exp No : 2a
Implementation of iteration function for tree traversal
Date :

Aim:
To write a program to implement of Iteration function for tree traversal

Algorithm:
1) Create an empty stack nodeStack and push root node to stack.
2) Do the following while nodeStack is not empty.
….a) Pop an item from the stack and print it.
….b) Push right child of a popped item to stack
….c) Push left child of a popped item to stack
The right child is pushed before the left child to make sure that the left subtree is processed
first.
PROGRAM :

#include <bits/stdc++.h>
using namespace std;

// Tree Node
struct Node {
int data;
Node *left, *right;

Node(int data)
{
this->data = data;
this->left = this->right = NULL;
}
};

// Iterative function to do Preorder traversal of the tree

void preorderIterative(Node* root)
{
if (root == NULL)
return;

stack<Node*> st;

// start from root node (set current node to root node)

Node* curr = root;

// run till stack is not empty or current is

// not NULL
while (!st.empty() || curr != NULL) {
// Print left children while exist
// and keep pushing right into the
// stack.
while (curr != NULL) {
cout << curr->data << " ";

if (curr->right)
st.push(curr->right);

curr = curr->left;
}
// We reach when curr is NULL, so We
// take out a right child from stack
if (st.empty() == false) {
curr = st.top();
st.pop();
}
}
}
// Driver Code
int main()
{
Node* root = new Node(10);
root->left = new Node(20);
root->right = new Node(30);
root->left->left = new Node(40);
root->left->left->left = new Node(70);
root->left->right = new Node(50);
root->right->left = new Node(60);
root->left->left->right = new Node(80);
preorderIterative(root);
return 0;
}
Output :

10 20 40 70 80 50 30 60

RESULT:
Thus the C++ program to implement iteration function for tree traversal was written, executed
and verified successfully
Exp No : 2b
Implementation of Iteration function for Fibonacci
Date :

Aim:
To write a program to implement of Iteration function for Fibonacci
Algorithm:
Step 1: Start the program
Step 2: Enter the number of terms
Step 3: call fib procedure
Step 4: To check the condition i<n
Step 5: To compute z=x+y and assign the values x=y & y=z
Step 5: Repeat step 4 to 5 until the condition false
PROGRAM :
#include<iostream.h>
using namespace std;
void fib(int num) {
int x = 0, y = 1, z = 0;
for (int i = 0; i < num; i++) {
cout << x << " ";
z = x + y;
x = y;
y = z;
}
}
int main() {
int num;
cout << "Enter the number : ";
cin >> num;
cout << "\nThe fibonacci series : " ;
fib(num);
return 0;
}
Enter the number: 10
The Fibonacci series: 0 1 1 2 3 5 8 13 21 34

RESULT:
Thus the C++ program to implement iteration function Fibonacci was written, executed and
verified successfully
Ex. No. : 3a

Date : Implementation of Merge Sort analysis

AIM:

To write a C++ 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 merge sort.

4. Merge the two sorted lists and return the result.

5. Stop the program.

PROGRAM :

#include<iostream.h>
void merge sort(int [],int ,int );
void merge(int [], int, int ,int );

int main()
{
int n;
cout<<"Enter the size of the array"<<endl;
cin>>n;
int a[n];
cout<<"Enter the elements in the array"<<endl;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}

cout<<"sorting using merge sort"<<endl;

int p=1,r=n;

merge_sort(a,p,r);

cout<<"sorted form"<<endl;
for(int i=1;i<=n;i++)
{
cout<<"a["<<i<<"]="<<a[i]<<endl;
 }
return 0;
}

void merge_sort(int a[],int p,int r)

{
int q;
if(p<r)
{ q=(p+r)/2;
merge_sort(a,p,q);
merge_sort(a,q+1,r);
merge(a,p,q,r);
}
}

void merge(int a[],int p,int q,int r)

{
cout<<"Entered merge"<<endl;
int n1=q-p+1;
int n2=r-q;
int L[n1+1];
int R[n2+1];
for(int i=1;i<=n1;i++)
{
L[i]=a[p+i-1];
}
for(int j=1;j<=n2;j++)
{
R[j]=a[q+j];
}
L[n1+1]=999;
R[n2+1]=999;
int i=1, j=1;
for(int k=p;k<=r;k++)
{
if(L[i]<=R[j])
{
a[k]=L[i];
i=i+1;
}
else
{
a[k]=R[j];
j=j+1;
}
}
}
OUTPUT:

RESULT:

The given elements are sorted using Merge sort algorithm and analyzed.
Ex. No. : 3b IMPLEMENTATION OF QUICK SORT

Date :

AIM:

To write a C++ program to implement quick sort.

ALGORTIHM:

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.

PROGRAM:

#include<iostream.h>
void QUICK SORT(int [],int ,int );
int PARTITION(int [],int,int );

int main()
{
int n;
cout<<"Enter the size of the array"<<endl;
cin>>n;
int a[n];
cout<<"Enter the elements in the array"<<endl;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cout<<"sorting using quick sort"<<endl;
int p=1,r=n;
QUICKSORT(a,p,r);
cout<<"sorted form"<<endl;
for(int i=1;i<=n;i++)
{
 cout<<"a["<<i<<"]="<<a[i]<<endl;
}
return 0;
}

void QUICKSORT(int a[],int p,int r)

{
int q;
if(p<r)
{ q=PARTITION(a,p,r);
QUICKSORT(a,p,q-1);
QUICKSORT(a,q+1,r);
}
}

int PARTITION(int a[],int p,int r)

{
int temp,temp1;
int x=a[r];
int i=p-1;
for(int j=p;j<=r-1;j++)
{
if(a[j]<=x)
{

i=i+1;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp1=a[i+1];
a[i+1]=a[r];
a[r]=temp1;
return i+1;
}
OUTPUT:

RESULT:

The given elements are sorted using Quick sort algorithm and analyzed.
 Ex. No. :4 IMPLEMENTATION OF BINARY SEARCH TREE

Date :

AIM:

To write a C++ 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 :

# include <iostream.h>
# include <cstdlib>
struct nod//node declaration
{
int info;
struct nod *l;
struct nod *r;
}*r;
class BST
{
 public://functions declaration
void search(nod *, int);
void find(int, nod **, nod **);
void insert(nod *, nod *);
void del(int);
void casea(nod *,nod *);
void caseb(nod *,nod *);
void casec(nod *,nod *);
void preorder(nod *);
void inorder(nod *);
void postorder(nod *);
void show(nod *, int);
BST()
{
r = NULL;
}
};
void BST::find(int i, nod **par, nod **loc)//find the position of the item
{
nod *ptr, *ptrsave;
if (r == NULL)
{
*loc = NULL;
*par = NULL;
return;
}
if (i == r→info)
{
*loc = r;
*par = NULL;
return;
}
if (i < r→info)
ptr = r→l;
else
 ptr = r→r;
ptrsave = r;
while (ptr != NULL)
{
if (i == ptr→info)
{
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (i < ptr→info)
ptr = ptr→l;
else
ptr = ptr→r;
}
*loc = NULL;
*par = ptrsave;
}
void BST::search(nod *root, int data) //searching
{
int depth = 0;
nod *temp = new nod;
temp = root;
while(temp != NULL)
{
depth++;
if(temp→info == data)
{
cout<<"\nData found at depth: "<<depth<<endl;
return;
}
else if(temp→info > data)
temp = temp→l;
else
 temp = temp→r;
}
cout<<"\n Data not found"<<endl;
return;
}
void BST::insert(nod *tree, nod *newnode)
{
if (r == NULL)
{
r = new nod;
r→info = newnode→info;
r→l= NULL;
r→r= NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree→info == newnode→info)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (tree→info > newnode→info)
{
if (tree→l != NULL)
{
insert(tree→l, newnode);
}
else
{
tree→l= newnode;
(tree→l)→l = NULL;
(tree→l)→r= NULL;
cout<<"Node Added To Left"<<endl;
return;
}
 }
else
{
if (tree→r != NULL)
{
insert(tree→r, newnode);
}
else
{
tree→r = newnode;
(tree→r)→l= NULL;
(tree→r)→r = NULL;
cout<<"Node Added To Right"<<endl;
return;
}
}
}
void BST::del(int i)
{
nod *par, *loc;
if (r == NULL)
{
cout<<"Tree empty"<<endl;
return;
}
find(i, &par, &loc);
if (loc == NULL)
{
cout<<"Item not present in tree"<<endl;
return;
}
if (loc→l == NULL && loc→r == NULL)
{
casea(par, loc);
cout<<"item deleted"<<endl;
 }
if (loc→l!= NULL && loc→r == NULL)
{
caseb(par, loc);
cout<<"item deleted"<<endl;
}
if (loc→l== NULL && loc→r != NULL)
{
caseb(par, loc);
cout<<"item deleted"<<endl;
}
if (loc→l != NULL && loc→r != NULL)
{
casec(par, loc);
cout<<"item deleted"<<endl;
}
free(loc);
}
void BST::casea(nod *par, nod *loc )
{
if (par == NULL)
{
r= NULL;
}
else
{
if (loc == par→l)
par→l = NULL;
else
par→r = NULL;
}
}
void BST::caseb(nod *par, nod *loc)
{
nod *child;
 if (loc→l!= NULL)
child = loc→l;
else
child = loc→r;
if (par == NULL)
{
r = child;
}
else
{
if (loc == par→l)
par→l = child;
else
par→r = child;
}
}
void BST::casec(nod *par, nod *loc)
{
nod *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc→r;
while (ptr→l!= NULL)
{
ptrsave = ptr;
ptr = ptr→l;
}
suc = ptr;
parsuc = ptrsave;
if (suc→l == NULL && suc→r == NULL)
casea(parsuc, suc);
else
caseb(parsuc, suc);
if (par == NULL)
{
r = suc;
 }
else
{
if (loc == par→l)
par→l = suc;
else
par→r= suc;
}
suc→l = loc→l;
suc→r= loc→r;
}
void BST::preorder(nod *ptr)
{
if (r == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
cout<<ptr→info<<" ";
preorder(ptr→l);
preorder(ptr→r);
}
}
void BST::inorder(nod *ptr)//inorder traversal
{
if (r == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
inorder(ptr→l);
 cout<<ptr→info<<" ";
inorder(ptr→r);
}
}
void BST::postorder(nod *ptr)//postorder traversal
{
if (r == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
postorder(ptr→l);
postorder(ptr→r);
cout<<ptr→info<<" ";
}
}
void BST::show(nod *ptr, int level)//print the tree
{
int i;
if (ptr != NULL)
{
show(ptr→r, level+1);
cout<<endl;
if (ptr == r)
cout<<"Root→: ";
else
{
for (i = 0;i < level;i++)
cout<<" ";
}
cout<<ptr→info;
show(ptr→l, level+1);
}
}
int main()
{
int c, n,item;
BST bst;
nod *t;
while (1)
{
cout<<"1.Insert Element "<<endl;
cout<<"2.Delete Element "<<endl;
cout<<"3.Search Element"<<endl;
cout<<"4.Inorder Traversal"<<endl;
cout<<"5.Preorder Traversal"<<endl;
cout<<"6.Postorder Traversal"<<endl;
cout<<"7.Display the tree"<<endl;
cout<<"8.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>c;
switch(c)
{
case 1:
t = new nod;
cout<<"Enter the number to be inserted : ";
cin>>t→info;
bst.insert(r, t);
break;
case 2:
if (r == NULL)
{
cout<<"Tree is empty, nothing to delete"<<endl;
continue;
}
cout<<"Enter the number to be deleted : ";
cin>>n;
bst.del(n);
 break;
case 3:
cout<<"Search:"<<endl;
cin>>item;
bst.search(r,item);
break;
case 4:
cout<<"Inorder Traversal of BST:"<<endl;
bst.inorder(r);
cout<<endl;
break;
case 5:
cout<<"Preorder Traversal of BST:"<<endl;
bst.preorder(r);
cout<<endl;
break;
case 6:
cout<<"Postorder Traversal of BST:"<<endl;
bst.postorder(r);
cout<<endl;
break;
case 7:
cout<<"Display BST:"<<endl;
bst.show(r,1);
cout<<endl;
break;
case 8:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
}
Output

1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 1
Enter the number to be inserted : 6
Root Node is Added
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 1
Enter the number to be inserted : 7
Node Added To Right
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 1
Enter the number to be inserted : 5
Node Added To Left
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 1
Enter the number to be inserted : 4
Node Added To Left
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 3
Search:
7
Data found at depth: 2
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 3
Search:
1
Data not found
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 4
Inorder Traversal of BST:
4567
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 5
Preorder Traversal of BST:
6547
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 6
Postorder Traversal of BST:
4576
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 7
Display BST:
7
Root→: 6
5
4
1. Insert Element
2. Delete Element
3. Search Element
4. Inorder Traversal
5. Preorder Traversal
6. Postorder Traversal
7. Display the tree
8. Quit
Enter your choice : 2
Enter the number to be deleted : 1
Item not present in tree
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 5
Preorder Traversal of BST:
6547
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 2
Enter the number to be deleted : 5
item deleted
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 7
Display BST:
7
Root→: 6
4
1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 8
RESULT:

The operations Insert, Search, Delete, Count node, Check empty in Binary Search tree are
performed successfully.
 Ex.No.:5 RED-BLACK TREE IMPLEMENTATION

Date:

AIM:

To write a C++ 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:

#include<iostream.h>
struct node
{
int key;
node *parent;
char color;
node *left;
node *right;
};
class RBtree
{
node *root;
node *q;
public :
RBtree()
{
q=NULL;
root=NULL;
}
void insert();
 void insertfix(node *);
void leftrotate(node *);
void rightrotate(node *);
void del();
node* successor(node *);
void delfix(node *);
void disp();
void display( node *);
void search();
};
void RBtree::insert()
{
int z,i=0;
cout<<"\nEnter key of the node to be inserted: ";
cin>>z;
node *p,*q;
node *t=new node;
t->key=z;
t->left=NULL;
t->right=NULL;
t->color='r';
p=root;
q=NULL;
if(root==NULL)
{
root=t;
t->parent=NULL;
}
else
{
while(p!=NULL)
{
q=p;
if(p->key<t->key)
p=p->right;
else
p=p->left;
}
t->parent=q;
if(q->key<t->key)
q->right=t;
else
q->left=t;
}
insertfix(t);
}
void RBtree::insertfix(node *t)
{
node *u;
if(root==t)
{
 t->color='b';
return;
}
while(t->parent!=NULL&&t->parent->color=='r')
{
node *g=t->parent->parent;
if(g->left==t->parent)
{
if(g->right!=NULL)
{
u=g->right;
if(u->color=='r')
{
t->parent->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->right==t)
{
t=t->parent;
leftrotate(t);
}
t->parent->color='b';
g->color='r';
rightrotate(g);
}
}
else
{
if(g->left!=NULL)
{
u=g->left;
if(u->color=='r')
{
t->parent->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->left==t)
{
t=t->parent;
rightrotate(t);
}
 t->parent->color='b';
g->color='r';
leftrotate(g);
}
}
root->color='b';
}
}

void RBtree::del()
{
if(root==NULL)
{
cout<<"\nEmpty Tree." ;
return ;
}
int x;
cout<<"\nEnter the key of the node to be deleted: ";
cin>>x;
node *p;
p=root;
node *y=NULL;
node *q=NULL;
int found=0;
while(p!=NULL&&found==0)
{
if(p->key==x)
found=1;
if(found==0)
{
if(p->key<x)
p=p->right;
else
p=p->left;
}
}
if(found==0)
{
cout<<"\nElement Not Found.";
return ;
}
else
{
cout<<"\nDeleted Element: "<<p->key;
cout<<"\nColour: ";
if(p->color=='b')
cout<<"Black\n";
else
cout<<"Red\n";

if(p->parent!=NULL)
 cout<<"\nParent: "<<p->parent->key;
else
cout<<"\nThere is no parent of the node. ";
if(p->right!=NULL)
cout<<"\nRight Child: "<<p->right->key;
else
cout<<"\nThere is no right child of the node. ";
if(p->left!=NULL)
cout<<"\nLeft Child: "<<p->left->key;
else
cout<<"\nThere is no left child of the node. ";
cout<<"\nNode Deleted.";
if(p->left==NULL||p->right==NULL)
y=p;
else
y=successor(p);
if(y->left!=NULL)
q=y->left;
else
{
if(y->right!=NULL)
q=y->right;
else
q=NULL;
}
if(q!=NULL)
q->parent=y->parent;
if(y->parent==NULL)
root=q;
else
{
if(y==y->parent->left)
y->parent->left=q;
else
y->parent->right=q;
}
if(y!=p)
{
p->color=y->color;
p->key=y->key;
}
if(y->color=='b')
delfix(q);
}
}

void RBtree::delfix(node *p)

{
node *s;
while(p!=root&&p->color=='b')
{
if(p->parent->left==p)
{
s=p->parent->right;
if(s->color=='r')
{
s->color='b';
p->parent->color='r';
leftrotate(p->parent);
s=p->parent->right;
}
if(s->right->color=='b'&&s->left->color=='b')
{
s->color='r';
p=p->parent;
}
else
{
if(s->right->color=='b')
{
s->left->color=='b';
s->color='r';
rightrotate(s);
s=p->parent->right;
}
s->color=p->parent->color;
p->parent->color='b';
s->right->color='b';
leftrotate(p->parent);
p=root;
}
}
else
{
s=p->parent->left;
if(s->color=='r')
{
s->color='b';
p->parent->color='r';
rightrotate(p->parent);
s=p->parent->left;
}
if(s->left->color=='b'&&s->right->color=='b')
{
s->color='r';
p=p->parent;
}
else
{
if(s->left->color=='b')
{
s->right->color='b';
 s->color='r';
leftrotate(s);
s=p->parent->left;
}
s->color=p->parent->color;
p->parent->color='b';
s->left->color='b';
rightrotate(p->parent);
p=root;
}
}
p->color='b';
root->color='b';
}
}

void RBtree::leftrotate(node *p)

{
if(p->right==NULL)
return ;
else
{
node *y=p->right;
if(y->left!=NULL)
{
p->right=y->left;
y->left->parent=p;
}
else
p->right=NULL;
if(p->parent!=NULL)
y->parent=p->parent;
if(p->parent==NULL)
root=y;
else
{
if(p==p->parent->left)
p->parent->left=y;
else
p->parent->right=y;
}
y->left=p;
p->parent=y;
}
}
void RBtree::rightrotate(node *p)
{
if(p->left==NULL)
return ;
else
{
 node *y=p->left;
if(y->right!=NULL)
{
p->left=y->right;
y->right->parent=p;
}
else
p->left=NULL;
if(p->parent!=NULL)
y->parent=p->parent;
if(p->parent==NULL)
root=y;
else
{
if(p==p->parent->left)
p->parent->left=y;
else
p->parent->right=y;
}
y->right=p;
p->parent=y;
}
}

node* RBtree::successor(node *p)

{
node *y=NULL;
if(p->left!=NULL)
{
y=p->left;
while(y->right!=NULL)
y=y->right;
}
else
{
y=p->right;
while(y->left!=NULL)
y=y->left;
}
return y;
}

void RBtree::disp()
{
display(root);
}
void RBtree::display(node *p)
{
if(root==NULL)
{
cout<<"\nEmpty Tree.";
 return ;
}
if(p!=NULL)
{
cout<<"\n\t NODE: ";
cout<<"\n Key: "<<p->key;
cout<<"\n Colour: ";
if(p->color=='b')
cout<<"Black";
else
cout<<"Red";
if(p->parent!=NULL)
cout<<"\n Parent: "<<p->parent->key;
else
cout<<"\n There is no parent of the node. ";
if(p->right!=NULL)
cout<<"\n Right Child: "<<p->right->key;
else
cout<<"\n There is no right child of the node. ";
if(p->left!=NULL)
cout<<"\n Left Child: "<<p->left->key;
else
cout<<"\n There is no left child of the node. ";
cout<<endl;
if(p->left)
{
cout<<"\n\nLeft:\n";
display(p->left);
}
/*else
cout<<"\nNo Left Child.\n";*/
if(p->right)
{
cout<<"\n\nRight:\n";
display(p->right);
}
/*else
cout<<"\nNo Right Child.\n"*/
}
}
void RBtree::search()
{
if(root==NULL)
{
cout<<"\nEmpty Tree\n" ;
return ;
}
int x;
cout<<"\n Enter key of the node to be searched: ";
cin>>x;
node *p=root;
 int found=0;
while(p!=NULL&& found==0)
{
if(p->key==x)
found=1;
if(found==0)
{
if(p->key<x)
p=p->right;
else
p=p->left;
}
}
if(found==0)
cout<<"\nElement Not Found.";
else
{
cout<<"\n\t FOUND NODE: ";
cout<<"\n Key: "<<p->key;
cout<<"\n Colour: ";
if(p->color=='b')
cout<<"Black";
else
cout<<"Red";
if(p->parent!=NULL)
cout<<"\n Parent: "<<p->parent->key;
else
cout<<"\n There is no parent of the node. ";
if(p->right!=NULL)
cout<<"\n Right Child: "<<p->right->key;
else
cout<<"\n There is no right child of the node. ";
if(p->left!=NULL)
cout<<"\n Left Child: "<<p->left->key;
else
cout<<"\n There is no left child of the node. ";
cout<<endl;

}
}
int main()
{
int ch,y=0;
RBtree obj;
do
{
cout<<"\n\t RED BLACK TREE " ;
cout<<"\n 1. Insert in the tree ";
cout<<"\n 2. Delete a node from the tree";
cout<<"\n 3. Search for an element in the tree";
cout<<"\n 4. Display the tree ";
 cout<<"\n 5. Exit " ;
cout<<"\nEnter Your Choice: ";
cin>>ch;
switch(ch)
{
case 1 : obj.insert();
cout<<"\nNode Inserted.\n";
break;
case 2 : obj.del();
break;
case 3 : obj.search();
break;
case 4 : obj.disp();
break;
case 5 : y=1;
break;
default : cout<<"\nEnter a Valid Choice.";
}
cout<<endl;

}while(y!=1);
return 1;
}

Output:
RESULT:

The red black tree and operations like Insert, Search, Count node, Check empty, Clear
tree are implemented.
 Ex.No:6 HEAP IMPLEMENTATION

Date:

AIM:

To write a C++ program for heap implement

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 :

#include <iostream.h>
void max_heap(int *a, int m, int n)
{
int j, t;
t = a[m];
j = 2 * m;
while (j <= n) {
if (j < n && a[j+1] > a[j])
j = j + 1;
if (t > a[j])
break;
else if (t <= a[j]) {
a[j / 2] = a[j];
j = 2 * j;
 }
}
a[j/2] = t;
return;
}
void build_maxheap(int *a,int n) {
int k;
for(k = n/2; k >= 1; k--) {
max_heap(a,k,n);
}
}
int main() {
int n, i;
cout<<"enter no of elements of array\n";
cin>>n;
int a[30];
for (i = 1; i <= n; i++) {
cout<<"enter elements"<<" "<<(i)<<endl;
cin>>a[i];
} build_maxheap(a,n);
cout<<"Max Heap\n";
for (i = 1; i <= n; i++) {
cout<<a[i]<<endl;
}
}
Output
enter no of elements of array
5
enter elements 1
7
enter elements 2
6
enter elements 3
2
enter elements 4
1
enter elements 5
4
Max Heap
7
6
2
1
4

RESULT:

Thus Binary heap operations Insert, Search, Count node, Check empty , Clear tree
operations are implemented and executed.
Ex.No.:7

Date: FIBONACCI HEAP IMPLEMENTATION

AIM:

To write a C++ 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.

PROGRAM :

#include <iostream.h>

#include <cmath>

#include <cstdlib>

struct node

int n;

int degree;

node* parent;

node* child;
 node* left;

node* right;

char mark;

char C;

};

class FibonacciHeap

private: int

nH; node

*H;

public:

node* InitializeHeap();

int Fibonnaci_link(node*, node*, node*);

node *Create_node(int);

node *Insert(node *, node *);

node *Union(node *, node *);

node *Extract_Min(node *);

int Consolidate(node *);

int Display(node *);

node *Find(node *, int);

int Decrease_key(node *, int, int);

int Delete_key(node *,int);

int Cut(node *, node *, node *);

 int Cascase_cut(node *, node *);

FibonacciHeap()

H = InitializeHeap();

};

node* FibonacciHeap::InitializeHeap()

node* np;

np = NULL;

return np;

/* Create Node */

node* FibonacciHeap::Create_node(int value)

node* x = new node;

x->n = value;

return x;

node* FibonacciHeap::Insert(node* H, node* x)

{
 x->degree = 0;

x->parent = NULL;

x->child = NULL;

x->left = x;

x->right = x;

x->mark = 'F';

x->C = 'N';

if (H != NULL)

(H->left)->right = x;

x->right = H;

x->left = H->left;

H->left = x;

if (x->n < H->n)

H = x;

else

H = x;

nH = nH + 1;

return H;

}
int FibonacciHeap::Fibonnaci_link(node* H1, node* y, node* z)

(y->left)->right = y->right;

(y->right)->left = y->left;

if (z->right == z)

H1 = z;

y->left = y;

y->right = y;

y->parent = z;

if (z->child == NULL)

z->child = y;

y->right = z->child;

y->left = (z->child)->left;

((z->child)->left)->right = y;

(z->child)->left = y;

if (y->n < (z->child)->n)

z->child = y;

z->degree++;

node* FibonacciHeap::Union(node* H1, node* H2)

node* np;

node* H = InitializeHeap();
 H = H1;

(H->left)->right = H2;

(H2->left)->right = H;

np = H->left;

H->left = H2->left;

H2->left = np;

return H;

int FibonacciHeap::Display(node* H)

node* p = H;

if (p == NULL)

cout<<"The Heap is Empty"<<endl;

return 0;

cout<<"The root nodes of Heap are: "<<endl;

do

cout<<p->n;

p = p->right;

if (p != H)
 {

cout<<"-->";

while (p != H && p->right != NULL);

cout<<endl;

node* FibonacciHeap::Extract_Min(node* H1)

node* p;

node* ptr;

node* z = H1;

p = z;

ptr = z;

if (z == NULL)

return z;

node* x;

node* np;

x = NULL;

if (z->child != NULL)

x = z->child;

if (x != NULL)

{
 ptr = x;

do

np = x->right;

(H1->left)->right = x;

x->right = H1;

x->left = H1->left;

H1->left = x;

if (x->n < H1->n)

H1 = x;

x->parent = NULL;

x = np;

while (np != ptr);

(z->left)->right = z->right;

(z->right)->left = z->left;

H1 = z->right;

if (z == z->right && z->child == NULL)

H = NULL;

else

H1 = z->right;
 Consolidate(H1);

nH = nH - 1;

return p;

int FibonacciHeap::Consolidate(node* H1)

int d, i;

float f = (log(nH)) / (log(2));

int D = f;

node* A[D];

for (i = 0; i <= D; i++)

A[i] = NULL;

node* x = H1;

node* y;

node* np;

node* pt = x;

do

pt = pt->right;

d = x->degree;

while (A[d] != NULL)

{
 y = A[d];

if (x->n > y->n)

np = x;

x = y;

y = np;

if (y == H1)

H1 = x;

Fibonnaci_link(H1, y, x);

if (x->right == x)

H1 = x;

A[d] = NULL;

d = d + 1;

A[d] = x;

x = x->right;

while (x != H1);

H = NULL;

for (int j = 0; j <= D; j++)

if (A[j] != NULL)

{
 A[j]->left = A[j];

A[j]->right =A[j];

if (H != NULL)

(H->left)->right = A[j];

A[j]->right = H;

A[j]->left = H->left;

H->left = A[j];

if (A[j]->n < H->n)

H = A[j];

else

H = A[j];

if(H == NULL)

H = A[j];

else if (A[j]->n < H->n)

H = A[j];

int FibonacciHeap::Decrease_key(node*H1, int x, int k)

{

node* y;

if (H1 == NULL)

cout<<"The Heap is Empty"<<endl;

return 0;

node* ptr = Find(H1, x);

if (ptr == NULL)

cout<<"Node not found in the Heap"<<endl;

return 1;

if (ptr->n < k)

cout<<"Entered key greater than current key"<<endl;

return 0;

ptr->n = k;

y = ptr->parent;

if (y != NULL && ptr->n < y->n)

Cut(H1, ptr, y);

 Cascase_cut(H1, y);

if (ptr->n < H->n)

H = ptr;

return 0;

int FibonacciHeap::Cut(node* H1, node* x, node* y)

if (x == x->right)

y->child = NULL;

(x->left)->right = x->right;

(x->right)->left = x->left;

if (x == y->child)

y->child = x->right;

y->degree = y->degree - 1;

x->right = x;

x->left = x;

(H1->left)->right = x;

x->right = H1;

x->left = H1->left;

H1->left = x;

x->parent = NULL;

x->mark = 'F';
}

int FibonacciHeap::Cascase_cut(node* H1, node* y)

node* z = y->parent;

if (z != NULL)

if (y->mark == 'F')

y->mark = 'T';

else

Cut(H1, y, z);

Cascase_cut(H1, z);

node* FibonacciHeap::Find(node* H, int k)

node* x = H;

x->C = 'Y';

node* p = NULL;
 if (x->n == k)

p = x;

x->C = 'N';

return p;

if (p == NULL)

if (x->child != NULL )

p = Find(x->child, k);

if ((x->right)->C != 'Y' )

p = Find(x->right, k);

x->C = 'N';

return p;

int FibonacciHeap::Delete_key(node* H1, int k)

node* np = NULL;

int t;

t = Decrease_key(H1, k, -5000);

if (!t)

np = Extract_Min(H);
 if (np != NULL)

cout<<"Key Deleted"<<endl;

else

cout<<"Key not Deleted"<<endl;

return 0;

int main()

int n, m, l;

FibonacciHeap fh;

node* p;

node* H;

H = fh.InitializeHeap();

while (1)

cout<<"----------------------------"<<endl;

cout<<"Operations on Binomial heap"<<endl;

cout<<"----------------------------"<<endl;

cout<<"1)Insert Element in the heap"<<endl;

cout<<"2)Extract Minimum key node"<<endl;

cout<<"3)Decrease key of a node"<<endl;

cout<<"4)Delete a node"<<endl;

cout<<"5)Display Heap"<<endl;
cout<<"6)Exit"<<endl;

cout<<"Enter Your Choice: ";

cin>>l;

switch(l)

case 1:

cout<<"Enter the element to be inserted: ";

cin>>m;

p = fh.Create_node(m);

H = fh.Insert(H, p);

break;

case 2:

p = fh.Extract_Min(H);

if (p != NULL)

cout<<"The node with minimum key: "<<p->n<<endl;

else

cout<<"Heap is empty"<<endl;

break;

case 3:

cout<<"Enter the key to be decreased: ";

cin>>m;

cout<<"Enter new key value: ";

cin>>l;
 fh.Decrease_key(H, m, l);

break;

case 4:

cout<<"Enter the key to be deleted: ";

cin>>m;

fh.Delete_key(H, m);

break;

case 5:

cout<<"The Heap is: "<<endl;

fh.Display(H);

break;

case 6:

exit(1);

default:

cout<<"Wrong Choice"<<endl;

return 0;

}
OUTPUT:

Operations on Binomial heap

----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 9
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 8
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 7
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 6
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 5
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 5
The Heap is:
The root nodes of Heap are:
5-->6-->7-->8-->9
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 2
The node with minimum key: 5
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 3
Enter the key to be decreased: 3
Enter new key value: 1
Node not found in the Heap
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 3
Enter the key to be decreased: 5
Enter new key value: 2
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 2
The node with minimum key: 2
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 6

Result:

Thus Fibbonacci heap operations Insert, Check empty , Clear tree operations are
implemented and executed.
 Ex.No.:8

Date: GRAPH TRAVERSALS

AIM:

To write a C++ 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 :

#include <iostream.h>
#include <list>
using namespace std;
//graph class for DFS travesal
class DFSGraph
{
int V; // No. of vertices
list<int> *adjList; // adjacency list
void DFS_util(int v, bool visited[]); // A function used by DFS
public:
// class Constructor
DFSGraph(int V)
{
this->V = V;
adjList = new list<int>[V];
}
// function to add an edge to graph void
addEdge(int v, int w){
adjList[v].push_back(w); // Add w to v’s list.
}
void DFS(); // DFS traversal function
};
void DFSGraph::DFS_util(int v, bool visited[])
{
// current node v is visited
visited[v] = true;
cout << v << " ";

// recursively process all the adjacent vertices of the node

list<int>::iterator i;
for(i = adjList[v].begin(); i != adjList[v].end(); ++i)
if(!visited[*i])
DFS_util(*i, visited);
}

// DFS traversal
void DFSGraph::DFS()
{
// initially none of the vertices are visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;

// explore the vertices one by one by recursively calling DFS_util

for (int i = 0; i < V; i++)
if (visited[i] == false)
DFS_util(i, visited);
}

int main()
{
// Create a graph
DFSGraph gdfs(5);
gdfs.addEdge(0, 1);
gdfs.addEdge(0, 2);
gdfs.addEdge(0, 3);
gdfs.addEdge(1, 2);
gdfs.addEdge(2, 4);
gdfs.addEdge(3, 3);
gdfs.addEdge(4, 4);

cout << "Depth-first traversal for the given graph:"<<endl;

gdfs.DFS();

return 0;
}
Output:

Depth-first traversal for the given graph:

01243

RESULT:

Thus the program for implementing depth first search is successfully implemented.
 Ex.No.:9

Date: SPANNING TREE IMPLEMENTATION (PRIM’S)

AIM:

To write a C++ 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. 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 :

#include <bits/stdc++.h>
#define V 5
bool createsMST(int u, int v, vector<bool> inMST){
if (u == v)
return false;
if (inMST[u] == false && inMST[v] == false)
return false;
else if (inMST[u] == true && inMST[v] == true)
return false;
return true;
}
void printMinSpanningTree(int cost[][V]){
vector<bool> inMST(V, false);
inMST[0] = true;
int edgeNo = 0, MSTcost = 0;
 while (edgeNo < V - 1) {
int min = INT_MAX, a = -1, b = -1;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (cost[i][j] < min) {
if (createsMST(i, j, inMST)) {
min = cost[i][j];
a = i;
b = j;
}
}
}
}
if (a != -1 && b != -1) {
cout<<"Edge "<<edgeNo++<<" : ("<<a<<" , "<<b<<" ) : cost = "<<min<<endl;
MSTcost += min;
inMST[b] = inMST[a] = true;
}
}
cout<<"Cost of Minimum spanning tree ="<<MSTcost;
}
int main() {
int cost[][V] = {
{ INT_MAX, 12, INT_MAX, 25, INT_MAX },
{ 12, INT_MAX, 11, 8, 12 },
{ INT_MAX, 11, INT_MAX, INT_MAX, 17 },
{ 25, 8, INT_MAX, INT_MAX, 15 },
{ INT_MAX, 12, 17, 15, INT_MAX },
};
cout<<"The Minimum spanning tree for the given tree is :\n";
printMinSpanningTree(cost);
return 0;
}
Output

The Minimum spanning tree for the given tree is :

Edge 0 : (0 , 1 ) : cost = 12
Edge 1 : (1 , 3 ) : cost = 8
Edge 2 : (1 , 2 ) : cost = 11
Edge 3 : (1 , 4 ) : cost = 12
Cost of Minimum spanning tree =43

RESULT:

The program for finding the minimum spanning tree using Prim’s algorithm is
successfully executed.
Ex.No.:10a

Date: DIJKSTRAS ALGORITHM

AIM:

To write a C++ 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
neighbors still have temporary distance

PROGRAM:

#include<iostream>
#include<climits>
int miniDist(int distance[], bool Tset[]) // finding minimum distance
{
int minimum=INT_MAX,ind;

for(int k=0;k<6;k++)
{
if(Tset[k]==false && distance[k]<=minimum)
{
 minimum=distance[k];
ind=k;
}
}
return ind;
}

void DijkstraAlgo(int graph[6][6],int src) // adjacency matrix

{
int distance[6]; // // array to calculate the minimum distance for each node
bool Tset[6];// boolean array to mark visited and unvisited for each node

for(int k = 0; k<6; k++)

{
distance[k] = INT_MAX;
Tset[k] = false;
}

distance[src] = 0; // Source vertex distance is set 0

for(int k = 0; k<6; k++)

{
int m=miniDist(distance,Tset);
Tset[m]=true;
for(int k = 0; k<6; k++)
{
// updating the distance of neighbouring vertex
if(!Tset[k] && graph[m][k] && distance[m]!=INT_MAX &&
distance[m]+graph[m][k]<distance[k])
distance[k]=distance[m]+graph[m][k];
}
}
cout<<"Vertex\t\tDistance from source vertex"<<endl;
for(int k = 0; k<6; k++)
{
char str=65+k;
cout<<str<<"\t\t\t"<<distance[k]<<endl;
}
}

int main()
{
int graph[6][6]={
{0, 1, 2, 0, 0, 0},
{1, 0, 0, 5, 1, 0},
{2, 0, 0, 2, 3, 0},
{0, 5, 2, 0, 2, 2},
{0, 1, 3, 2, 0, 1},
{0, 0, 0, 2, 1, 0}};
 DijkstraAlgo(graph,0);
return 0;
}

Output:

Vertex Distance from Source

A 0
B 1
C 2

D 4

E 2

F 3

RESULT:

Thus the program for finding the shortest path using Dijkstra’s algorithm is successfully
implemented.
 Ex.No.:10b

Date: IMPLEMENTATION OF BELLMANFORD ALGORITHM

AIM:

To write a C++ program to implement quick sort.

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

PROGRAM :

#include <bits/stdc++.h>
struct Edge {
int src, dest, weight;
};
struct Graph {
int V, E;
struct Edge* edge;
};
struct Graph* createGraph(int V, int E) {
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->edge = new Edge[E];
return graph;
}
void BellmanFord(struct Graph* graph, int src) {
int V = graph->V;
 int E = graph->E;
int dist[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
for (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < E; j++) {
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for (int i = 0; i < E; i++) {
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
printf("Graph contains negative weight cycle");
return;
}
}
printf("Vertex :\t\t\t ");
for (int i = 0; i < V; ++i)
printf("%d \t", i);
printf("\nDistance From Source : ");
for (int i = 0; i < V; ++i)
printf("%d \t",dist[i]);
return;
}
int main() {
int V = 5;
int E = 8;
struct Graph* graph = createGraph(V, E);
graph->edge[0].src = 0;
 graph->edge[0].dest = 1;
graph->edge[0].weight = -1;
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
BellmanFord(graph, 0);
return 0;
}
Output
Vertex : 0 1 2 3 4
Distance From Source : 0 -1 2 -2 1

RESULT:

Thus the program for executing Bellman Ford algorithm for negative weighing edges is
successfully implemented.
Ex.No.:11

Date: IMPLEMENTATION OF MATRIX CHAIN MULTIPLICATION

AIM:

To write a C++ program to implement Matrix Chain Multiplication.

ALGORITHM:

A chain of matrices to be multiplied is given as input.

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)

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

A parenthesizing of the chain of the matrices is obtained as output

 PROGRAM :

#include<stdio.h>
#include<limits.h>

// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n

int MatrixChainMultiplication(int p[], int n)

{
int m[n][n];
int i, j, k, L, q;

for (i=1; i<n; i++)

m[i][i] = 0; //number of multiplications are 0(zero) when there is only one matrix

//Here L is chain length. It varies from length 2 to length n.

for (L=2; L<n; L++)
{
for (i=1; i<n-L+1; i++)
{
j = i+L-1;
m[i][j] = INT_MAX; //assigning to maximum value

for (k=i; k<=j-1; k++)

{
q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (q < m[i][j])
{
m[i][j] = q; //if number of multiplications found less that number will be updated.
}
}
}
}

return m[1][n-1]; //returning the final answer which is M[1][n]

int main()
{
int n,i;
printf("Enter number of matrices\n");
scanf("%d",&n);

n++;

int arr[n];

printf("Enter dimensions \n");

 for(i=0;i<n;i++)
{
printf("Enter d%d :: ",i);
scanf("%d",&arr[i]);
}

int size = sizeof(arr)/sizeof(arr[0]);

printf("Minimum number of multiplications is %d ", MatrixChainMultiplication(arr, size));

return 0;
}
Output

Enter number of matrices

4
Enter dimensions
Enter d0 :: 10
Enter d1 :: 100
Enter d2 :: 20
Enter d3 :: 5
Enter d4 :: 80
Minimum number of multiplications is 19000

RESULT:

Thus the program for implementing matrix chain multiplication is successfully

implemented.
 Ex.No.:12a

Date: IMPLEMENTATION OF ACTIVITY SELECTION

AIM:

To write a C++ 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 :

#include<stdio.h>
int main(){
int start[] = {1 , 5 , 12};
int finish[] = {10, 13, 23};
int activities = sizeof(start)/sizeof(start[0]);
int i, j;
printf ("Following activities are selected \t");
i = 0;
printf("%d\t", i);
for (j = 1; j < activities; j++){
if (start[j] >= finish[i]){
printf ("%d ", j);
i = j;
}
}
return 0;
}
Output
Following activities are selected 0 2

RESULT:

Thus the program for implementing activity selection problem is successfully

implemented.
 Ex.No.:12b

Date: IMPLEMENTATION OF HUFFMAN CODING

AIM:

To write a C++ 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 :
#include<iostream>
#include<queue>
#include<string>
using namespace std;
struct node{
int freq;
char data;
const node *child0, *child1;
node(char d, int f = -1){ //assign values in the node
data = d;
freq = f;
 child0 = NULL;
child1 = NULL;
}
node(const node *c0, const node *c1){
data = 0;
freq = c0->freq + c1->freq;
child0=c0;
child1=c1;
}
bool operator<( const node &a ) const { //< operator performs to find priority in queue
return freq >a.freq;
}
void traverse(string code = "")const{
if(child0!=NULL){
child0->traverse(code+'0'); //add 0 with the code as left child
child1->traverse(code+'1'); //add 1 with the code as right child
}else{
cout << "Data: " << data<< ", Frequency: "<<freq << ", Code: " << code<<endl;
}
}
};
void huffmanCoding(string str){
priority_queue<node> qu;
int frequency[256];
for(int i = 0; i<256; i++)
frequency[i] = 0; //clear all frequency
for(int i = 0; i<str.size(); i++){
frequency[int(str[i])]++; //increase frequency
}
for(int i = 0; i<256; i++){
if(frequency[i]){
qu.push(node(i, frequency[i]));
}
}
while(qu.size() >1){
node *c0 = new node(qu.top()); //get left child and remove from queue
 qu.pop();
node *c1 = new node(qu.top()); //get right child and remove from queue
qu.pop();
qu.push(node(c0, c1)); //add freq of two child and add again in the queue
}
cout << "The Huffman Code: "<<endl;
qu.top().traverse(); //traverse the tree to get code
}
main(){
string str = "ACCEBFFFFAAXXBLKE"; //arbitray string to get frequency
huffmanCoding(str);
}
Output
The Huffman Code:
Data: K, Frequency: 1, Code: 0000
Data: L, Frequency: 1, Code: 0001
Data: E, Frequency: 2, Code: 001
Data: F, Frequency: 4, Code: 01
Data: B, Frequency: 2, Code: 100
Data: C, Frequency: 2, Code: 101
Data: X, Frequency: 2, Code: 110
Data: A, Frequency: 3, Code: 111

RESULT:

Thus the program for implementing Huffman code is successfully implemented using an input file.