1.

IMPLEMENTATION OF AVL TREE AND ITS

OPERATIONS
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
int ht;
};
struct node* root = NULL;
struct node* create(int);
struct node* insert(struct node*, int);
struct node* delete(struct node*, int);
struct node* search(struct node*, int);
struct node* rotate_left(struct node*);
struct node* rotate_right(struct node*);
int balance_factor(struct node*);
int height(struct node*);
void inorder(struct node*);
void preorder(struct node*);
void postorder(struct node*);

int main()
{
int user_choice, data;
char user_continue = 'y';
struct node* result = NULL;

while (user_continue == 'y' || user_continue == 'Y')

{
printf("\n\n------- AVL TREE --------\n");
printf("\n1. Insert");
printf("\n2. Delete");
printf("\n3. Search");
printf("\n4. Inorder");
printf("\n5. Preorder");
printf("\n6. Postorder");
printf("\n7. EXIT");
printf("\n\nEnter Your Choice: ");
scanf("%d", &user_choice);
switch(user_choice)
{
case 1:
printf("\nEnter data: ");
scanf("%d", &data);
root = insert(root, data);
break;

case 2:
printf("\nEnter data: ");
scanf("%d", &data);
root = delete(root, data);
break;
case 3:
printf("\nEnter data: ");
scanf("%d", &data);
result = search(root, data);
if (result == NULL)
{
printf("\nNode not found!");
}
else
{
printf("\n Node found");
}
break;
case 4:
inorder(root);
break;
case 5:
preorder(root);
break;
case 6:
postorder(root);
break;
case 7:
printf("\n\tProgram Terminated\n");
return 1;
default:
printf("\n\tInvalid Choice\n");
}
printf("\n\nDo you want to continue? ");
scanf(" %c", &user_continue);
}

return 0;
}
struct node* create(int data)
{
struct node* new_node = (struct node*) malloc (sizeof(struct node));
if (new_node == NULL)
{
printf("\nMemory can't be allocated\n");
return NULL;
}
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
struct node* rotate_left(struct node* root)
{
struct node* right_child = root->right;
root->right = right_child->left;
right_child->left = root;
root->ht = height(root);
right_child->ht = height(right_child);
return right_child;
}
struct node* rotate_right(struct node* root)
{
struct node* left_child = root->left;
root->left = left_child->right;
left_child->right = root;
root->ht = height(root);
left_child->ht = height(left_child);
return left_child;
}
int balance_factor(struct node* root)
{
int lh, rh;
if (root == NULL)
return 0;
if (root->left == NULL)
lh = 0;
else
lh = 1 + root->left->ht;
if (root->right == NULL)
rh = 0;
else
rh = 1 + root->right->ht;
return lh - rh;
}
int height(struct node* root)
{
int lh, rh;
if (root == NULL)
{
return 0;
}
if (root->left == NULL)
lh = 0;
else
lh = 1 + root->left->ht;
if (root->right == NULL)
rh = 0;
else
rh = 1 + root->right->ht;

if (lh > rh)

return (lh);
return (rh);
}
struct node* insert(struct node* root, int data)
{
if (root == NULL)
{
struct node* new_node = create(data);
if (new_node == NULL)
{
return NULL;
}
root = new_node;
}
else if (data > root->data)
{
root->right = insert(root->right, data);
if (balance_factor(root) == -2)
{
if (data > root->right->data)
{
root = rotate_left(root);
}
else
{
root->right = rotate_right(root->right);
root = rotate_left(root);
}
}
}
else
{
root->left = insert(root->left, data);
if (balance_factor(root) == 2)
{
if (data < root->left->data)
{
root = rotate_right(root);
}
else
{
root->left = rotate_left(root->left);
root = rotate_right(root);
}
}
}
root->ht = height(root);
return root;
}
struct node * delete(struct node *root, int x)
{
struct node * temp = NULL;

if (root == NULL)
{
return NULL;
}

if (x > root->data)
{
root->right = delete(root->right, x);
if (balance_factor(root) == 2)
{
if (balance_factor(root->left) >= 0)
{
root = rotate_right(root);
}
else
{
root->left = rotate_left(root->left);
root = rotate_right(root);
}
}
}
else if (x < root->data)
{
root->left = delete(root->left, x);
if (balance_factor(root) == -2)
{
if (balance_factor(root->right) <= 0)
{
root = rotate_left(root);
}
else
{
root->right = rotate_right(root->right);
root = rotate_left(root);
}
}
}
else
{
if (root->right != NULL)
{
temp = root->right;
while (temp->left != NULL)
temp = temp->left;

root->data = temp->data;
root->right = delete(root->right, temp->data);
if (balance_factor(root) == 2)
{
if (balance_factor(root->left) >= 0)
{
root = rotate_right(root);
}
else
{
root->left = rotate_left(root->left);
root = rotate_right(root);
}
}
}
else
{
return (root->left);
}
}
root->ht = height(root);
return (root);
}
struct node* search(struct node* root, int key)
{
if (root == NULL)
{
return NULL;
}

if(root->data == key)
{
return root;
}
if(key > root->data)
{
search(root->right, key);
}
else
{
search(root->left, key);
}
}
void inorder(struct node* root)
{
if (root == NULL)
{
return;
}
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
void preorder(struct node* root)
{
if (root == NULL)
return;
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
void postorder(struct node* root)
{
if (root == NULL)
{
return;
}
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
OUTPUT:

------- AVL TREE --------

1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 1
Enter data: 2
Do you want to continue? y

------- AVL TREE --------

1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 1
Enter data: 2
Do you want to continue? y

------- AVL TREE --------

1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT

Enter Your Choice: 3

Enter data: 2

Node found

Do you want to continue? y

------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 2
Enter data: 2
Do you want to continue? y

------- AVL TREE --------

1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 4
2
Do you want to continue? N
 2.IMPLEMENTATION OF B TREE AND ITS OPERATIONS
#include <stdio.h>

#include <stdlib.h>

#define MAX 4

#define MIN 2

struct btreeNode {

int val[MAX + 1], count;

struct btreeNode *link[MAX + 1];

};

struct btreeNode *root;

/* creating new node */

struct btreeNode * createNode(int val, struct btreeNode *child) {

struct btreeNode *newNode;

newNode = (struct btreeNode *)malloc(sizeof(struct btreeNode));

newNode->val[1] = val;

newNode->count = 1;

newNode->link[0] = root;

newNode->link[1] = child;

return newNode;

/* Places the value in appropriate position */

void addValToNode(int val, int pos, struct btreeNode *node,

struct btreeNode *child) {

int j = node->count;
while (j > pos) {

node->val[j + 1] = node->val[j];

node->link[j + 1] = node->link[j];

j--;

node->val[j + 1] = val;

node->link[j + 1] = child;

node->count++;

/* split the node */

void splitNode (int val, int *pval, int pos, struct btreeNode *node,

struct btreeNode *child, struct btreeNode **newNode) {

int median, j;

if (pos > MIN)

median = MIN + 1;

else

median = MIN;

*newNode = (struct btreeNode *)malloc(sizeof(struct btreeNode));

j = median + 1;

while (j <= MAX) {

(*newNode)->val[j - median] = node->val[j];

(*newNode)->link[j - median] = node->link[j];

j++;

}
node->count = median;

(*newNode)->count = MAX - median;

if (pos <= MIN) {

addValToNode(val, pos, node, child);

} else {

addValToNode(val, pos - median, *newNode, child);

*pval = node->val[node->count];

(*newNode)->link[0] = node->link[node->count];

node->count--;

/* sets the value val in the node */

int setValueInNode(int val, int *pval,

struct btreeNode *node, struct btreeNode **child) {

int pos;

if (!node) {

*pval = val;

*child = NULL;

return 1;

if (val < node->val[1]) {

pos = 0;

} else {

for (pos = node->count;

(val < node->val[pos] && pos > 1); pos--);

if (val == node->val[pos]) {

printf("Duplicates not allowed\n");

return 0;

if (setValueInNode(val, pval, node->link[pos], child)) {

if (node->count < MAX) {

addValToNode(*pval, pos, node, *child);

} else {

splitNode(*pval, pval, pos, node, *child, child);

return 1;

return 0;

/* insert val in B-Tree */

void insertion(int val) {

int flag, i;

struct btreeNode *child;

flag = setValueInNode(val, &i, root, &child);

if (flag)

root = createNode(i, child);

}
/* copy successor for the value to be deleted */

void copySuccessor(struct btreeNode *myNode, int pos) {

struct btreeNode *dummy;

dummy = myNode->link[pos];

for (;dummy->link[0] != NULL;)

dummy = dummy->link[0];

myNode->val[pos] = dummy->val[1];

/* removes the value from the given node and rearrange values */

void removeVal(struct btreeNode *myNode, int pos) {

int i = pos + 1;

while (i <= myNode->count) {

myNode->val[i - 1] = myNode->val[i];

myNode->link[i - 1] = myNode->link[i];

i++;

myNode->count--;

/* shifts value from parent to right child */

void doRightShift(struct btreeNode *myNode, int pos) {

struct btreeNode *x = myNode->link[pos];

int j = x->count;

while (j > 0) {
x->val[j + 1] = x->val[j];

x->link[j + 1] = x->link[j];

x->val[1] = myNode->val[pos];

x->link[1] = x->link[0];

x->count++;

x = myNode->link[pos - 1];

myNode->val[pos] = x->val[x->count];

myNode->link[pos] = x->link[x->count];

x->count--;

return;

/* shifts value from parent to left child */

void doLeftShift(struct btreeNode *myNode, int pos) {

int j = 1;

struct btreeNode *x = myNode->link[pos - 1];

x->count++;

x->val[x->count] = myNode->val[pos];

x->link[x->count] = myNode->link[pos]->link[0];

x = myNode->link[pos];

myNode->val[pos] = x->val[1];

x->link[0] = x->link[1];

x->count--;

while (j <= x->count) {

x->val[j] = x->val[j + 1];

x->link[j] = x->link[j + 1];

j++;

return;

/* merge nodes */

void mergeNodes(struct btreeNode *myNode, int pos) {

int j = 1;

struct btreeNode *x1 = myNode->link[pos], *x2 = myNode->link[pos - 1];

x2->count++;

x2->val[x2->count] = myNode->val[pos];

x2->link[x2->count] = myNode->link[0];

while (j <= x1->count) {

x2->count++;

x2->val[x2->count] = x1->val[j];

x2->link[x2->count] = x1->link[j];

j++;

j = pos;

while (j < myNode->count) {

myNode->val[j] = myNode->val[j + 1];

myNode->link[j] = myNode->link[j + 1];

j++;
}

myNode->count--;

free(x1);

/* adjusts the given node */

void adjustNode(struct btreeNode *myNode, int pos) {

if (!pos) {

if (myNode->link[1]->count > MIN) {

doLeftShift(myNode, 1);

} else {

mergeNodes(myNode, 1);

} else {

if (myNode->count != pos) {

if(myNode->link[pos - 1]->count > MIN) {

doRightShift(myNode, pos);

} else {

if (myNode->link[pos + 1]->count > MIN) {

doLeftShift(myNode, pos + 1);

} else {

mergeNodes(myNode, pos);

} else {
if (myNode->link[pos - 1]->count > MIN)

doRightShift(myNode, pos);

else

mergeNodes(myNode, pos);

/* delete val from the node */

int delValFromNode(int val, struct btreeNode *myNode) {

int pos, flag = 0;

if (myNode) {

if (val < myNode->val[1]) {

pos = 0;

flag = 0;

} else {

for (pos = myNode->count;

(val < myNode->val[pos] && pos > 1); pos--);

if (val == myNode->val[pos]) {

flag = 1;

} else {

flag = 0;

}}

if (flag) {

if (myNode->link[pos - 1]) {
copySuccessor(myNode, pos);

flag = delValFromNode(myNode->val[pos], myNode->link[pos]);

if (flag == 0) {

printf("Given data is not present in B-Tree\n");

} else {

removeVal(myNode, pos);

} else {

flag = delValFromNode(val, myNode->link[pos]);

if (myNode->link[pos]) {

if (myNode->link[pos]->count < MIN)

adjustNode(myNode, pos);

}}

return flag;

/* delete val from B-tree */

void deletion(int val, struct btreeNode *myNode) {

struct btreeNode *tmp;

if (!delValFromNode(val, myNode)) {

printf("Given value is not present in B-Tree\n");

return;

} else {
if (myNode->count == 0) {

tmp = myNode;

myNode = myNode->link[0];

free(tmp);

}}

root = myNode;

return;

/* search val in B-Tree */

void searching(int val, int *pos, struct btreeNode *myNode) {

if (!myNode) {

return;

if (val < myNode->val[1]) {

*pos = 0;

} else {

for (*pos = myNode->count;

(val < myNode->val[*pos] && *pos > 1); (*pos)--);

if (val == myNode->val[*pos]) {

printf("Given data %d is present in B-Tree", val);

return;

}}

searching(val, pos, myNode->link[*pos]);

return;
}

/* B-Tree Traversal */

void traversal(struct btreeNode *myNode) {

int i;

if (myNode) {

for (i = 0; i < myNode->count; i++) {

traversal(myNode->link[i]);

printf("%d ", myNode->val[i + 1]);

traversal(myNode->link[i]);

}}

int main() {

int val, ch;

clrscr();

while (1) {

printf("\n********B TREE IMPLEMENTATION*********\n");

printf("1. Insertion\t2. Deletion\n");

printf("3. Searching\t4. Traversal\n");

printf("5. Exit\nEnter your choice:");

scanf("%d", &ch);

switch (ch) {

case 1:

printf("Enter your input:");

scanf("%d", &val);
insertion(val);

break;

case 2:

printf("Enter the element to delete:");

scanf("%d", &val);

deletion(val, root);

break;

case 3:

printf("Enter the element to search:");

scanf("%d", &val);

searching(val, &ch, root);

break;

case 4:

traversal(root);

break;

case 5:

exit(0);

default:

printf("U have entered wrong option!!\n");

break;

printf("\n");

}
OUTPUT:

********B TREE IMPLEMENTATION*********

1. Insertion 2. Deletion

3. Searching 4. Traversal

5. Exit

Enter your choice:1

Enter your input:22

********B TREE IMPLEMENTATION*********

1. Insertion 2. Deletion

3. Searching 4. Traversal

5. Exit

Enter your choice:1

Enter your input:45

********B TREE IMPLEMENTATION*********

1. Insertion 2. Deletion

3. Searching 4. Traversal

5. Exit

Enter your choice:1

Enter your input:93

********B TREE IMPLEMENTATION*********

1. Insertion 2. Deletion

3. Searching 4. Traversal

5. Exit

Enter your choice:1

Enter your input:165

********B TREE IMPLEMENTATION*********

1. Insertion 2. Deletion

3. Searching 4. Traversal

5. Exit

Enter your choice:4

22 45 93 165

********B TREE IMPLEMENTATION*********

1. Insertion 2. Deletion

3. Searching 4. Traversal

5. Exit

Enter your choice:2

Enter the element to delete:165

********B TREE IMPLEMENTATION*********

1. Insertion 2. Deletion

3. Searching 4. Traversal

5. Exit

Enter your choice:4

22 45 93

********B TREE IMPLEMENTATION*********

1. Insertion 2. Deletion

3. Searching 4. Traversal

5. Exit

Enter your choice:3

Enter the element to search:45

Given data 45 is present in B-Tree

********B TREE IMPLEMENTATION*********

1. Insertion 2. Deletion

3. Searching 4. Traversal

5. Exit

Enter your choice:5

 3.IMPLEMENTATION OF MIN AND MAX HEAP

#include<stdio.h>
#include<limits.h>
#define MAXSIZE 100
void swap(int *x,int *y);
void minHeapify(int arr[], int n,int i);
void maxHeapify(int arr[], int n, int i);
void buildMinHeap(int arr[], int n);
void buildMaxHeap(int arr[], int n);
void heapInsert(int arr[], int *size, int value, int isMinHeap);
void heapDelete(int arr[], int *size, int isMinHeap);
void displayHeap(int arr[], int size);
int main(){
int minHeap[MAXSIZE]={0};
int maxHeap[MAXSIZE]={0};
int minSize=0, maxSize=0;
int choice,value,isMinHeap;
clrscr();
while(1){
printf("\nMenu:\n");
printf("\n1.Insert into min Heap\n2.Insert into max Heap\n3.Delete from Min
Heap\n4.Delete from max Heap\n5.Display Min Heap\n6.Display max Heap\
n7.Exit\n");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1:printf("Enter the value to insert into Min Heap: \n");
scanf("%d",&value);
heapInsert(minHeap,&minSize,value,1);
printf("Inserted %d into min Heap\n",value);
break;
case 2:printf("Enter the value to insert into Max Heap: \n");
scanf("%d",&value);
heapInsert(maxHeap,&maxSize,value,0);
printf("Inserted %d into Max Heap\n",value);
break;
case 3:if(minSize>0){
heapDelete(minHeap,&minSize,1);
printf("Deleted root node from Min Heap\n");
}
else{
printf("Min Heap is Empty\n");
}break;
case 4:if(maxSize>0){
heapDelete(maxHeap,&maxSize,0);
printf("Deleted root node from Max Heap\n");
}else
printf("Max Heap is empty\n");
break;
case 5:printf("Min Heap:\n");
displayHeap(minHeap,minSize);
break;
case 6:printf("Max Heap:\n");
displayHeap(maxHeap,maxSize);
break;
case 7:printf("Exiting...\n");
return 0;
default:printf("Invalid choice, Enter a valid chocie\n");
}
}
return 0;
}
void swap(int *x, int *y){
int temp=*x;
*x=*y;
*y=temp;
}
void minHeapify(int arr[], int n, int i){
int small=i;
int l=2*i+1;
int r=2*i+2;
if(l<n && arr[l]<arr[small])
small=l;
if(r<n && arr[r]<arr[small])
small=r;
if(small!=i)
{
swap(&arr[i],&arr[small]);
minHeapify(arr,n,small);
}
}
void maxHeapify(int arr[],int n, int i){
int large=i;
int l=2*i+1;
int r=2*i+2;
if(large<n && arr[l]>arr[large])
large=l;
if(large<n && arr[r]>arr[large])
large=r;
if(large!=i){
swap(&arr[i],&arr[large]);
maxHeapify(arr,n,large);
}
}
void buildMinHeap(int arr[], int n){
int i;
for(i=(n/2)-1;i>=0;i--)
minHeapify(arr,n,i);
}
void buildMaxHeap(int arr[], int n){
int i;
for(i=(n/2)-1;i>=0;i--)
maxHeapify(arr,n,i);
}
void heapInsert(int arr[], int *size, int value, int isMinHeap){
int i;
if(*size==MAXSIZE){
printf("Heap Overflow\n");
return;
}
arr[(*size)++]=value;
i=*size-1;
if(isMinHeap){
while(i!=0 && arr[(i-1)/2]>arr[i]){
swap(&arr[i],&arr[(i-1)/2]);
i=(i-1)/2;
}
}else{
while(i!=0 && arr[(i-1)/2]<arr[i])
swap(&arr[i],&arr[(i-1)/2]);
i=(i-1)/2;
}
}

void heapDelete(int arr[], int *size, int isMinHeap){

if(*size<=0){
printf("Heap Underflow\n");
return;
}
arr[0]=arr[--(*size)];
if(isMinHeap)
minHeapify(arr,*size,0);
else
maxHeapify(arr,*size,0);
}
void displayHeap(int arr[], int size){
int i;
for(i=0;i<size;i++)
printf("%d ",arr[i]);
printf("\n");
}
OUTPUT:
Menu:
1.Insert into min Heap
2.Insert into max Heap
3.Delete from Min Heap
4.Delete from max Heap
5.Display Min Heap
6.Display max Heap
7.Exit
Enter your choice: 1
Enter the value to insert into Min Heap:
10
Inserted 10 into min Heap

Menu:

1.Insert into min Heap

2.Insert into max Heap
3.Delete from Min Heap
4.Delete from max Heap
5.Display Min Heap
6.Display max Heap
7.Exit
Enter your choice: 1
Enter the value to insert into Min Heap:
5
Inserted 5 into min Heap

Menu:

1.Insert into min Heap

2.Insert into max Heap
3.Delete from Min Heap
4.Delete from max Heap
5.Display Min Heap
6.Display max Heap
7.Exit
Enter your choice: 1
Enter the value to insert into Min Heap:
2
Inserted 2 into min Heap

Menu:
1.Insert into min Heap
2.Insert into max Heap
3.Delete from Min Heap
4.Delete from max Heap
5.Display Min Heap
6.Display max Heap
7.Exit
Enter your choice: 5
Min Heap:
2 10 5

Menu:

1.Insert into min Heap

2.Insert into max Heap
3.Delete from Min Heap
4.Delete from max Heap
5.Display Min Heap
6.Display max Heap
7.Exit
Enter your choice: 3
Deleted root node from Min Heap

Menu:

1.Insert into min Heap

2.Insert into max Heap
3.Delete from Min Heap
4.Delete from max Heap
5.Display Min Heap
6.Display max Heap
7.Exit
Enter your choice: 2
Enter the value to insert into Max Heap:
34
Inserted 34 into Max Heap

Menu:

1.Insert into min Heap

2.Insert into max Heap
3.Delete from Min Heap
4.Delete from max Heap
5.Display Min Heap
6.Display max Heap
7.Exit
Enter your choice: 2
Enter the value to insert into Max Heap:
54
Inserted 54 into Max Heap

Menu:

1.Insert into min Heap

2.Insert into max Heap
3.Delete from Min Heap
4.Delete from max Heap
5.Display Min Heap
6.Display max Heap
7.Exit
Enter your choice: 2
Enter the value to insert into Max Heap:
20
Inserted 20 into Max Heap

Menu:

1.Insert into min Heap

2.Insert into max Heap
3.Delete from Min Heap
4.Delete from max Heap
5.Display Min Heap
6.Display max Heap
7.Exit
Enter your choice: 6
Max Heap:
54 34 20

Menu:

1.Insert into min Heap

2.Insert into max Heap
3.Delete from Min Heap
4.Delete from max Heap
5.Display Min Heap
6.Display max Heap
7.Exit
Enter your choice: 4
Deleted root node from Max Heap

Menu:

1.Insert into min Heap

2.Insert into max Heap
3.Delete from Min Heap
4.Delete from max Heap
5.Display Min Heap
6.Display max Heap
7.Exit
Enter your choice: 7
Exiting...
 4(a).BFT & DFT USING ADJACENCY MATRIX

#include <stdio.h>
#define Max 5
void bfs(int adj[][Max], int visited[], int start);
void dfs(int adj[][Max], int visited[], int start);
int main() {
int visited[Max] = {0};
int adj[Max][Max], i, j;
int option;
clrscr();
do {
printf("\n*** Main Menu ***");
printf("\n1. Enter values in graph");
printf("\n2. BFS traversal");
printf("\n3. DFS traversal");
printf("\n4. Exit");
printf("\n\nEnter your option: ");
scanf("%d", &option);
switch (option) {
case 1:
printf("Enter the adjacency matrix:\n");
for (i = 0; i < Max; i++) {
for (j = 0; j < Max; j++) {
scanf("%d", &adj[i][j]);
}
}
break;
case 2:
printf("BFS traversal:\n");
for (i = 0; i < Max; i++) visited[i] = 0;
bfs(adj, visited, 0);
printf("\n");
break;
case 3:
printf("DFS traversal:\n");
for (i = 0; i < Max; i++) visited[i] = 0;
dfs(adj, visited, 0);
printf("\n");
break;
}
} while (option != 4);
return 0;
}
void bfs(int adj[][Max], int visited[], int start) {
int queue[Max], rear = -1, front = -1, i;
int k;
for (k = 0; k < Max; k++) visited[k] = 0;
queue[++rear] = start;
++front;
visited[start] = 1;
while (rear >= front) {
start = queue[front++];
printf("%c ", start + 65);
for (i = 0; i < Max; i++) {
if (adj[start][i] && visited[i] == 0) {
queue[++rear] = i;
visited[i] = 1;
}
}
}
}
void dfs(int adj[][Max], int visited[], int start) {
int stack[Max], top = -1, i;
int k;
for (k = 0; k < Max; k++) visited[k] = 0;
stack[++top] = start;
visited[start] = 1;
while (top != -1) {
start = stack[top--];
printf("%c ", start + 65);
for (i = 0; i < Max; i++) {
if (adj[start][i] && visited[i] == 0) {
stack[++top] = i;
visited[i] = 1;
}
}
}
}
OUTPUT:

Enter the adjacency matrix:

11110
11101
11011
10111
01111

*** Main Menu ***

1. Enter values in graph
2. BFS traversal
3. DFS traversal
4. Exit

Enter your option: 2

BFS traversal:
ABCDE

*** Main Menu ***

1. Enter values in graph
2. BFS traversal
3. DFS traversal
4. Exit

Enter your option:3

DFS traversal:
ADECB

*** Main Menu ***

1. Enter values in graph
2. BFS traversal
3. DFS traversal
4. Exit

Enter your option: 4

 4(b).BFT USING ADJACENCY LIST

#include <stdio.h>
#include <stdlib.h>
struct node
{int vertex;
struct node* next;
};
struct adj_list {
struct node* head;
};
struct graph {
int num_vertices;
struct adj_list* adj_lists;
int* visited;
};
struct node* new_node(int vertex) {
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->vertex = vertex;
new_node->next = NULL;
return new_node;
}
struct graph* create_graph(int n) {
int i;
struct graph* graph = (struct graph*)malloc(sizeof(struct graph));
graph->num_vertices = n;
graph->adj_lists = (struct adj_list*)malloc(n * sizeof(struct adj_list));
graph->visited = (int*)malloc(n * sizeof(int));
for (i = 0; i< n; i++) {
graph->adj_lists[i].head = NULL;
graph->visited[i] = 0;
}
return graph;
}
void add_edge(struct graph* graph, int src, int dest) {
struct node* new_node1 = new_node(dest);
struct node* new_node2 = new_node(src);
new_node1->next = graph->adj_lists[src].head;
graph->adj_lists[src].head = new_node1;
new_node2->next = graph->adj_lists[dest].head;
graph->adj_lists[dest].head = new_node2;
}
void bfs(struct graph* graph, int v) {
int queue[1000];
int front = -1;
int rear = -1;
graph->visited[v] = 1;
queue[++rear] = v;
while (front != rear) {
int current_vertex = queue[++front];
struct node* temp = graph->adj_lists[current_vertex].head;
printf("%d ", current_vertex);
while (temp != NULL) {
int adj_vertex = temp->vertex;
if (graph->visited[adj_vertex] == 0) {
graph->visited[adj_vertex] = 1;
queue[++rear] = adj_vertex;
}

temp = temp->next;
}
}
}

int main() {
struct graph*graph=create_graph(6);
clrscr();
add_edge(graph, 0,1);
add_edge(graph, 0, 2);
add_edge(graph, 1, 3);
add_edge(graph, 1, 4);
add_edge(graph, 2, 4);
add_edge(graph, 3, 4);
add_edge(graph, 3, 5);
add_edge(graph, 4,5);
printf("BFS traversal starting from vertex 0: ");
bfs(graph, 0);
getch();
}
OUTPUT:

BFS traversal starting from vertex 0:

021435
 5. BI-CONNECTED COMPONENT

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 100
typedef int bool;
#define true 1
#define false 0
typedef struct{
int u,v;
}edge;
int time=0;
int disc[MAX],low[MAX],parent[MAX];
int visited[MAX];
edge stack[MAX];
int top=-1;
void initgraph(int v, bool graph[MAX][MAX]){
int i,j;
for(i=0;i<v;i++){
for(j=0;j<v;j++){
graph[i][j]=false;
}
}
}
void addedge(bool graph[MAX][MAX],int u,int v)
{
graph[u][v]=true;
graph[v][u]=false;
}
void printbcc(int u,int v){
printf("\nBCC:");
while(true){
edge edge1=stack[top--];
if(edge1.u==u && edge1.v==v)
{
printf("%d-%d",u,v);
break;
}
printf("%d-%d",edge1.u,edge1.v);
}
printf("\n");
}
void bccdfs(bool graph[MAX][MAX],int u)
{
int children=0,v;
edge newedge;
visited[u]=true;
disc[u]=low[u]=++time;
for(v=0;v<MAX;++v)
{
if(graph[u][v])
{
if(!visited[v])
{
++children;
parent[v]=u;
newedge.u=u;
newedge.v=v;
stack[++top]=newedge;
bccdfs(graph,v);
low[u]=(low[u]<low[v])?low[u]:low[v];
if((parent[u]==-1 && children>1) || (parent[u]!=-1 && low[v]>=disc[u]))
{
printbcc(u,v);
}
}else if(v!=parent[u] && disc[u]>disc[v])
{
stack[++top]=newedge;
low[u]=((low[u]<disc[v])?low[u]:disc[v]);
}
}
}
}
void findbcc(bool graph[MAX][MAX], int v){
int i;
for(i=0;i<v;i++)
{
disc[i]=low[i]-1;
visited[i]=false;
parent[i]=-1;
}
for(i=0;i<v;i++)
{
if(!visited[i])
{
bccdfs(graph,i);
}
}
}
int main()
{
int v,e,i;
bool graph[MAX][MAX];
clrscr();
printf("\nEnter no.of vertices:");
scanf("%d",&v);
printf("\nEnter no.of edges: ");
scanf("%d",&e);
initgraph(v,graph);
printf("\nEnter edges(u,v):\n");
for(i=0;i<e;++i)
{
int u,v;
scanf("%d%d",&u,&v);
addedge(graph,u,v);
}
printf("\nBi-connected components in graph:\n");
findbcc(graph,v);
getch();
return 0;
}
OUTPUT:

Enter no.of vertices:2

Enter no.of edges: 2

Enter edges(u,v):
12
23

Bi-connected components in graph:

BCC:2-3

6(a) . QUICK SORT

#include<stdio.h>
#include<stdlib.h>
void quicksort(int num[25],int first,int last){
int i,j,pivot,temp;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(num[i]<=num[pivot]&&i<last)
i++;
while(num[j]>num[pivot])
j--;
if(i<j){
temp=num[i];
num[i]=num[j];
num[j]=temp;
}}
temp=num[pivot];
num[pivot]=num[j];
num[j]=temp;
quicksort(num,first,j-1);
quicksort(num,j+1,last);
}
}
int main(){
int i,count,num[25];
clrscr();
printf("how many elements are u going to enter ? :");
scanf("%d",&count);
printf("enter elements :");
for(i=0;i<count;i++) {
scanf("%d",&num[i]);
}
quicksort(num,0,count-1);
printf("Sorted order: ");
for(i=0;i<count;i++)
printf("%d ",num[i]);
return 0;
}
OUTPUT :

how many elements are u going to enter ? :5

enter elements :6 4 7 3 2
Sorted order:2 3 4 6 7

6(b). MERGE SORT

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void merge(int arr[],int left,int mid,int right){
int i,j,k;
int size1=mid-left+1;
int size2=right-mid;
int Left[100],Right[100];
for(i=0;i<size1;i++)
Left[i]=arr[left+i];
for(j=0;j<size2;j++)
Right[j]=arr[mid+1+j];
i=0;
j=0;
k=left;
while((i<size1) && (j<size2)){
if(Left[i]<=Right[j]){
arr[k]=Left[i];
i++;
}
else{
arr[k]=Right[j];
j++;
}
k++;
}
while(i<size1){
arr[k]=Left[i];
i++;
k++;
}
while(j<size2){
arr[k]=Right[j];
j++;
k++;
}
}
void merge_sort(int arr[],int left,int right){
if(left<right){
int mid=left+(right-left)/2;
merge_sort(arr,left,mid);
merge_sort(arr,mid+1,right);
merge(arr,left,mid,right);
}
}
int main(){
int size,i,arr[100];
printf("enter the size: ");
scanf("%d",&size);
printf("enter the elements of array :") ;
for(i=0;i<size;i++){
scanf("%d",&arr[i]);
}
merge_sort(arr,0,size-1);
printf("the sorted array is :");
for(i=0;i<size;i++){
printf("%d ",arr[i]);
}
printf("\n");
return 0;
}

OUTPUT :

enter the size: 5

enter the elements of array : 5 4 3 2 1
the sorted array is :1 2 3 4 5
 7. SINGLE SOURCE SHORTEST PATH USING
GREEDY METHOD
#include <stdio.h>

// defining some constants

#define INF 9999
#define MAX 10

// prototyping of the function

void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start);

// defining the function for Dijkstra's Algorithm

void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start) {
int cost[MAX][MAX], distance[MAX], previous[MAX];
int visited_nodes[MAX], counter, minimum_distance, next_node, i, j;

// creating cost matrix

for (i = 0; i < size; i++)
for (j = 0; j < size; j++)
if (Graph[i][j] == 0)
cost[i][j] = INF;
else
cost[i][j] = Graph[i][j];

for (i = 0; i < size; i++) {

distance[i] = cost[start][i];
previous[i] = start;
visited_nodes[i] = 0;
}

distance[start] = 0;
visited_nodes[start] = 1;
counter = 1;

while (counter < size - 1) {

minimum_distance = INF;

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

if (distance[i] < minimum_distance && !visited_nodes[i]) {
minimum_distance = distance[i];
next_node = i;
}

visited_nodes[next_node] = 1;
for (i = 0; i < size; i++)
if (!visited_nodes[i])
if (minimum_distance + cost[next_node][i] < distance[i]) {
distance[i] = minimum_distance + cost[next_node][i];
previous[i] = next_node;
}
counter++;
}

// printing the distance

for (i = 0; i < size; i++)
if (i != start) {
printf("\nDistance from the Source Node to %d: %d", i, distance[i]);
}
}

// main function
int main() {
// defining variables
int Graph[MAX][MAX], i, j, size, source;
// declaring the size of the matrix
size = 7;

// declaring the nodes of graph

Graph[0][0] = 0;
Graph[0][1] = 4;
Graph[0][2] = 0;
Graph[0][3] = 0;
Graph[0][4] = 0;
Graph[0][5] = 8;
Graph[0][6] = 0;

Graph[1][0] = 4;
Graph[1][1] = 0;
Graph[1][2] = 8;
Graph[1][3] = 0;
Graph[1][4] = 0;
Graph[1][5] = 11;
Graph[1][6] = 0;

Graph[2][0] = 0;
Graph[2][1] = 8;
Graph[2][2] = 0;
Graph[2][3] = 7;
Graph[2][4] = 0;
Graph[2][5] = 4;
Graph[2][6] = 0;
Graph[3][0] = 0;
Graph[3][1] = 0;
Graph[3][2] = 7;
Graph[3][3] = 0;
Graph[3][4] = 9;
Graph[3][5] = 14;
Graph[3][6] = 0;

Graph[4][0] = 0;
Graph[4][1] = 0;
Graph[4][2] = 0;
Graph[4][3] = 9;
Graph[4][4] = 0;
Graph[4][5] = 10;
Graph[4][6] = 2;

Graph[5][0] = 0;
Graph[5][1] = 0;
Graph[5][2] = 4;
Graph[5][3] = 14;
Graph[5][4] = 10;
Graph[5][5] = 0;
Graph[5][6] = 2;
Graph[6][0] = 0;
Graph[6][1] = 0;
Graph[6][2] = 0;
Graph[6][3] = 0;
Graph[6][4] = 2;
Graph[6][5] = 0;
Graph[6][6] = 1;

source = 0;
DijkstraAlgorithm(Graph, size, source);
return 0;
}
OUTPUT:
Distance from the Source Node to 1: 4

Distance from the Source Node to 2: 12

Distance from the Source Node to 3: 19

Distance from the Source Node to 4: 12

Distance from the Source Node to 5: 8

Distance from the Source Node to 6: 10

 8. IMPLEMENT JOB SEQUENCING WITH
DEADLINES USING GREEDY STRATEGY.

#include <stdio.h>
#include <stdlib.h>

// A structure to represent a job

typedef struct Job {
char id; // Job Id
int dead; // Deadline of job
int profit; // Profit if job is over before or on deadline
} Job;

// This function is used for sorting all jobs according to profit

int compare(const void* a, const void* b) {
Job* temp1 = (Job*)a;
Job* temp2 = (Job*)b;
return (temp2->profit - temp1->profit);
}

// Find minimum between two numbers.

int num1,num2;
int min( num1, num2) {
return (num1 > num2) ? num2 : num1;
}

// Returns maximum profit from jobs

void printJobScheduling(Job arr[], int n) {
// Sort all jobs according to decreasing order of profit
qsort(arr, n, sizeof(Job), compare);

int result[n]; // To store result (Sequence of jobs)

int slot[n]; // To keep track of free time slots

// Initialize all slots to be free

for (int i = 0; i < n; i++)
slot[i] = 0;

// Iterate through all given jobs

for (int i = 0; i < n; i++) {
// Find a free slot for this job (Note that we start from the last possible slot)
for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) {
// Free slot found
if (slot[j] == 0) {
result[j] = i; // Add this job to result
slot[j] = 1; // Make this slot occupied
break;
}
}
}

// Print the result

for (int i = 0; i < n; i++)
if (slot[i])
printf("%c ", arr[result[i]].id);
}

// Driver's code
int main() {
Job arr[] = { { 'a', 2, 100 },
{ 'b', 1, 19 },
{ 'c', 2, 27 },
{ 'd', 1, 25 },
{ 'e', 3, 15 } };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Following is maximum profit sequence of jobs \n");

// Function call
printJobScheduling(arr, n);
return 0;
}
OUTPUT:
Following is maximum profit sequence of jobs

cae
 9. 0\1 KNAPSACK PROBLEM USING DYNAMIC
PROGRAMMING

#include <stdio.h>
#include<conio.h>
int max(int a, int b) { return (a > b) ? a : b; }
// put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
if (n == 0 || W == 0)
return 0;
// If weight of the nth item is more than
// Knapsack capacity W, then this item cannot
// be included in the optimal solution
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);
// Return the maximum of two cases:
// (1) nth item included
// (2) not included
else
return max(
val[n - 1]
+ knapSack(W - wt[n - 1], wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}

// Driver code
void main()
{
int profit[] = { 60, 100, 120 };
int weight[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(profit) / sizeof(profit[0]);
clrscr();
printf("Final Profit=%d", knapSack(W, weight, profit, n));
getch();
}
OUTPUT:

Total Profit=220
 10. PROGRAM FOR N QUEEN PROBLEM USING
BACKTRACKING

#define N 4

#include <stdio.h>

void printSolution(int board[N][N])

int i,j;

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

for (j = 0; j < N; j++) {

if(board[i][j])

printf("Q ");

else

printf(". ");

printf("\n");

int isSafe(int board[N][N], int row, int col)

int i, j;

// Check this row on left side

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

if (board[row][i])

return 0;

// Check upper diagonal on left side

for (i = row, j = col; i >= 0 && j >= 0; i--, j--)

if (board[i][j])

return 0;

// Check lower diagonal on left side

for (i = row, j = col; j >= 0 && i < N; i++, j--)

if (board[i][j])

return 0;

return 1;

// A recursive utility function to solve N

// Queen problem

int solveNQUtil(int board[N][N], int col)

int i;

if (col >= N)

return 1;

// Consider this column and try placing

// this queen in all rows one by one

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

// Check if the queen can be placed on

// board[i][col]

if (isSafe(board, i, col)) {

// Place this queen in board[i][col]

board[i][col] = 1;

// Recur to place rest of the queens

if (solveNQUtil(board, col + 1))

return 1;

// If placing queen in board[i][col]

// doesn't lead to a solution, then

// remove queen from board[i][col]

board[i][col] = 0; // BACKTRACK

// If the queen cannot be placed in any row in

// this column col then return false

return 0;

int solveNQ()

int board[N][N] = { { 0, 0, 0, 0 },

{ 0, 0, 0, 0 },

{ 0, 0, 0, 0 },

{ 0, 0, 0, 0 } };

if (solveNQUtil(board, 0) == 0) {
printf("Solution does not exist");

return 0;

printSolution(board);

return 1;

void main()

clrscr();

solveNQ();

getch();

}
OUTPUT:

..Q.
Q...
...Q
.Q..
 11.KNAPSACK PROBLEM USING BACKTRACKING
/* Variable Description….
n – Total no. of items available
w[] – Weight of each item
p[] – Profit of each item
m – Maximum Capacity of the Sack
unit[] – Profit of each item per Unit p[]/w[]
x[] – Final list of items put into the Sack
y[] – Intermediate list of selected items
fp – Final Profit
fw – Final Weight
cp – Current Profit
cw – Current Weight
*/
#include <stdio.h>
#include <conio.h>
#define max 10
int w[max],i,j,p[max];
int n,m;
float unit[max];
int y[max],x[max],fp=-1,fw;
void get()
{
printf(“\n Enter total number of items: “);
scanf(“%d”,&n);
printf(“\n Enter the Maximum capacity of the Sack: “);
scanf(“%d”,&m);
for(i=0;i<n;i++)
{
printf(“\n Enter the weight of the item # %d : “,i+1);
scanf(“%d”,&w[i]);
printf(“\n Enter the profit of the item # %d : “, i+1);
scanf(“%d”, &p[i]);
}
}
void show()
{
float s=0.0;
printf(“\n\tItem\tWeight\tCost\tUnit Profit\tSelected “);
for(i=0;i<n;i++)
printf(“\n\t%d\t%d\t%d\t%f\t%d”,i+1,w[i],p[i],unit[i],x[i]);
printf(“\n\n The Sack now holds following items : “);
for(i=0;i<n;i++)
if(x[i]==1)
{
printf(“%d\t”,i+1);
s += (float) p[i] * (float) x[i];
}
printf(“\n Maximum Profit: %f “,s);
}
/*Arrange the item based on high profit per Unit*/
void sort()
{
int t,t1;
float t2;
for(i=0;i<n;i++)
unit[i] = (float) p[i] / (float) w[i];
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(unit[i] < unit[j])
{
t2 = unit[i];
unit[i] = unit[j];
unit[j] = t2;
t = p[i];
p[i] = p[j];
p[j] = t;
t1 = w[i];
w[i] = w[j];
w[j] =t1;
}
}
}
}
float bound(float cp,float cw,int k)
{
float b = cp;
float c = cw;
for(i=k;i<=n;i++)
{
c = c+w[i];
if( c < m)
b = b +p[i];
else
return (b+(1-(c-m)/ (float)w[i])*p[i]);
}
return b;
}
void knapsack(int k,float cp,float cw)
{
if(cw+w[k] <= m)
{
y[k] = 1;
if(k <= n)
knapsack(k+1,cp+p[k],cw+w[k]);
if(((cp+p[k]) > fp) && ( k == n))
{
fp = cp+p[k];
fw = cw+w[k];
for(j=0;j<=k;j++)
x[j] = y[j];
}
}
if(bound(cp,cw,k) >= fp)
{
y[k] = 0;
if( k <= n)
knapsack(k+1,cp,cw);
if((cp > fp) && (k == n))
{
fp = cp;
fw = cw;
for(j=0;j<=k;j++)
x[j] = y[j];
}
}
}
void main()
{
clrscr();
printf(“\n\n\n\t\t ******** KNAPSACK PROBLEM ********”);
printf(“\n\t\t —————————————–“);
get();
printf(“\n The Sack is arranged in the order…\n”);
sort();
knapsack(0,0.0,0.0);
show();
getch();
}
OUTPUT:
******** KNAPSACK PROBLEM ********
——————————————-
Enter total number of items: 3
Enter the Maximum capacity of the Sack: 25
Enter the weight of the item # 1 : 1
Enter the profit of the item # 1 : 11
Enter the weight of the item # 2 : 11
Enter the profit of the item # 2 : 21
Enter the weight of the item # 3 : 21
Enter the profit of the item # 3 : 31
The Sack is arranged in the order…
Item Weight Cost Unit Profit Selected
1 1 11 11.000000 1
2 11 21 1.909091 0
3 21 31 1.476190 1
The Sack now holds following items : 1 3
Maximum Profit: 42.000000
 12.BRANCH AND BOUND ALGORITHM FOR
TRAVELLING SALES PERSON

#include<stdio.h>
#include<conio.h>
int a[10][10], visited[10], n, cost = 0;
void get() {
int i, j;
printf("Enter No. of Cities: ");
scanf("%d", &n);
printf("\nEnter Cost Matrix: \n");
for (i = 0; i < n; i++) {
printf("\n Enter Elements of Row# : %d\n", i + 1);
for (j = 0; j < n; j++)
scanf("%d", &a[i][j]);
visited[i] = 0;
}
printf("\n\nThe cost list is:\n\n");
for (i = 0; i < n; i++) {
printf("\n\n");
for (j = 0; j < n; j++)
printf("\t % d", a[i][j]);
}}
void mincost(int city) {
int i, ncity;
visited[city] = 1;
printf("%d ->", city + 1);
ncity = least(city);
if (ncity == 999) {
ncity = 0;
printf("%d", ncity + 1);
cost += a[city][ncity];
return;
}
mincost(ncity);
}
int least(int c) {
int i, nc = 999;
int min = 999, kmin;
for (i = 0; i < n; i++) {
if ((a[c][i] != 0) && (visited[i] == 0))
if (a[c][i] < min) {
min = a[i][0] + a[c][i];
kmin = a[c][i];
nc = i;
}}
if (min != 999)
cost += kmin;
return nc;
}
void put() {
printf("\n\nMinimum cost:");
printf("%d", cost);
}
void main() {
clrscr();
get();
printf("\n\nThe Path is:\n\n");
mincost(0);
put();
getch();
}
OUTPUT:

Enter No. of Cities: 6

Enter Cost Matrix:

99 10 15 20 99 8

5 99 9 10 8 99

6 13 99 12 99 5

8 8 9 99 6 99

99 10 99 6 99 99

10 99 5 99 99 99

Enter Elements of Row# : 1

Enter Elements of Row# : 2

Enter Elements of Row# : 3

Enter Elements of Row# : 4

Enter Elements of Row# : 5

Enter Elements of Row# : 6

The Path is:

1 –>6 –>3 –>4 –>5 –>2 –>1

Minimum cost:46
CONTENT BEYOND
SYLLABUS
 13(a).HEAPSORT
#include <stdio.h>

#include<conio.h>

void heapify(int arr[], int n, int i)

int temp, maximum, left_index, right_index;

maximum = i;

right_index = 2 * i + 2;

left_index = 2 * i + 1;

if (left_index < n && arr[left_index] > arr[maximum])

maximum = left_index;

if (right_index < n && arr[right_index] > arr[maximum])

maximum = right_index;

if (maximum != i) {

temp = arr[i];

arr[i] = arr[maximum];

arr[maximum] = temp;

heapify(arr, n, maximum);

}}

void heapsort(int arr[], int n)

int i, temp;

for (i = n / 2 - 1; i >= 0; i--) {

heapify(arr, n, i);
}

for (i = n - 1; i > 0; i--) {

temp = arr[0];

arr[0] = arr[i];

arr[i] = temp;

heapify(arr, i, 0);

}}

void main()

int i,n=6,j,arr[]={7,8,34,2,90,5};

clrscr();

printf("Original Array : ");

for ( i = 0; i < n; i++) {

printf("%d ", arr[i]);

printf("\nAFTER HEAPSORT\n");

heapsort(arr, n);

printf("Array after performing heap sort: ");

for ( i = 0; i < n; i++) {

printf("%d ", arr[i]);

getch();

}
OUTPUT:
 13(b).PRIM`S ALGORITH USING MINIMUM COST
SPANNING TREE

#include <stdio.h>

#include <limits.h>

#include<conio.h>

#define vertices 5

int minimum_key(int k[], int mst[])

int minimum = INT_MAX, min,i;

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

if (mst[i] == 0 && k[i] < minimum )

minimum = k[i], min = i;

return min;

void prim(int g[vertices][vertices])

int parent[vertices];

int k[vertices];

int mst[vertices];

int i, count,edge,v; /*Here 'v' is the vertex*/

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

k[i] = INT_MAX;
mst[i] = 0;

k[0] = 0;

parent[0] = -1;

for (count = 0; count < vertices-1; count++)

edge = minimum_key(k, mst);

mst[edge] = 1;

for (v = 0; v < vertices; v++)

if (g[edge][v] && mst[v] == 0 && g[edge][v] < k[v])

parent[v] = edge, k[v] = g[edge][v];

printf("\n Edge \t Weight\n");

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

printf(" %d <-> %d %d \n", parent[i], i, g[i][parent[i]]);

void main()

int g[vertices][vertices] = {{0, 0, 3, 0, 0},

{0, 0, 10, 4, 0},

{3, 10, 0, 2, 6},

{0, 4, 2, 0, 1},

{0, 0, 6, 1, 0},

};

clrscr();

printf("\n\nPRIM`S ALGORITH USING MINIMUM COST SPANNING

TREE\n");

prim(g);

getch();

}
OUTPUT:
 13(c).IMPLEMENTATION OF KRUSKAL'S
ALGORITHM

#include <conio.h>

#include <stdlib.h>

int i, j, k, a, b, u, v, n, ne = 1;

int min, mincost = 0, cost[9][9], parent[9];

int find(int);

int uni(int, int);

void main() {

clrscr();

printf("\n\tImplementation of Kruskal's Algorithm\n");

printf("\nEnter the no. of vertices:");

scanf("%d", & n);

printf("\nEnter the cost adjacency matrix:\n");

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

for (j = 1; j <= n; j++) {

scanf("%d", & cost[i][j]);

if (cost[i][j] == 0)

cost[i][j] = 999;

printf("The edges of Minimum Cost Spanning Tree are\n");

while (ne < n) {

for (i = 1, min = 999; i <= n; i++) {

for (j = 1; j <= n; j++) {

if (cost[i][j] < min) {

min = cost[i][j];

a = u = i;

b = v = j;

u = find(u);

v = find(v);

if (uni(u, v)) {

printf("%d edge (%d,%d) =%d\n", ne++, a, b, min);

mincost += min;

cost[a][b] = cost[b][a] = 999;

printf("\n\tMinimum cost = %d\n", mincost);

getch();

int find(int i) {

while (parent[i])

i = parent[i];

return i;
}

int uni(int i, int j) {

if (i != j) {

parent[j] = i;

return 1;

return 0;

}
OUTPUT: