15.

Write a program to soert given set of elements using the following sorting techniques

#include <stdio.h> / / Selection sort implementation

void selectionSort(int arr*+, int n) ,
for (int i = 0; i < n - 1; i++) ,
int min = i;
for (int j = i + 1; j < n; j++) ,
if (arr*j+ < arr*min+)
min = j;
-
if (min != i) ,
int temp = arr*min+;
arr*min+ = arr*i+;
arr*i+ = temp;
-
-
-
int main() ,
int arr*+ = , 2 ,6, 1, 5, 3, 4 -;
int n = sizeof(arr) / sizeof(arr*0+);
// Perform Selection Sort
selectionSort(arr,n);
for (int i = 0; i < n; i++)
printf("%d ", arr*i+);
return 0;
-
Output: 1 2 3 4 5 6
HEAP SORT
#include <stdio.h>
1. void swap(int* a, int* b) ,
2. int temp = *a;
3. *a = *b;
4. *b = temp;
5. -
6. void heapify(int arr*+, int n, int i) ,
7. int largest = i;
8. int left = 2 * i + 1;
9. int right = 2 * i + 2;
10. if (left < n && arr*left+ > arr*largest+)
11. largest = left;
12. if (right < n && arr*right+ > arr*largest+)
13. largest = right;
14. if (largest != i) ,
15. swap(&arr*i+, &arr*largest+);
16. heapify(arr, n, largest);
17. -
18. -
19. void heapSort(int arr*+, int n) ,
20. for (int i = n / 2 - 1; i >= 0; i--)
21. heapify(arr, n, i);
22. for (int i = n - 1; i > 0; i--) ,
23. swap(&arr*0+, &arr*i+);
24. heapify(arr, i, 0);
25. -
26. -
27. int main() ,
28. int arr*+ = ,64, 34, 25, 12, 22, 11, 90-;
29. int n = sizeof(arr) / sizeof(arr*0+);
30. heapSort(arr, n);
31. printf("Sorted array: ");
32. for (int i = 0; i < n; i++)
33. printf("%d ", arr*i+);
34. return 0;
35. -

8 i). write a program to search for an element given in an array using the linear search

#include <stdio.h>
int linearSearch(int arr*+, int size, int target) ,
// Iterate through the array elements
for (int i = 0; i < size; i++) ,
// Check if the current element matches the target
if (arr*i+ == target) ,
// If found, return the index
return i;
-
-
// If the loop finishes without finding the target, return -1
return -1;
-
int main() ,
int myArray*+ = ,2, 4, 0, 1, 9, 5, 8-;
int targetElement = 5;
// Calculate the size of the array
int arraySize = sizeof(myArray) / sizeof(myArray*0+);
// Call the linearSearch function
int resultIndex = linearSearch(myArray, arraySize, targetElement);
// Print the result
if (resultIndex != -1) ,
printf("Element %d found at index %d.\n", targetElement, resultIndex);
- else ,
printf("Element %d not found in the array.\n", targetElement);
-
// Example of a target not in the array
int nonExistentElement = 3;
resultIndex = linearSearch(myArray, arraySize, nonExistentElement);
if (resultIndex != -1) ,
printf("Element %d found at index %d.\n", nonExistentElement, resultIndex);
- else ,
printf("Element %d not found in the array.\n", nonExistentElement);
-
return 0;
-
 Output:
Element 5 found at index 5.
Element 3 not found in the array.

=== Code Execution Successful ===

8. ii) write a program to search for an element given in an array using the Binary search

#include <stdio.h>
int binarySearch(int arr*+, int n, int target) ,
int left = 0;
int right = n - 1;
while (left <= right) ,
// Calculate the middle index
int mid = left + (right - left) / 2;
// Check if the target is present at the middle
if (arr*mid+ == target) ,
return mid;
-
// If target is greater, ignore the left half
if (arr*mid+ < target) ,
left = mid + 1;
-
// If target is smaller, ignore the right half
else ,
right = mid - 1;
-
-
// Target was not found in the array
return -1;
-
int main() ,
// Example sorted array
int arr*+ = ,2, 5, 8, 12, 16, 23, 38, 56, 72, 91-;
// Calculate the number of elements in the array
int n = sizeof(arr) / sizeof(arr*0+);
int target = 23;
// Perform the binary search
int result = binarySearch(arr, n, target);
// Print the result
if (result != -1) ,
printf("Element %d found at index %d\n", target, result);
- else ,
printf("Element %d not found in the array\n", target);
-
// Another example for an element not present
target = 50;
result = binarySearch(arr, n, target);
if (result != -1) ,
printf("Element %d found at index %d\n", target, result);
- else ,
printf("Element %d not found in the array\n", target);
-
 return 0;
-

Output:
Element 23 found at index 5
Element 50 not found in the array

=== Code Execution Successful ===

9. write a program to build a hash table using linear probing and search for an given element
.

#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 10
// Structure for a single data item
struct DataItem ,
int data;
int key;
-;
// Array to hold the hash table
struct DataItem* hashArray*TABLE_SIZE+;
// A dummy item to mark deleted entries
struct DataItem* dummyItem;
// An item to represent an available (non-deleted) entry
struct DataItem* item;
// Hash function
int getHashCode(int key) ,
return key % TABLE_SIZE;
-
// Function to search for an item in the hash table
struct DataItem *search(int key) ,
// Get the hash
int hashIndex = getHashCode(key);
// Loop through the table until an empty slot is found or the item is found
while(hashArray*hashIndex+ != NULL) ,
if(hashArray*hashIndex+->key == key)
return hashArray*hashIndex+; // Item found
// Go to the next cell
++hashIndex;
// Wrap around the table
hashIndex %= TABLE_SIZE;
-
return NULL; // Item not found
-
// Function to insert an item into the hash table
void insert(int key, int data) ,
struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
item->data = data;
item->key = key;
// Get the hash
int hashIndex = getHashCode(key);
 // Loop until an empty or dummy cell is found
while(hashArray*hashIndex+ != NULL && hashArray*hashIndex+->key != -1) ,
// Go to the next cell
++hashIndex;
// Wrap around the table
hashIndex %= TABLE_SIZE;
-
hashArray*hashIndex+ = item;
-
// A utility function to display the hash table
void display() ,
int i = 0;
for(i = 0; i < TABLE_SIZE; i++) ,
if(hashArray*i+ != NULL)
printf(" Index %d: (eey: %d, Data: %d)\n", i, hashArray*i+->key, hashArray*i+->data);
else
printf(" Index %d: ~~ \n", i);
-
-
// Main function to demonstrate usage
int main() ,
dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem));
dummyItem->data = -1;
dummyItem->key = -1;
// Insert some items
insert(1, 20);
insert(2, 70);
insert(42, 80);
insert(4, 25);
insert(12, 44);
insert(14, 32);
insert(17, 11);
insert(13, 78);
insert(37, 97);
printf("Hash Table after insertions:\n");
display();
// Search for an existing element (key 37)
int searcheey = 37;
item = search(searcheey);
if(item != NULL) ,
printf("\nElement found: (eey: %d, Data: %d)\n", item->key, item->data);
- else ,
printf("\nElement not found for key %d\n", searcheey);
-
// Search for a non-existing element (key 100)
searcheey = 100;
item = search(searcheey);
if(item != NULL) ,
printf("Element found: (eey: %d, Data: %d)\n", item->key, item->data);
- else ,
printf("Element not found for key %d\n", searcheey);
-
return 0;
-
output:

Hash Table after insertions:

Index 0: ~~
Index 1: (eey: 1, Data: 20)
Index 2: (eey: 2, Data: 70)
Index 3: (eey: 42, Data: 80)
Index 4: (eey: 4, Data: 25)
Index 5: (eey: 12, Data: 44)
Index 6: (eey: 14, Data: 32)
Index 7: (eey: 17, Data: 11)
Index 8: (eey: 13, Data: 78)
Index 9: (eey: 37, Data: 97)

Element found: (eey: 37, Data: 97)

Element not found for key 100

=== Code Execution Successful ===

10. Write a program construct binary tree and implement display in order, pre order and
post order traversal

#include <stdio.h>
#include <stdlib.h>
// Definition of a binary tree node
struct Node ,
int data;
struct Node* left;
struct Node* right;
-;
// Function to create a new node
struct Node* createNode(int data) ,
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) ,
printf("Memory allocation failed\n");
exit(1);
-
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
-
// Function to perform inorder traversal (Left, Root, Right)
void inorderTraversal(struct Node* root) ,
if (root != NULL) ,
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
-
-
// Function to perform preorder traversal (Root, Left, Right)
void preorderTraversal(struct Node* root) ,
if (root != NULL) ,
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
-
-
// Function to perform postorder traversal (Left, Right, Root)
void postorderTraversal(struct Node* root) ,
if (root != NULL) ,
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->data);
-
-
// Main function to construct the tree and display traversals
int main() ,
// Construct the binary tree manually for demonstration
// 1
// / \
// 2 3
// / \
// 4 5
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);

printf("Inorder traversal: ");

inorderTraversal(root); // Expected output: 4 2 5 1 3
printf("\n");

printf("Preorder traversal: ");

preorderTraversal(root); // Expected output: 1 2 4 5 3
printf("\n");

printf("Postorder traversal: ");

postorderTraversal(root); // Expected output: 4 5 2 3 1
printf("\n");
// Free the allocated memory (optional for simple programs but good practice)
// A more robust function would traverse the entire tree to free all nodes.
// For this example, we skip a full recursive free for simplicity.

return 0;
-

Output:

Inorder traversal: 4 2 5 1 3
Preorder traversal: 1 2 4 5 3
Postorder traversal: 4 5 2 3 1

=== Code Execution Successful ===

11. Write a program construct binary tree and implement insertion, deletion and search
operation on it.

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

// Definition of a tree node

struct Node ,
int key;
struct Node *left, *right;
-;

// Function to create a new node

struct Node* createNode(int item) ,
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
if (temp == NULL) ,
printf("Memory allocation failed\n");
exit(1);
-
temp->key = item;
temp->left = temp->right = NULL;
return temp;
-

// Function to insert a new key in BST

struct Node* insert(struct Node* node, int key) ,
// If the tree is empty, return a new node
if (node == NULL) return createNode(key);

// Otherwise, recur down the tree

if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);

// Return the (unchanged) node pointer

return node;
-

// Function to search for a key in BST

struct Node* search(struct Node* root, int key) ,
// Base Cases: root is null or key is present at root
if (root == NULL || root->key == key)
return root;

// eey is greater than root's key

if (root->key < key)
return search(root->right, key);

// eey is smaller than root's key

return search(root->left, key);
-
// Function to find the minimum value node in a BST
struct Node* minValueNode(struct Node* node) ,
struct Node* current = node;

// Loop down to find the leftmost leaf

while (current && current->left != NULL)
current = current->left;

return current;
-

// Function to delete a key from BST

struct Node* deleteNode(struct Node* root, int key) ,
// Base case: tree is empty
if (root == NULL) return root;

// Recur down the tree to find the node to be deleted

if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
// If key is same as root's key, then this is the node to be deleted
else ,
// Node with only one child or no child
if (root->left == NULL) ,
struct Node *temp = root->right;
free(root);
return temp;
- else if (root->right == NULL) ,
struct Node *temp = root->left;
free(root);
return temp;
-

// Node with two children: Get the inorder successor (smallest in the right subtree)
struct Node* temp = minValueNode(root->right);

// Copy the inorder successor's content to this node

root->key = temp->key;

// Delete the inorder successor

root->right = deleteNode(root->right, temp->key);
-
return root;
-

// Function to print the tree in Inorder traversal (sorted order)

void inorder(struct Node* root) ,
if (root != NULL) ,
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
-
-
// Main function to test the operations
int main() ,
struct Node* root = NULL;

// Insertion
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);

printf("Inorder traversal of the given tree: ");

inorder(root);
printf("\n");

// Searching
int searcheey = 40;
struct Node* searchResult = search(root, searcheey);
if (searchResult != NULL) ,
printf("Found %d in the tree.\n", searcheey);
- else ,
printf("%d not found in the tree.\n", searcheey);
-

// Deletion
int deleteeey = 20;
printf("Deleting %d\n", deleteeey);
root = deleteNode(root, deleteeey);
printf("Inorder traversal after deleting %d: ", deleteeey);
inorder(root);
printf("\n");

deleteeey = 30;
printf("Deleting %d\n", deleteeey);
root = deleteNode(root, deleteeey);
printf("Inorder traversal after deleting %d: ", deleteeey);
inorder(root);
printf("\n");

deleteeey = 50;
printf("Deleting %d\n", deleteeey);
root = deleteNode(root, deleteeey);
printf("Inorder traversal after deleting %d: ", deleteeey);
inorder(root);
printf("\n");

return 0;
-
output:

Inorder traversal: 4 2 5 1 3
Preorder traversal: 1 2 4 5 3
Postorder traversal: 4 5 2 3 1

=== Code Execution Successful ===

_________________________________________________________________-

12. Write a program to construct a AVL tree and implement insertion deletion and search
operation on it.

AVL Tree Insertion

// C program to insert a node in AVL tree

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

// An AVL tree node

struct Node
,
int key;
struct Node *left;
struct Node *right;
int height;
-;

// A utility function to get the height of the tree

int height(struct Node *N)
,
if (N == NULL)
return 0;
return N->height;
-

// A utility function to get maximum of two integers

int max(int a, int b)
,
return (a > b)? a : b;
-

/* Helper function that allocates a new node with the given key and
NULL left and right pointers. */
struct Node* newNode(int key)
,
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return(node);
-
// A utility function to right rotate subtree rooted with y
// See the diagram given above.
struct Node *rightRotate(struct Node *y)
,
struct Node *x = y->left;
struct Node *T2 = x->right;

// Perform rotation
x->right = y;
y->left = T2;

// Update heights
y->height = max(height(y->left),
height(y->right)) + 1;
x->height = max(height(x->left),
height(x->right)) + 1;

// Return new root

return x;
-

// A utility function to left rotate subtree rooted with x

// See the diagram given above.
struct Node *leftRotate(struct Node *x)
,
struct Node *y = x->right;
struct Node *T2 = y->left;

// Perform rotation
y->left = x;
x->right = T2;

// Update heights
x->height = max(height(x->left),
height(x->right)) + 1;
y->height = max(height(y->left),
height(y->right)) + 1;

// Return new root

return y;
-

// Get Balance factor of node N

int getBalance(struct Node *N)
,
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
-

// Recursive function to insert a key in the subtree rooted

// with node and returns the new root of the subtree.
struct Node* insert(struct Node* node, int key)
,
/* 1. Perform the normal BST insertion */
if (node == NULL)
return(newNode(key));

if (key < node->key)

node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys are not allowed in BST
return node;

/* 2. Update height of this ancestor node */

node->height = 1 + max(height(node->left),
height(node->right));

/* 3. Get the balance factor of this ancestor

node to check whether this node became
unbalanced */
int balance = getBalance(node);

// If this node becomes unbalanced, then

// there are 4 cases

// Left Left Case

if (balance > 1 && key < node->left->key)
return rightRotate(node);

// Right Right Case

if (balance < -1 && key > node->right->key)
return leftRotate(node);

// Left Right Case

if (balance > 1 && key > node->left->key)
,
node->left = leftRotate(node->left);
return rightRotate(node);
-

// Right Left Case

if (balance < -1 && key < node->right->key)
,
node->right = rightRotate(node->right);
return leftRotate(node);
-

/* return the (unchanged) node pointer */

return node;
-

// A utility function to print preorder traversal

// of the tree.
// The function also prints height of every node
void preOrder(struct Node *root)
,
if(root != NULL)
,
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
-
-

/* Driver program to test above function*/

int main()
,
struct Node *root = NULL;

/* Constructing tree given in the above figure */

root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);

/* The constructed AVL Tree would be

30
/ \
20 40
/ \ \
10 25 50
*/

// Preorder traversal
preOrder(root);

return 0;
-

output
30 20 10 25 40 50

=== Code Execution Successful ===

AVL Tree Deletion

// C program to delete a node from AVL Tree
#include<stdio.h>
#include<stdlib.h>

// An AVL tree node

struct Node
,
int key;
struct Node *left;
struct Node *right;
int height;
-;
// A utility function to get maximum of two integers
int max(int a, int b);

// A utility function to get height of the tree

int height(struct Node *N)
,
if (N == NULL)
return 0;
return N->height;
-

// A utility function to get maximum of two integers

int max(int a, int b)
,
return (a > b)? a : b;
-

/* Helper function that allocates a new node with the given key and
NULL left and right pointers. */
struct Node* newNode(int key)
,
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return(node);
-

// A utility function to right rotate subtree rooted with y

// See the diagram given above.
struct Node *rightRotate(struct Node *y)
,
struct Node *x = y->left;
struct Node *T2 = x->right;

// Perform rotation
x->right = y;
y->left = T2;

// Update heights
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;

// Return new root

return x;
-

// A utility function to left rotate subtree rooted with x

// See the diagram given above.
struct Node *leftRotate(struct Node *x)
,
 struct Node *y = x->right;
struct Node *T2 = y->left;

// Perform rotation
y->left = x;
x->right = T2;

// Update heights
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;

// Return new root

return y;
-

// Get Balance factor of node N

int getBalance(struct Node *N)
,
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
-

struct Node* insert(struct Node* node, int key)

,
/* 1. Perform the normal BST rotation */
if (node == NULL)
return(newNode(key));

if (key < node->key)

node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys not allowed
return node;

/* 2. Update height of this ancestor node */

node->height = 1 + max(height(node->left),
height(node->right));

/* 3. Get the balance factor of this ancestor

node to check whether this node became
unbalanced */
int balance = getBalance(node);

// If this node becomes unbalanced, then there are 4 cases

// Left Left Case

if (balance > 1 && key < node->left->key)
return rightRotate(node);

// Right Right Case

if (balance < -1 && key > node->right->key)
return leftRotate(node);
 // Left Right Case
if (balance > 1 && key > node->left->key)
,
node->left = leftRotate(node->left);
return rightRotate(node);
-

// Right Left Case

if (balance < -1 && key < node->right->key)
,
node->right = rightRotate(node->right);
return leftRotate(node);
-

/* return the (unchanged) node pointer */

return node;
-

/* Given a non-empty binary search tree, return the

node with minimum key value found in that tree.
Note that the entire tree does not need to be
searched. */
struct Node * minValueNode(struct Node* node)
,
struct Node* current = node;

/* loop down to find the leftmost leaf */

while (current->left != NULL)
current = current->left;

return current;
-

// Recursive function to delete a node with given key

// from subtree with given root. It returns root of
// the modified subtree.
struct Node* deleteNode(struct Node* root, int key)
,
// STEP 1: PERFORM STANDARD BST DELETE

if (root == NULL)
return root;

// If the key to be deleted is smaller than the

// root's key, then it lies in left subtree
if ( key < root->key )
root->left = deleteNode(root->left, key);

// If the key to be deleted is greater than the

// root's key, then it lies in right subtree
else if( key > root->key )
root->right = deleteNode(root->right, key);
// if key is same as root's key, then This is
// the node to be deleted
else
,
// node with only one child or no child
if( (root->left == NULL) || (root->right == NULL) )
,
struct Node *temp = root->left ? root->left :
root->right;

// No child case
if (temp == NULL)
,
temp = root;
root = NULL;
-
else // One child case
*root = *temp; // Copy the contents of
// the non-empty child
free(temp);
-
else
,
// node with two children: Get the inorder
// successor (smallest in the right subtree)
struct Node* temp = minValueNode(root->right);

// Copy the inorder successor's data to this node

root->key = temp->key;

// Delete the inorder successor

root->right = deleteNode(root->right, temp->key);
-
-

// If the tree had only one node then return

if (root == NULL)
return root;

// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE

root->height = 1 + max(height(root->left),
height(root->right));

// STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to

// check whether this node became unbalanced)
int balance = getBalance(root);

// If this node becomes unbalanced, then there are 4 cases

// Left Left Case

if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);

// Left Right Case

 if (balance > 1 && getBalance(root->left) < 0)
,
root->left = leftRotate(root->left);
return rightRotate(root);
-

// Right Right Case

if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);

// Right Left Case

if (balance < -1 && getBalance(root->right) > 0)
,
root->right = rightRotate(root->right);
return leftRotate(root);
-

return root;
-

// A utility function to print preorder traversal of

// the tree.
// The function also prints height of every node
void preOrder(struct Node *root)
,
if(root != NULL)
,
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
-
-

/* Driver program to test above function*/

int main()
,
struct Node *root = NULL;

/* Constructing tree given in the above figure */

root = insert(root, 9);
root = insert(root, 5);
root = insert(root, 10);
root = insert(root, 0);
root = insert(root, 6);
root = insert(root, 11);
root = insert(root, -1);
root = insert(root, 1);
root = insert(root, 2);
 /* The constructed AVL Tree would be
9
/ \
1 10
/ \ \
0 5 11
/ / \
-1 2 6
*/

printf("Preorder traversal of the constructed AVL "

"tree is \n");
preOrder(root);

root = deleteNode(root, 10);

/* The AVL Tree after deletion of 10

1
/ \
0 9
/ / \
-1 5 11
/ \
2 6
*/

printf("\nPreorder traversal after deletion of 10 \n");

preOrder(root);

return 0;
-

output

Preorder traversal of the constructed AVL tree is

9 1 0 -1 5 2 6 10 11
Preorder traversal after deletion of 10
1 0 -1 9 5 2 6 11

=== Code Execution Successful ===

13 A. write a program to construct a graph and traverse using DFS

#include <stdio.h>
#define MAX 20

int adj*MAX+*MAX+, visited*MAX+;

int n; // Number of vertices

// Recursive DFS function

void DFS(int vertex) ,
int i;
visited*vertex+ = 1;
printf("%d ", vertex);

// Visit all adjacent unvisited vertices

for (i = 1; i <= n; i++) ,
if (adj*vertex+*i+ == 1 && visited*i+ == 0) ,
DFS(i);
-
-
-

int main() ,
int i, j, start;

printf("Enter number of vertices: ");

scanf("%d", &n);

// Construct adjacency matrix

printf("Enter adjacency matrix (1 for edge, 0 for no edge):\n");
for (i = 1; i <= n; i++) ,
for (j = 1; j <= n; j++) ,
printf("Edge %d->%d: ", i, j);
scanf("%d", &adj*i+*j+);
-
-

// Display adjacency matrix

printf("\nAdjacency Matrix:\n");
for (i = 1; i <= n; i++) ,
for (j = 1; j <= n; j++) ,
printf("%d ", adj*i+*j+);
-
printf("\n");
-

// Initialize visited array

for (i = 1; i <= n; i++) ,
visited*i+ = 0;
-

// Get starting vertex and perform DFS

printf("\nEnter starting vertex for DFS: ");
scanf("%d", &start);
 printf("DFS Traversal starting from %d: ", start);
DFS(start);
printf("\n");

return 0;
-

output

Enter number of vertices: 4

Enter adjacency matrix:
Edge 1->1: 0
Edge 1->2: 1
Edge 1->3: 1
Edge 1->4: 0
... (continue for all entries)

Adjacency Matrix:
0110
1001
1001
0110

Enter starting vertex for DFS: 1

DFS Traversal starting from 1: 1 2 4 3

13 B. Write a program to construct a graph and traverse using BFS

#include <stdio.h>
#define MAX 20

int adj*MAX+*MAX+, visited*MAX+;

int queue*MAX+, front = -1, rear = -1;
int n; // Number of vertices

// Queue functions for BFS

void enqueue(int vertex) ,
if (rear == MAX - 1) return;
if (front == -1) front = 0;
queue*++rear+ = vertex;
-

int dequeue() ,
if (front == -1 || front > rear) return -1;
return queue*front+++;
-

int isEmpty() ,
return front == -1 || front > rear;
-
void BFS(int start) ,
int vertex, i;

printf("%d ", start);

visited*start+ = 1;
enqueue(start);

while (!isEmpty()) ,
vertex = dequeue();
for (i = 1; i <= n; i++) ,
if (adj*vertex+*i+ == 1 && visited*i+ == 0) ,
printf("%d ", i);
visited*i+ = 1;
enqueue(i);
-
-
-
printf("\n");
-

int main() ,
int i, j, start;

printf("Enter number of vertices: ");

scanf("%d", &n);

// Construct adjacency matrix

printf("\nEnter adjacency matrix (1 for edge, 0 for no edge):\n");
for (i = 1; i <= n; i++) ,
for (j = 1; j <= n; j++) ,
printf("adj*%d+*%d+: ", i, j);
scanf("%d", &adj*i+*j+);
-
-

// Display adjacency matrix

printf("\nAdjacency Matrix:\n");
for (i = 1; i <= n; i++) ,
for (j = 1; j <= n; j++) ,
printf("%2d ", adj*i+*j+);
-
printf("\n");
-

// Initialize visited array and queue

for (i = 1; i <= n; i++) ,
visited*i+ = 0;
-
front = rear = -1;

// Get starting vertex and perform BFS

printf("\nEnter starting vertex for BFS: ");
scanf("%d", &start);
 printf("BFS Traversal starting from %d: ", start);
BFS(start);

return 0;
-

output

Enter number of vertices: 2

Enter adjacency matrix (1 for edge, 0 for no edge):

adj*1+*1+: 0
adj*1+*2+: 1
adj*2+*1+: 2
adj*2+*2+: 3

Adjacency Matrix:
0 1
2 3

Enter starting vertex for BFS: 3

BFS Traversal starting from 3: 3

=== Code Execution Successful ===

14. write a program to design a minimum spanning tree using prism and krishkal algorithm

#include <stdio.h>
#define MAX 20
#define INF 99999

int cost*MAX+*MAX+, parent*MAX+;

int find(int v);
void union_sets(int u, int v);
int rank*MAX+;

void prims(int n) ,
int visited*MAX+ = ,0-, i, j, k, u, v, min, min_cost = 0;

visited*1+ = 1;
printf("\n--- Prim's Algorithm ---\n");
printf("Minimum Spanning Tree:\n");

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

min = INF; u = v = 0;
for (j = 1; j <= n; j++) ,
if (visited*j+) ,
for (k = 1; k <= n; k++) ,
if (!visited*k+ && cost*j+*k+ < min) ,
min = cost*j+*k+;
u = j; v = k;
-
 -
-
-
printf("Edge %d->%d: cost %d\n", u, v, min);
min_cost += min;
visited*v+ = 1;
-
printf("Total cost: %d\n", min_cost);
-

int find(int v) ,
if (parent*v+ == v) return v;
return parent*v+ = find(parent*v+);
-

void union_sets(int u, int v) ,

u = find(u); v = find(v);
if (u != v) ,
if (rank*u+ < rank*v+) parent*u+ = v;
else if (rank*u+ > rank*v+) parent*v+ = u;
else ,
parent*v+ = u;
rank*u+++;
-
-
-

void kruskal(int n) ,
struct Edge ,
int u, v, w;
- edges*MAX*MAX+;
int edge_count = 0, i, j, min_cost = 0, edges_used = 0;

// Collect all edges

for (i = 1; i <= n; i++) ,
for (j = i+1; j <= n; j++) ,
if (cost*i+*j+ != INF) ,
edges*edge_count+.u = i;
edges*edge_count+.v = j;
edges*edge_count+.w = cost*i+*j+;
edge_count++;
-
-
-

// Sort edges by weight

for (i = 0; i < edge_count-1; i++) ,
for (j = 0; j < edge_count-i-1; j++) ,
if (edges*j+.w > edges*j+1+.w) ,
struct Edge temp = edges*j+;
edges*j+ = edges*j+1+;
edges*j+1+ = temp;
-
-
 -

// Initialize Union-Find
for (i = 1; i <= n; i++) ,
parent*i+ = i;
rank*i+ = 0;
-

printf("\n--- eruskal's Algorithm ---\n");

printf("Minimum Spanning Tree:\n");

for (i = 0; i < edge_count && edges_used < n-1; i++) ,

if (find(edges*i+.u) != find(edges*i+.v)) ,
union_sets(edges*i+.u, edges*i+.v);
printf("Edge %d->%d: cost %d\n", edges*i+.u, edges*i+.v, edges*i+.w);
min_cost += edges*i+.w;
edges_used++;
-
-
printf("Total cost: %d\n", min_cost);
-

int main() ,
int i, j, n, choice;

printf("Enter number of vertices: ");

scanf("%d", &n);

printf("Enter cost matrix (0=no edge, use %d for INF):\n", INF);

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+ = INF;
cost*j+*i+ = cost*i+*j+; // Symmetric for undirected
-
-

printf("\nCost Matrix:\n");
for (i = 1; i <= n; i++) ,
for (j = 1; j <= n; j++) ,
printf("%6d ", cost*i+*j+);
-
printf("\n");
-

printf("\n1. Prim's Algorithm\n2. eruskal's Algorithm\nChoice: ");

scanf("%d", &choice);

if (choice == 1) prims(n);
else if (choice == 2) kruskal(n);

return 0;
-
output

Enter number of vertices: 4

Enter cost matrix:
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

Choice: 1 (Prim's)
Minimum Spanning Tree:
Edge 1->2: cost 10
Edge 1->3: cost 15
Edge 4->2: cost 25
Total cost: 50

Choice: 2 (eruskal) yields same result