PRACTICAL FILE

on
Advanced Data Structure and Algorithms
(M24-CSE-105)

[Link]. Computer Science (Software)

Session:- 2025-2027

Submitted To: Submitted By:

Dr. Yogita Sangwan Aditya Chauhan
Dr. Kanwal Garg 25/MS/02
Ms. Nisha Bali [Link]. CS Sem 1st
Ms. Sonia
Ms. Anita Mehta

DEPARTMENT OF COMPUTER SCIENCE AND

APPLICATIONS KURUKSHETRA UNIVERSITY,
KURUKSHETRA

1
 INDEX
[Link]. Program Page Remarks
No.
1. Implement an AVL tree. Insert the 5-10
following sequence of numbers: 20, 4,
15, 70, 50. Show the tree structure after
insertion and perform necessary
rotations.
2. Develop a Splay tree and insert the 11-16
following sequence of numbers: 5, 9, 3,
1, 7. Show the tree structure after each
insertion and splay operation.
3. Create a B-tree of order 3 and insert the 17-22
following sequence of numbers: 10, 20,
5, 6, 12. Show the tree structure after
each insertion.
4. Construct a Red-Black tree and insert 23-29
the following sequence of numbers: 10,
18, 7, 15, 16. Show the tree structure
after each insertion and color
adjustment.
5. Implement a Binomial heap and 30-35
perform the following operations:
insert(10), insert(20), insert(5). Show
the heap structure after each insertion.
6. Develop a Fibonacci heap and perform 36-40
the following operations: insert(10),
insert(20), insert(5). Show the heap
structure after each insertion.
7. Create a Pairing heap and perform the 41-44
following operations: insert(10),
insert(20), insert(5). Show the heap
structure after each insertion.
8. Perform traversal of graph DFS. 45-47
9. Perform traversal of graph BFS. 48-49

2
10. Create an algorithm for topological 50-52
sorting and apply it to a directed acyclic
graph (DAG) with 10 vertices and 12
edges.
11. Implement Tarjan's algorithm to find 53-56
strongly connected components (SCCs)
in a directed graph with 10 vertices and
15 edges.
12. Implement the buddy system for 57-60
memory allocation. Simulate the
allocation and deallocation of memory
blocks of sizes 64KB, 128KB, 32KB,
and 256KB, and show the memory
structure after each operation.
13. Develop a memory pool allocation 61-63
system for fixed-size memory blocks of
64 bytes. Simulate the allocation and
deallocation of 1,000 blocks and
measure the time taken for these
operations.
14. Compare different garbage collection 64-68
algorithms (mark-and-sweep, reference
counting, generational) by simulating a
program that creates and destroys
objects, and measure the memory usage
and time taken.
15. Implement a basic mark-and-sweep 69-72
garbage collector in a simulated
environment with 100 objects and show
the effect on memory usage after
garbage collection.
16. Analyze the trade-offs between different 73-79
memory allocation strategies (e.g.,
buddy system vs. memory pool) by
simulating memory usage patterns and
measuring performance.
17. Implement Dijkstra's algorithm to find 80-82

3
 the shortest path in a weighted graph
with 10 vertices and 20 edges, and
analyze its time complexity.
18. Develop Bellman-Ford algorithm to 83-85
handle graphs with negative weight
edges and demonstrate its use in
detecting negative cycles in a graph
with 10 vertices and 15 edges.
19. Create Floyd-Warshall algorithm for 86-90
finding all pairs shortest paths in a
graph with 5 vertices and 10 edges, and
compare its performance with Dijkstra's
algorithm.
20. Implement Kruskal's algorithm to 91-94
find the minimum spanning tree of
a graph with 10 vertices and 15
edges, and analyze its efficiency.
21. Develop Prim's algorithm for minimum 95-101
spanning trees and compare its
performance with Kruskal's algorithm
on a graph with 10 vertices and 15
edges.

1. Implement an AVL tree. Insert the following sequence of

numbers: 20, 4, 15, 70, 50. Show the tree structure after each
insertion and perform necessary rotations
4
#include <stdio.h>
#include <stdlib.h>
struct Node {
int key;
struct Node *left, *right;
int height;
};
int height(struct Node *n) {
return (n == NULL) ? 0 : n->height;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
struct Node* newNode(int key) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->key = key;
node->left = node->right = NULL;
node->height = 1;
return node;
}
struct Node* rightRotate(struct Node* y) {
struct Node* x = y->left;
struct Node* T2 = x->right;
x->right = y;

5
 y->left = T2;
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x;
}
struct Node* leftRotate(struct Node* x) {
struct Node* y = x->right;
struct Node* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y;
}
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) {
if (node == NULL)
return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);

6
 else if (key > node->key)
node->right = insert(node->right, key);
else
return node;
node->height = 1 + max(height(node->left), height(node->right));
int balance = getBalance(node);
if (balance > 1 && key < node->left->key)
return rightRotate(node);
if (balance < -1 && key > node->right->key)
return leftRotate(node);
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->key) { // RL
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void printTree(struct Node* root, int space) {
if (root == NULL)
return;
space += 5;

7
 printTree(root->right, space);
printf("\n");
for (int i = 5; i < space; i++)
printf(" ");
printf("%d\n", root->key);
printTree(root->left, space);
}
int main() {
struct Node* root = NULL;
int arr[] = {20, 4, 15, 70, 50};
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < n; i++) {
printf("\nInserting %d...\n", arr[i]);
root = insert(root, arr[i]);
printTree(root, 0);
}
return 0;
}

Output:

Inserting 20...

8
20

Inserting 4...

20

Inserting 15...

20

15

Inserting 70...

70

9
 20

15

Inserting 50...

70

50

20

15

4
2. Develop a Splay tree and insert the following sequence of
numbers: 5, 9, 3, 1, 7. Show the tree structure after each
insertion and splay operation
#include <stdio.h>
#include <stdlib.h>

10
struct Node {
int key;
struct Node *left, *right;
};
struct Node* newNode(int key) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->key = key;
node->left = node->right = NULL;
return node;
}
struct Node* rightRotate(struct Node* x) {
struct Node* y = x->left;
x->left = y->right;
y->right = x;
return y;
}
struct Node* leftRotate(struct Node* x) {
struct Node* y = x->right;
x->right = y->left;
y->left = x;
return y;
}
struct Node* splay(struct Node* root, int key) {
if (root == NULL || root->key == key)

11
 return root;
if (key < root->key) {
if (root->left == NULL)
return root;
if (key < root->left->key) {
root->left->left = splay(root->left->left, key);
root = rightRotate(root);
} else if (key > root->left->key) {
root->left->right = splay(root->left->right, key);
if (root->left->right)
root->left = leftRotate(root->left);
}
return (root->left == NULL) ? root
rightRotate(root);
}
else {
if (root->right == NULL) return root;
if (key > root->right->key) {
root->right->right = splay(root->right->right, key);
root = leftRotate(root);
} else if (key < root->right->key) {
root->right->left = splay(root->right->left, key);
if (root->right->left)
root->right = rightRotate(root->right);

12
 }
return (root->right == NULL) ? root : leftRotate(root);
}
}
struct Node* insert(struct Node* root, int key) {
if (root == NULL)
return newNode(key);
root = splay(root, key);
if (root->key == key)
return root;
struct Node* node = newNode(key);
if (key < root->key) {
node->right = root;
node->left = root->left;
root->left = NULL;
} else {
node->left = root;
node->right = root->right;
root->right = NULL;
}
return node;
}
void printTree(struct Node* root, int space) {
if (!root) return;

13
 space += 5;
printTree(root->right, space);
printf("\n");
for (int i = 5; i < space; i++) printf(" ");
printf("%d\n", root->key);
printTree(root->left, space);
}
int main() {
struct Node* root = NULL;
int arr[] = {5, 9, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < n; i++) {
printf("\nInsert %d:\n", arr[i]);
root = insert(root, arr[i]);
printTree(root, 0);
}
return 0;
}

Output:

Insert 5:
5

14
Insert 9:

Insert 1:

Insert 7:

15
 5

3. Create a B-tree of order 3 and insert the following sequence of

numbers: 10, 20, 5, 6, 12. Show the tree structure after each
insertion
#include <stdio.h>
#include <stdlib.h>
#define ORDER 3
typedef struct BTreeNode {

16
 int keys[ORDER];
struct BTreeNode *child[ORDER + 1];
int n;
int leaf;
} BTreeNode;
BTreeNode *root = NULL;
BTreeNode *createNode(int leaf) {
BTreeNode *node = (BTreeNode *)malloc(sizeof(BTreeNode));
node->leaf = leaf;
node->n = 0;
for (int i = 0; i <= ORDER; i++)
node->child[i] = NULL;
return node;
}
void printTree(BTreeNode *node, int level) {
if (node == NULL) return;
printf("\nLevel %d [", level);
for (int i = 0; i < node->n; i++)
printf(" %d ", node->keys[i]);
printf("]");
for (int i = 0; i <= node->n; i++)
if (node->child[i])
printTree(node->child[i], level + 1);
}

17
void splitChild(BTreeNode *parent, int i, BTreeNode *fullChild) {
int t = ORDER / 2;
BTreeNode *newChild = createNode(fullChild->leaf);
newChild->n = t;
for (int j = 0; j < t; j++)
newChild->keys[j] = fullChild->keys[j + t + 1];
if (!fullChild->leaf) {
for (int j = 0; j <= t; j++)
newChild->child[j] = fullChild->child[j + t + 1];
}
fullChild->n = t;
for (int j = parent->n; j >= i + 1; j--)
parent->child[j + 1] = parent->child[j];
parent->child[i + 1] = newChild;
for (int j = parent->n - 1; j >= i; j--)
parent->keys[j + 1] = parent->keys[j];
parent->keys[i] = fullChild->keys[t];
parent->n++;
}
void insertNonFull(BTreeNode *node, int k) {
int i = node->n - 1;
if (node->leaf) {
while (i >= 0 && k < node->keys[i]) {
node->keys[i + 1] = node->keys[i];

18
 i--;
}
node->keys[i + 1] = k;
node->n++;
} else {
while (i >= 0 && k < node->keys[i])
i--;
i++;
if (node->child[i]->n == ORDER) {
splitChild(node, i, node->child[i]);
if (k > node->keys[i])
i++;
}
insertNonFull(node->child[i], k);
}
}
void insert(int k) {
if (root == NULL) {
root = createNode(1);
root->keys[0] = k;
root->n = 1;
} else {
if (root->n == ORDER) {
BTreeNode *newRoot = createNode(0);

19
 newRoot->child[0] = root;
splitChild(newRoot, 0, root);
int i = 0;
if (k > newRoot->keys[0])
i++;
insertNonFull(newRoot->child[i], k);
root = newRoot;
} else {
insertNonFull(root, k);
}
}
}
int main() {
int arr[] = {10, 20, 5, 6, 12};
int n = sizeof(arr) / sizeof(arr[0]);
printf("B-Tree of order 3 insertion:\n");
for (int i = 0; i < n; i++) {
printf("\n\nAfter inserting %d:", arr[i]);
insert(arr[i]);
printTree(root, 0);
printf("\n");
}
return 0;
}

20
Output:
B-Tree of order 3 insertion:
After inserting 10:
Level 0 [ 10 ]

After inserting 20:

Level 0 [ 10 20 ]

21
 After inserting 5:
Level 0 [ 5 10 20 ]

After inserting 6:
Level 0 [ 10 ]
Level 1 [ 5 6 ]
Level 1 [ 20]

After inserting 12:

Level 0 [ 10 ]
Level 1 [ 5 6 ]
Level 1 [ 12 20 ]

4. Construct a Red-Black tree and insert the following sequence

of numbers: 10, 18, 7, 15, 16. Show the tree structure after each
insertion and color adjustment
#include <stdio.h>
#include <stdlib.h>
enum Color { RED, BLACK };
struct Node {
int data;
enum Color color;

22
 struct Node *left, *right, *parent;
};
struct Node* createNode(int data) {
struct Node* n = (struct Node*)malloc(sizeof(struct Node));
n->data = data;
n->color = RED;
n->left = n->right = n->parent = NULL;
return n;
}
struct Node* rotateLeft(struct Node* root, struct Node* x) {
struct Node* y = x->right;
x->right = y->left;
if (y->left) y->left->parent = x;
y->parent = x->parent;
if (!x->parent) root = y;
else if (x == x->parent->left) x->parent->left = y;
else x->parent->right = y;
y->left = x;
x->parent = y;
return root;
}
struct Node* rotateRight(struct Node* root, struct Node* y) {
struct Node* x = y->left;
y->left = x->right;

23
 if (x->right) x->right->parent = y;
x->parent = y->parent;
if (!y->parent) root = x;
else if (y == y->parent->left) y->parent->left = x;
else y->parent->right = x;
x->right = y;
y->parent = x;
return root;
}

struct Node* fixInsert(struct Node* root, struct Node* z) {

while (z->parent && z->parent->color == RED) {
struct Node* gp = z->parent->parent;
if (z->parent == gp->left) {
struct Node* y = gp->right;
if (y && y->color == RED) { // Case 1
z->parent->color = BLACK;
y->color = BLACK;
gp->color = RED;
z = gp;
} else {
if (z == z->parent->right) { // Case 2
z = z->parent;
root = rotateLeft(root, z);

24
 }
z->parent->color = BLACK; // Case 3
gp->color = RED;

root = rotateRight(root, gp);

}
} else {
struct Node* y = gp->left;
if (y && y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
gp->color = RED;
z = gp;
} else {
if (z == z->parent->left) {
z = z->parent;
root = rotateRight(root, z);
}
z->parent->color = BLACK;
gp->color = RED;
root = rotateLeft(root, gp);
}
}
}

25
 root->color = BLACK;
return root;
}
struct Node* insert(struct Node* root, int data) {
struct Node* z = createNode(data);
struct Node* y = NULL;
struct Node* x = root;
while (x != NULL) {
y = x;
if (z->data < x->data) x = x->left;
else x = x->right;
}
z->parent = y;
if (y == NULL) root = z;
else if (z->data < y->data) y->left = z;
else y->right = z;
return fixInsert(root, z);
}
void printTree(struct Node* root, int space) {
if (!root) return;
space += 8;
printTree(root->right, space);
printf("\n");
for (int i = 8; i < space; i++) printf(" ");

26
 printf("%d(%c)\n", root->data, root->color == RED ? 'R' : 'B');
printTree(root->left, space);
}
int main() {
struct Node* root = NULL;
int arr[] = {10, 18, 7, 15, 16};
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < n; i++) {
printf("\nInsert %d:\n", arr[i]);
root = insert(root, arr[i]);
printTree(root, 0);
}
return 0;
}

Output:
Insert 10:

10(B)

Insert 18:

18(R)

27
10(B)

Insert 7:

18(R)

10(B)

7(R)

Insert 15:

18(B)

15(R)

10(B)

7(B)

28
 Insert 16:

18(R)

16(B)

15(R)

10(B)

7(B)

5. Implement a Binomial heap and perform the following

operations insert(10), insert(20), insert(5). Show the heap
structure after each insertion
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct BinomialNode {
int key;
int degree;
struct BinomialNode *parent;
struct BinomialNode *child;

29
 struct BinomialNode *sibling;
} BinomialNode;
BinomialNode* createNode(int key) {
BinomialNode* newNode =
(BinomialNode*)malloc(sizeof(BinomialNode));
newNode->key = key;
newNode->degree = 0;
newNode->parent = NULL;
newNode->child = NULL;
newNode->sibling = NULL;
return newNode;
}
void binomialLink(BinomialNode* y, BinomialNode* z) {
y->parent = z;
y->sibling = z->child;
z->child = y;
z->degree++;
}
BinomialNode* binomialMerge(BinomialNode* h1, BinomialNode*
h2) {
if (!h1) return h2;
if (!h2) return h1;
BinomialNode* head;
BinomialNode* tail;

30
 if (h1->degree <= h2->degree) {
head = h1;
h1 = h1->sibling;
} else {
head = h2;
h2 = h2->sibling;
}
tail = head;
while (h1 && h2) {
if (h1->degree <= h2->degree) {
tail->sibling = h1;
h1 = h1->sibling;
} else {
tail->sibling = h2;
h2 = h2->sibling;
}
tail = tail->sibling;
}
tail->sibling = h1 ? h1 : h2;
return head;
}
BinomialNode* binomialUnion(BinomialNode* h1, BinomialNode*
h2) {
BinomialNode* newHeap = binomialMerge(h1, h2);

31
 if (!newHeap) return NULL;
BinomialNode* prev = NULL;
BinomialNode* curr = newHeap;
BinomialNode* next = curr->sibling;
while (next != NULL) {
if ((curr->degree != next->degree) ||
(next->sibling != NULL && next->sibling->degree == curr-
>degree)) {
prev = curr;
curr = next;
} else {
if (curr->key <= next->key) {
curr->sibling = next->sibling;
binomialLink(next, curr);
} else {
if (prev == NULL)
newHeap = next;
else
prev->sibling = next;
binomialLink(curr, next);
curr = next;
}
}
next = curr->sibling;

32
 }
return newHeap;
}
BinomialNode* insert(BinomialNode* heap, int key) {
BinomialNode* newNode = createNode(key);
heap = binomialUnion(heap, newNode);
return heap;
}
void displayHeap(BinomialNode* h){
printf("\nBinomial Heap Structure:\n");
BinomialNode* temp = h;
while (temp != NULL) {
printf("B%d: ", temp->degree);
printf("(root %d) ", temp->key);
if (temp->child) {
BinomialNode* c = temp->child;
printf("[children: ");
while (c) {
printf("%d ", c->key);
c = c->sibling;
}
printf("]");
}
printf("\n");

33
 temp = temp->sibling;
}
}
int main() {
BinomialNode* heap = NULL;
printf("Inserting 10...\n");
heap = insert(heap, 10);
displayHeap(heap);
printf("Inserting 20...\n");
heap = insert(heap, 20);
displayHeap(heap);
printf("Inserting 5...\n");
heap = insert(heap, 5);
displayHeap(heap);
return 0;
}

Output:
Inserting 10...
Binomial Heap Structure:
B0: (root 10)

Inserting 20...
Binomial Heap Structure:

34
 B1: (root 10) [children: 20 ]

Inserting 5...
Binomial Heap Structure:
B0: (root 5)
B1: (root 10) [children: 20 ]

6. Develop a Fibonacci heap and performs the following

operations insert(10), insert(20), insert 5. Show that heap
structure after each insertion
#include <stdio.h>
#include <stdlib.h>
typedef struct FibonacciNode {
int key;
int degree;
struct FibonacciNode *parent;
struct FibonacciNode *child;
struct FibonacciNode *left;

35
 struct FibonacciNode *right;
int mark;
} FibonacciNode;
typedef struct FibonacciHeap {
FibonacciNode *min;
int n;
} FibonacciHeap;
FibonacciNode* createNode(int key) {
FibonacciNode* node =
(FibonacciNode*)malloc(sizeof(FibonacciNode));
node->key = key;
node->degree = 0;
node->parent = NULL;
node->child = NULL;
node->left = node;
node->right = node;
node->mark = 0;
return node;
}
FibonacciHeap* createHeap() {
FibonacciHeap* heap =
(FibonacciHeap*)malloc(sizeof(FibonacciHeap));
heap->min = NULL;
heap->n = 0;

36
 return heap;
}
void insertNode(FibonacciHeap* heap, FibonacciNode* node) {
if (heap->min == NULL) {
heap->min = node;
} else {
node->left = heap->min;
node->right = heap->min->right;
heap->min->right->left = node;
heap->min->right = node;
if (node->key < heap->min->key)
heap->min = node;
}
heap->n++;
}
void insert(FibonacciHeap* heap, int key) {
FibonacciNode* node = createNode(key);
insertNode(heap, node);
printf("Inserted %d into Fibonacci Heap.\n", key);
}
void displayHeap(FibonacciHeap* heap) {
if (heap->min == NULL) {
printf("\nFibonacci Heap is empty.\n");
return;

37
 }
printf("\nFibonacci Heap Structure:\n");
FibonacciNode* temp = heap->min;
FibonacciNode* start = temp;
do {
printf("Key: %d (degree %d)\n", temp->key, temp->degree);
if (temp->child) {
printf(" Children: ");
FibonacciNode* c = temp->child;
FibonacciNode* cstart = c;
do {
printf("%d ", c->key);
c = c->right;
} while (c != cstart);
printf("\n");
}
temp = temp->right;
} while (temp != start);
}
int main() {
FibonacciHeap* heap = createHeap();
insert(heap, 10);
displayHeap(heap);
insert(heap, 20);

38
 displayHeap(heap);
insert(heap, 5);
displayHeap(heap);
return 0;
}

Output:
Inserted 10 into Fibonacci Heap.
Fibonacci Heap Structure:
Key: 10 (degree 0)

Inserted 20 into Fibonacci Heap.

Fibonacci Heap Structure:
Key: 10 (degree 0)
Key: 20 (degree 0)

39
 Inserted 5 into Fibonacci Heap.
Fibonacci Heap Structure:
Key: 5 (degree 0)
Key: 20 (degree 0)
Key: 10 (degree 0)

7. Create a Pairing heap and performs the following operations

insert(10), insert(20), insert(5). Show the heap structure after
each insertion
#include <stdio.h>
#include <stdlib.h>
typedef struct PairNode {
int key;
struct PairNode* child;
struct PairNode* sibling;
} PairNode;
PairNode* createNode(int key) {
PairNode* node = (PairNode*)malloc(sizeof(PairNode));

40
 node->key = key;
node->child = NULL;
node->sibling = NULL;
return node;
}
PairNode* merge(PairNode* h1, PairNode* h2) {
if (h1 == NULL)
return h2;
if (h2 == NULL)
return h1;

if (h2->key < h1->key) {

h1->sibling = h2->child;
h2->child = h1;
return h2;
}
else {
h2->sibling = h1->child;
h1->child = h2;
return h1;
}
}
PairNode* insert(PairNode* heap, int key) {
PairNode* newNode = createNode(key);

41
 heap = merge(heap, newNode);
printf("Inserted %d into Pairing Heap.\n", key);
return heap;
}
void displayHeap(PairNode* root, int level) {
if (root == NULL)
return;
for (int i = 0; i < level; i++)
printf(" ");
printf("%d\n", root->key);
displayHeap(root->child, level + 1);
displayHeap(root->sibling, level);
}
void showHeap(PairNode* heap) {
printf("\nPairing Heap Structure:\n");
displayHeap(heap, 0);
}
int main() {
PairNode* heap = NULL;
heap = insert(heap, 10);
showHeap(heap);
heap = insert(heap, 20);
showHeap(heap);
heap = insert(heap, 5);

42
 showHeap(heap);
return 0;
}

Output:
Inserted 10 into Pairing Heap.
Pairing Heap Structure:
10

Inserted 20 into Pairing Heap.

Pairing Heap Structure:
10
20

Inserted 5 into Pairing Heap.

Pairing Heap Structure:

43
 5
10
20

8. Perform Traversal of graph BFS

#include <stdio.h>
#include <stdlib.h>
struct Node {
int dest;
struct Node* next;
};
struct AdjList {
struct Node* head;
};
struct Node* createNode(int dest) {

44
 struct Node* newNode = (struct Node*)malloc(sizeof(struct
Node));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
void DFSRec(struct AdjList adj[], int visited[], int s) {
visited[s] = 1;
printf("%d ", s);
struct Node* current = adj[s].head;
while (current != NULL) {
int dest = current->dest;
if (!visited[dest]) {
DFSRec(adj, visited, dest);
}
current = current->next;
}
}
void DFS(struct AdjList adj[], int V, int s) {
int visited[V];
for (int i = 0; i < V; i++)
visited[i] = 0;

DFSRec(adj, visited, s);

45
}
void addEdge(struct AdjList adj[], int s, int t) {
struct Node* newNode = createNode(t);
newNode->next = adj[s].head;
adj[s].head = newNode;
newNode = createNode(s);
newNode->next = adj[t].head;
adj[t].head = newNode;
}
int main() {
int V = 5;
struct AdjList adj[V];
for (int i = 0; i < V; i++) {
adj[i].head = NULL;
}
int E = 5;
int edges[][2] = {{1, 2}, {1, 0}, {2, 0}, {2, 3}, {2, 4}};
for (int i = 0; i < E; i++) {
addEdge(adj, edges[i][0], edges[i][1]);
}
int source = 1;
printf("DFS from source %d:\n", source);
DFS(adj, V, source);
return 0;

46
 }

Output:
DFS from source 1:
10243

9. Perform Traversal of graph BFS

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 100
void BFS(int adj[MAX][MAX], int V, int s) {
int q[MAX], front = 0, rear = 0;
bool visited[MAX] = {false};
visited[s] = true;
q[rear++] = s;
while (front < rear) {

47
 int curr = q[front++];
printf("%d ", curr);
for (int i = 0; i < V; i++) {
if (adj[curr][i] == 1 && !visited[i]) {
visited[i] = true;
q[rear++] = i;
}
}
}
}
void addEdge(int adj[MAX][MAX], int u, int v) {
adj[u][v] = 1;
adj[v][u] = 1;
}
int main() {
int V = 5;
int adj[MAX][MAX] = {0};
addEdge(adj, 0, 1);
addEdge(adj, 0, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 2, 4);
printf("BFS starting from 0:\n");
BFS(adj, V, 0);

48
 return 0;
}

Output:
BFS starting from 0:
01234

10. Create an algorithm for topological sorting and apply it to a

directed acyclic graph (DAG) with 10 vertices and 12 edges
#include <stdio.h>
#include <stdlib.h>
#define V 10
#define E 12
typedef struct Node {
int vertex;
struct Node* next;
} Node;
Node* adjList[V];
int indegree[V];
49
Node* createNode(int v) {
Node* temp = (Node*)malloc(sizeof(Node));
temp->vertex = v;
temp->next = NULL;
return temp;
}
void addEdge(int u, int v) {
Node* temp = createNode(v);
temp->next = adjList[u];
adjList[u] = temp;
indegree[v]++;
}
void topologicalSort() {
int queue[V], front = 0, rear = 0;
int topoOrder[V], k = 0;
for (int i = 0; i < V; i++)
if (indegree[i] == 0)
queue[rear++] = i;
while (front < rear) {
int u = queue[front++];
topoOrder[k++] = u;
Node* temp = adjList[u];
while (temp != NULL) {
indegree[temp->vertex]--;

50
 if (indegree[temp->vertex] == 0)
queue[rear++] = temp->vertex;
temp = temp->next;
}
}
if (k != V) {
printf("Graph has a cycle! Topological sort not possible.\n");
return;
}
printf("Topological Sort Order: ");
for (int i = 0; i < V; i++)
printf("%d ", topoOrder[i]);
printf("\n");
}
int main() {
for (int i = 0; i < V; i++) {
adjList[i] = NULL;
indegree[i] = 0;
}
int edges[E][2] = {
{0, 2}, {0, 3},
{1, 3}, {1, 4},
{2, 5}, {3, 5},
{3, 6}, {4, 6},

51
 {5, 7}, {6, 8},
{7, 9}, {8, 9}
};
for (int i = 0; i < E; i++)
addEdge(edges[i][0], edges[i][1]);
topologicalSort();
return 0;
}

Output:
Topological Sort Order:
0124365879
11. Implement Tarjan's algorithm to find strongly connected
components (SCCs) in a directed graph with 10 vertices and 15
edges
#include <stdio.h>
#include <stdlib.h>
#define V 10
#define E 15
int adj[V][V];
int indexCounter = 0;
int indices[V], lowlink[V], onStack[V];
int stack[V], top = -1;
void push(int v) { stack[++top] = v; }

52
int pop() { return stack[top--]; }
void addEdge(int u, int v) {
adj[u][v] = 1;
}
void tarjanDFS(int u) {
indices[u] = lowlink[u] = indexCounter++;
push(u);
onStack[u] = 1;
for (int v = 0; v < V; v++) {
if (adj[u][v]) {
if (indices[v] == -1) {
tarjanDFS(v);
lowlink[u] = (lowlink[u] < lowlink[v]) ? lowlink[u] :
lowlink[v];
}
else if (onStack[v]) {
lowlink[u] = (lowlink[u] < indices[v]) ? lowlink[u] :
indices[v];
}
}
}
if (lowlink[u] == indices[u]) {
printf("SCC: ");
while (1) {

53
 int v = pop();
onStack[v] = 0;
printf("%d ", v);
if (v == u) break;
}
printf("\n");
}
}
int main() {
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
adj[i][j] = 0;
int edges[15][2] = {
{0,1},{1,2},{2,0},
{3,4},{4,5},{5,3},
{6,7},{7,8},{8,6},
{2,3},{5,6},{8,9},
{1,9},{4,7},{0,5}
};
top = -1;
indexCounter = 0;
for (int i = 0; i < V; i++) {
indices[i] = -1;
lowlink[i] = 0;

54
 onStack[i] = 0;
}
for (int i = 0; i < 15; i++)
addEdge(edges[i][0], edges[i][1]);
printf("Strongly Connected Components:\n");
for (int i = 0; i < V; i++)
if (indices[i] == -1)
tarjanDFS(i);
return 0;
}

Output:
Strongly Connected Components:
SCC: 9
SCC: 8 7 6
SCC: 5 4 3
SCC: 2 1 0

55
12. Implement the buddy system for memory allocation. Simulate
the allocation and deallocation of memory blocks of sizes
64KB, 128KB, 32KB, and 256KB, and show the memory
structure after each operation
#include <stdio.h>
#include <math.h>
#include <string.h>
#define MAX 1024
#define LEVELS 10
int memory[MAX];
int buddyFree[LEVELS];
void printMemory() {
printf("Memory Blocks (0 = Free, 1 = Used):\n");
for (int i = 0; i < 64; i++)

56
 printf("%d", memory[i]);
printf("\n\n");
}
int nextPower(int size) {
int p = 1;
while (p < size) p *= 2;
return p;
}
void allocate(int size) {
int block = nextPower(size);
int idx = -1;
for (int i = 0; i < MAX; i += block) {
int free = 1;
for (int j = i; j < i + block; j++) {
if (memory[j] == 1) {
free = 0;
break;
}
}
if (free) {
idx = i;
break;
}
}

57
 if (idx == -1) {
printf("Cannot allocate %d KB\n", size);
return;
}
for (int i = idx; i < idx + block; i++)
memory[i] = 1;
printf("Allocated %d KB (block %d KB) at index %d\n", size,
block, idx);
printMemory();
}
void deallocate(int size, int start) {
int block = nextPower(size);
for (int i = start; i < start + block; i++)
memory[i] = 0;
printf("Deallocated %d KB (block %d KB) from index %d\n", size,
block, start);
printMemory();
}
int main() {
memset(memory, 0, sizeof(memory));
allocate(64);
allocate(128);
allocate(32);
allocate(256);

58
 deallocate(128, 64);
return 0;
}

Output:
Allocated 64 KB (block 64 KB) at index 0
Memory Blocks (0 = Free, 1 = Used):
111111111111111111111111111111111111111111111111111111111111
1111
Allocated 128 KB (block 128 KB) at index 128
Memory Blocks (0 = Free, 1 = Used):
111111111111111111111111111111111111111111111111111111111111
1111
Allocated 32 KB (block 32 KB) at index 32
Memory Blocks (0 = Free, 1 = Used):
111111111111111111111111111111111111111111111111111111111111
1111
Allocated 256 KB (block 256 KB) at index 256
59
 Memory Blocks (0 = Free, 1 = Used):
111111111111111111111111111111111111111111111111111111111111
1111
Deallocated 128 KB (block 128 KB) from index 64Memory Blocks (0
= Free, 1 =
Used)1111111111111111111111111111111111111111111111111111111
11111111111

13. Develop a memory pool allocation system for fixed-size

memory blocks of 64 bytes. Simulate the allocation and
deallocation of 1,000 blocks and measure the time taken for
these operations
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define BLOCK_SIZE 64
#define NUM_BLOCKS 1000
typedef struct Block {
struct Block* next;
char data[BLOCK_SIZE];
} Block;
Block memoryPool[NUM_BLOCKS];
Block* freeList = NULL;
void initMemoryPool() {
60
 freeList = &memoryPool[0];
for (int i = 0; i < NUM_BLOCKS - 1; i++) {
memoryPool[i].next = &memoryPool[i + 1];
}
memoryPool[NUM_BLOCKS - 1].next = NULL;
}
void* allocateBlock() {
if (freeList == NULL) {
return NULL;
}
Block* block = freeList;
freeList = freeList->next;
return (void*)block;
}
void deallocateBlock(void* ptr) {
Block* block = (Block*)ptr;
block->next = freeList;
freeList = block;
}
int main() {
clock_t start, end;
double allocTime, deallocTime;
initMemoryPool();
void* allocated[NUM_BLOCKS];

61
 start = clock();
for (int i = 0; i < NUM_BLOCKS; i++) {
allocated[i] = allocateBlock();
if (!allocated[i]) {
printf("Memory pool exhausted at block %d\n", i);
break;
}
}
end = clock();
allocTime = ((double)(end - start)) / CLOCKS_PER_SEC;
start = clock();
for (int i = 0; i < NUM_BLOCKS; i++) {
deallocateBlock(allocated[i]);
}
end = clock();
deallocTime = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Allocated %d blocks of %d bytes\n", NUM_BLOCKS,
BLOCK_SIZE);
printf("Allocation time: %.6f seconds\n", allocTime);
printf("Deallocation time: %.6f seconds\n", deallocTime);
return 0;
}

Output:

62
 Allocated 1000 blocks of 64 bytes
Allocation time: 0.000007 seconds
Deallocation time: 0.000006 seconds

14. Compare different garbage collection algorithms (mark-and-

sweep, reference counting, generational) by simulating a
program that creates and destroys objects, and measure the
memory usage and time taken
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define NUM_OBJECTS 50000
#define MAX_CHILDREN 3
typedef struct Object {
int id;
int marked;
int refCount;
int numChildren;
struct Object* children[MAX_CHILDREN];
} Object;

63
Object* heap[NUM_OBJECTS];
Object* roots[1000];
int rootCount = 0;
double now() {
return (double)clock() / CLOCKS_PER_SEC;
}
Object* newObject(int id) {
Object* obj = (Object*)malloc(sizeof(Object));
obj->id = id;
obj->marked = 0;
obj->refCount = 1;
obj->numChildren = 0;
return obj;
}
void addChild(Object* parent, Object* child) {
if (parent->numChildren < MAX_CHILDREN) {
parent->children[parent->numChildren++] = child;
child->refCount++;
}
}
void rcDelete(Object* obj) {
if (!obj || --obj->refCount > 0) return;

for (int i = 0; i < obj->numChildren; i++)

64
 rcDelete(obj->children[i]);
free(obj);
}
void runReferenceCounting() {
double t = now();
for (int i = 0; i < NUM_OBJECTS; i++) {
heap[i] = newObject(i);
if (i > 0)
addChild(heap[i - 1], heap[i]);
}
for (int i = 0; i < NUM_OBJECTS; i++)
rcDelete(heap[i]);
printf("Reference Counting Time: %.4f sec\n", now() - t);
}
void mark(Object* obj) {
if (!obj || obj->marked) return;
obj->marked = 1;
for (int i = 0; i < obj->numChildren; i++)
mark(obj->children[i]);
}
void sweep() {
for (int i = 0; i < NUM_OBJECTS; i++) {
if (heap[i] && !heap[i]->marked) {
free(heap[i]);

65
 heap[i] = NULL;
} else if (heap[i]) {
heap[i]->marked = 0; // reset for next cycle
}
}
}
void runMarkAndSweep() {
double t = now();
for (int i = 0; i < NUM_OBJECTS; i++) {
heap[i] = newObject(i);
if (i > 0)
addChild(heap[i - 1], heap[i]);
}
roots[rootCount++] = heap[0];
for (int i = 0; i < rootCount; i++)
mark(roots[i]);
sweep();
printf("Mark-and-Sweep Time: %.4f sec\n", now() - t);
}
#define YOUNG_SIZE 20000
Object* youngGen[YOUNG_SIZE];
Object* oldGen[NUM_OBJECTS];

int youngCount = 0, oldCount = 0;

66
void promote(Object* obj) {
oldGen[oldCount++] = obj;
}
void runGenerationalGC() {
double t = now();
for (int i = 0; i < NUM_OBJECTS; i++) {
Object* obj = newObject(i);
if (youngCount < YOUNG_SIZE)
youngGen[youngCount++] = obj;
else
promote(obj);
}
for (int i = 0; i < youngCount; i++)
free(youngGen[i]);
youngCount = 0;
for (int i = 0; i < oldCount; i++)
free(oldGen[i]);
printf("Generational GC Time: %.4f sec\n", now() - t);
}
int main() {
printf("Creating objects: %d\n\n", NUM_OBJECTS);
runReferenceCounting();
runMarkAndSweep();
runGenerationalGC();

67
 return 0;
}
Output:
Creating objects: 50000
Reference Counting Time: 0.0031 sec
Mark-and-Sweep Time: 0.0031 sec
Generational GC Time: 0.0027 sec
15. Implement a basic mark-and-sweep garbage collector in a
simulated environment with 100 objects and show the effect on
memory usage after garbage collection
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 100
#define MAXREF 3
#define ROOTS 5
typedef struct Object {
int id;
int marked;
int num_refs;
struct Object* refs[MAXREF];
} Object;
Object* heap[N];
Object* roots[ROOTS];

68
Object* createObject(int id) {
Object* obj = (Object*)malloc(sizeof(Object));
obj->id = id;
obj->marked = 0;
obj->num_refs = 0;
for (int i = 0; i < MAXREF; i++)
obj->refs[i] = NULL;
return obj;
}
void mark(Object* obj) {
if (!obj || obj->marked) return;
obj->marked = 1;
for (int i = 0; i < obj->num_refs; i++)
mark(obj->refs[i]);
}
int sweep() {
int freed = 0;
for (int i = 0; i < N; i++) {
if (heap[i] != NULL && heap[i]->marked == 0) {
free(heap[i]);
heap[i] = NULL;
freed++;
}
else if (heap[i] != NULL) {

69
 heap[i]->marked = 0; // reset for next cycle
}
}
return freed;
}
void showMemoryUsage() {
int used = 0;
for (int i = 0; i < N; i++)
if (heap[i] != NULL)
used++;
printf("Objects currently alive: %d\n", used);
}
int main() {
srand(time(0));
for (int i = 0; i < N; i++)
heap[i] = createObject(i);
for (int i = 0; i < N; i++) {
int refCount = rand() % (MAXREF + 1);
heap[i]->num_refs = refCount;

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

heap[i]->refs[j] = heap[rand() % N];
}

70
 for (int i = 0; i < ROOTS; i++)
roots[i] = heap[rand() % N];

printf("\n=== Memory Usage Before Garbage Collection ===\n");

showMemoryUsage();
for (int i = 0; i < ROOTS; i++)
mark(roots[i]);
int freed = sweep();
printf("\n=== Garbage Collection Complete ===\n");
printf("Objects freed: %d\n", freed);
printf("\n=== Memory Usage After Garbage Collection ===\n");
showMemoryUsage();
return 0;
}

Output:
=== Memory Usage Before Garbage Collection ===
Objects currently alive: 100

=== Garbage Collection Complete ===

Objects freed: 42

=== Memory Usage After Garbage Collection ===

Objects currently alive: 58

71
16. Analyze the trade-offs between different memory allocation
strategies (e.g., buddy system vs. memory pool) by simulating
memory usage patterns and measuring performance
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TOTAL_MEMORY (1024 * 1024)
#define BLOCK_SIZE 64
#define OPS 50000
unsigned char pool[TOTAL_MEMORY];
int pool_free[(TOTAL_MEMORY / BLOCK_SIZE)];
void pool_init() {
int total_blocks = TOTAL_MEMORY / BLOCK_SIZE;
for (int i = 0; i < total_blocks; i++)
pool_free[i] = 1;
}
void* pool_alloc(int size) {
int needed = (size + BLOCK_SIZE - 1) / BLOCK_SIZE;
int total_blocks = TOTAL_MEMORY / BLOCK_SIZE;

72
 int count = 0, start = -1;

for (int i = 0; i < total_blocks; i++) {

if (pool_free[i]) {
if (count == 0) start = i;
count++;
if (count == needed) {
for (int j = start; j < start + needed; j++)
pool_free[j] = 0;
return &pool[start * BLOCK_SIZE];
}
} else {
count = 0;
}
}
return NULL;
}
void pool_free_block(void* ptr, int size) {
int start = ((unsigned char*)ptr - pool) / BLOCK_SIZE;
int blocks = (size + BLOCK_SIZE - 1) / BLOCK_SIZE;
for (int i = start; i < start + blocks; i++)
pool_free[i] = 1;
}

73
typedef struct Buddy {
int size;
int free;
struct Buddy* next;
} Buddy;
Buddy* buddy_list[20];

// Compute level based on block size

int level_from_size(int size) {
int level = 0;
int s = 1;
while (s < size) {
s <<= 1;
level++;
}
return level;
}
void buddy_init() {
for (int i = 0; i < 20; i++)
buddy_list[i] = NULL;
Buddy* root = (Buddy*)malloc(sizeof(Buddy));
root->size = TOTAL_MEMORY;
root->free = 1;
root->next = NULL;

74
 buddy_list[level_from_size(TOTAL_MEMORY)] = root;
}
Buddy* buddy_alloc(int size) {
int level = level_from_size(size);
int i = level;
while (i < 20 && buddy_list[i] == NULL)
i++;
if (i == 20) return NULL;
Buddy* block = buddy_list[i];
buddy_list[i] = block->next;
while (i > level) {
i--;
Buddy* buddy = (Buddy*)malloc(sizeof(Buddy));
buddy->size = (1 << i);
buddy->free = 1;
buddy->next = buddy_list[i];
buddy_list[i] = buddy;
block->size = (1 << i);
}
block->free = 0;
return block;
}
void buddy_free(Buddy* block) {
int level = level_from_size(block->size);

75
 block->free = 1;
block->next = buddy_list[level];
buddy_list[level] = block;
}
int random_size() {
return (rand() % 500) + 1;
}
double time_now() {
return (double)clock() / CLOCKS_PER_SEC;
}
double fragmentation_pool() {
int used = 0, total = TOTAL_MEMORY / BLOCK_SIZE;
for (int i = 0; i < total; i++)
if (!pool_free[i]) used++;
return 100.0 * (1.0 - ((double)used * BLOCK_SIZE) /
TOTAL_MEMORY);
}
double fragmentation_buddy() {
int free_bytes = 0;
for (int i = 0; i < 20; i++) {
Buddy* b = buddy_list[i];
while (b) {
if (b->free) free_bytes += b->size;
b = b->next;

76
 }
}
return 100.0 * free_bytes / TOTAL_MEMORY;
}
int main() {
srand(time(NULL));
pool_init();
double t1 = time_now();
for (int i = 0; i < OPS; i++) {
int size = random_size();
void* p = pool_alloc(size);
if (p) pool_free_block(p, size);
}
double t_pool = time_now() - t1;
buddy_init();
t1 = time_now();
for (int i = 0; i < OPS; i++) {
int size = random_size();
Buddy* b = buddy_alloc(size);
if (b) buddy_free(b);
}
double t_buddy = time_now() - t1;
printf("\n===== MEMORY ALLOCATION STRATEGY
COMPARISON =====\n");

77
 printf("Buddy System: time = %.4f sec, fragmentation = %.2f%%\
n",
t_buddy, fragmentation_buddy());
printf("Memory Pool: time = %.4f sec, fragmentation = %.2f%%\
n",
t_pool, fragmentation_pool());
return 0;
}

Output:
===== MEMORY ALLOCATION STRATEGY COMPARISON
=====
Buddy System: time = 0.0016 sec, fragmentation = 0.00%
Memory Pool: time = 0.0024 sec, fragmentation = 100.00%

78
17. Implement Dijkstra's algorithm to find the shortest path in a
weighted graph with 10 vertices and 20 edges, and analyze its
time complexity
#include <stdio.h>
#include <limits.h>
#define V 10
int minDistance(int dist[], int visited[]) {
int min = INT_MAX, index = -1;
for (int i = 0; i < V; i++) {
if (!visited[i] && dist[i] < min) {
min = dist[i];
index = i;
}
}
return index;
}
void dijkstra(int graph[V][V], int src) {
int dist[V], visited[V];
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;

79
 visited[i] = 0;
}
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, visited);
visited[u] = 1;
for (int v = 0; v < V; v++) {
if (!visited[v] && graph[u][v] &&
dist[u] != INT_MAX &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
printf("Vertex \tDistance from Source\n");
for (int i = 0; i < V; i++) {
printf("%d \t%d\n", i, dist[i]);
}
}
int main() {
int graph[V][V] = {
{0, 4, 0, 0, 0, 0, 0, 8, 0, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2, 0},

80
 {0, 0, 7, 0, 9, 14, 0, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6, 0},
{8, 11, 0, 0, 0, 0, 1, 0, 7, 0},
{0, 0, 2, 0, 0, 0, 6, 7, 0, 3},
{0, 0, 0, 0, 0, 0, 0, 0, 3, 0}
};
dijkstra(graph, 0);
return 0;
}

Output:
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
9 17

81
18. Develop Bellman-Ford algorithm to handle graphs with
negative weight edges and demonstrate its use in detecting
negative cycles in a graph with 10 vertices and 15 edges
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define V 10
#define E 15
typedef struct {
int src, dest, weight;
} Edge;
typedef struct {
int numVertices, numEdges;
Edge edges[E];
} Graph;
Graph* createGraph() {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->numVertices = V;
graph->numEdges = E;
graph->edges[0] = (Edge){0, 1, 6};
graph->edges[1] = (Edge){0, 2, 5};
graph->edges[2] = (Edge){0, 3, 5};

82
 graph->edges[3] = (Edge){1, 4, -1};
graph->edges[4] = (Edge){2, 1, -2};
graph->edges[5] = (Edge){2, 4, 1};
graph->edges[6] = (Edge){3, 2, -2};
graph->edges[7] = (Edge){3, 5, -1};
graph->edges[8] = (Edge){4, 6, 3};
graph->edges[9] = (Edge){5, 6, 3};
graph->edges[10] = (Edge){6, 7, 2};
graph->edges[11] = (Edge){7, 8, -5};
graph->edges[12] = (Edge){8, 9, 2};
graph->edges[13] = (Edge){9, 3, 1};
graph->edges[14] = (Edge){4, 9, 2};
return graph;
}
void BellmanFord(Graph* graph, int src) {
int numVertices = graph->numVertices;
int numEdges = graph->numEdges;
int dist[numVertices];
for (int i = 0; i < numVertices; i++)
dist[i] = INT_MAX;
dist[src] = 0;
for (int i = 1; i <= numVertices - 1; i++) {
for (int j = 0; j < numEdges; j++) {
int u = graph->edges[j].src;

83
 int v = graph->edges[j].dest;
int w = graph->edges[j].weight;
if (dist[u] != INT_MAX && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
}
}
for (int j = 0; j < numEdges; j++) {
int u = graph->edges[j].src;
int v = graph->edges[j].dest;
int w = graph->edges[j].weight;
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
printf("Graph contains a negative weight cycle\n");
return;
}
}
printf("Vertex Distance from Source %d\n", src);
for (int i = 0; i < numVertices; i++)
printf("%d\t\t%d\n", i, dist[i]);
}
int main() {
Graph* graph = createGraph();
BellmanFord(graph, 0);
free(graph);
return 0;

84
 }
Output: Graph contains a negative weight cycle
19. Create Floyd-Warshall algorithm for finding all pairs shortest
paths in a graph with 5 vertices and 10 edges, and compare its
performance with Dijkstra's algorithm
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>
#define V 5
#define E 10
#define INF 1000000
int graph[V][V];
void initGraph() {
for(int i = 0; i < V; i++)
for(int j = 0; j < V; j++)
if(i == j) graph[i][j] = 0;
else graph[i][j] = INF;
int edges[E][3] = {
{0,1,3}, {0,2,8}, {0,4,-4}, {1,3,1}, {1,4,7},
{2,1,4}, {3,0,2}, {3,2,-5}, {4,3,6}, {2,4,2}
};
for(int i = 0; i < E; i++) {
int u = edges[i][0];

85
 int v = edges[i][1];
int w = edges[i][2];
graph[u][v] = w;
}
}
void floydWarshall() {
int dist[V][V];
for(int i = 0; i < V; i++)
for(int j = 0; j < V; j++)
dist[i][j] = graph[i][j];
for(int k = 0; k < V; k++)
for(int i = 0; i < V; i++)
for(int j = 0; j < V; j++)
if(dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
printf("Floyd-Warshall All-Pairs Shortest Paths:\n");
for(int i = 0; i < V; i++) {
for(int j = 0; j < V; j++) {
if(dist[i][j] == INF) printf("INF ");
else printf("%d ", dist[i][j]);
}
printf("\n");
}
}

86
void dijkstra(int src) {
int dist[V];
int visited[V] = {0};
for(int i = 0; i < V; i++)
dist[i] = INF;
dist[src] = 0;
for(int count = 0; count < V-1; count++) {
int min = INF, u;
for(int i = 0; i < V; i++)
if(!visited[i] && dist[i] <= min) {
min = dist[i];
u = i;
}
visited[u] = 1;
for(int v = 0; v < V; v++)
if(!visited[v] && graph[u][v] != INF &&
dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printf("Dijkstra from vertex %d:\n", src);
for(int i = 0; i < V; i++) {
if(dist[i] == INF) printf("INF ");
else printf("%d ", dist[i]);
}

87
 printf("\n");
}
int main() {
initGraph();
clock_t start, end;
start = clock();
floydWarshall();
end = clock();
double fw_time = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Floyd-Warshall Time: %f seconds\n", fw_time);
start = clock();
for(int i = 0; i < V; i++)
dijkstra(i);
end = clock();
double dj_time = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Dijkstra (all sources) Time: %f seconds\n", dj_time);
return 0;
}

88
Output:
Floyd-Warshall All-Pairs Shortest Paths:
0 1 -3 2 -4
3 0 -4 1 -2
74052
2 -1 -5 0 -3
85160
Floyd-Warshall Time: 0.000054 seconds
Dijkstra from vertex 0:
0 1 -3 2 -4
Dijkstra from vertex 1:
3 0 -4 1 -2
Dijkstra from vertex 2:
74052
Dijkstra from vertex 3:
2 -1 -5 0 -3
Dijkstra from vertex 4:
85160
Dijkstra (all sources) Time: 0.000029 seconds

89
20. Implement Kruskal's algorithm to find the minimum spanning
tree of a graph with 10 vertices and 15 edges, and analyze its
efficiency
#include <stdio.h>
#include <stdlib.h>
#define V 10
#define E 15
typedef struct {
int u, v;
int weight;
} Edge;
typedef struct {
int parent;
int rank;
} Subset;
int find(Subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
void Union(Subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);

90
 if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
int compare(const void* a, const void* b) {
return ((Edge*)a)->weight - ((Edge*)b)->weight;
}
void kruskal(Edge edges[]) {
Edge result[V-1];
int e = 0;
int i = 0;
qsort(edges, E, sizeof(edges[0]), compare);
Subset subsets[V];
for (int v = 0; v < V; v++) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
while (e < V - 1 && i < E) {
Edge next_edge = edges[i++];

91
 int x = find(subsets, next_edge.u);
int y = find(subsets, next_edge.v);
if (x != y) {
result[e++] = next_edge;
Union(subsets, x, y);
}
}
printf("Edges in MST:\n");
int totalWeight = 0;
for (i = 0; i < e; i++) {
printf("%d -- %d == %d\n", result[i].u, result[i].v,
result[i].weight);
totalWeight += result[i].weight;
}
printf("Total weight of MST: %d\n", totalWeight);
}
int main() {
Edge edges[E] = {
{0,1,4}, {0,7,8}, {1,2,8}, {1,7,11}, {2,3,7},
{2,8,2}, {2,5,4}, {3,4,9}, {3,5,14}, {4,5,10},
{5,6,2}, {6,7,1}, {6,8,6}, {7,8,7}, {3,6,9}
};
kruskal(edges);
return 0;

92
}
Output:
Edges in MST:
6 -- 7 == 1
2 -- 8 == 2
5 -- 6 == 2
0 -- 1 == 4
2 -- 5 == 4
2 -- 3 == 7
0 -- 7 == 8
3 -- 4 == 9
Total weight of MST: 37

93
21. Develop Prim's algorithm for minimum spanning trees and
compare its performance with Kruskal's algorithm on a graph
with 10 vertices and 15 edges
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>
#define V 10
#define E 15
#define INF 999999
typedef struct {
int src, dest, weight;
} Edge;
typedef struct {
int parent;
int rank;
} Subset;
int compareEdges(const void *a, const void *b) {
Edge *e1 = (Edge *)a;
Edge *e2 = (Edge *)b;
return e1->weight - e2->weight;
}
int find(Subset subsets[], int x) {
if (subsets[x].parent != x)

94
 subsets[x].parent = find(subsets, subsets[x].parent);
return subsets[x].parent;
}
void unionSet(Subset subsets[], int x, int y) {
int rootX = find(subsets, x);
int rootY = find(subsets, y);
if (subsets[rootX].rank < subsets[rootY].rank)
subsets[rootX].parent = rootY;
else if (subsets[rootX].rank > subsets[rootY].rank)
subsets[rootY].parent = rootX;
else {
subsets[rootY].parent = rootX;
subsets[rootX].rank++;
}
}
void kruskalMST(Edge edges[]) {
Edge result[V];
Subset subsets[V];
for (int v = 0; v < V; v++) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
qsort(edges, E, sizeof(Edge), compareEdges);
int e = 0, i = 0, totalWeight = 0;

95
 printf("\n--- Kruskal's MST ---\n");
while (e < V - 1 && i < E) {
Edge next = edges[i++];
int x = find(subsets, [Link]);
int y = find(subsets, [Link]);
if (x != y) {
result[e++] = next;
totalWeight += [Link];
unionSet(subsets, x, y);
}
}
for (int i = 0; i < e; i++)
printf("%d -- %d \tw=%d\n",
result[i].src, result[i].dest, result[i].weight);
printf("Total weight (Kruskal) = %d\n", totalWeight);
}
int minKey(int key[], int mstSet[]) {
int min = INF, min_index = -1;
for (int v = 0; v < V; v++)
if (!mstSet[v] && key[v] < min) {
min = key[v];
min_index = v;
}
return min_index;

96
}
void primMST(int graph[V][V]) {
int parent[V];
int key[V];
int mstSet[V] = {0};
for (int i = 0; i < V; i++)
key[i] = INF;
key[0] = 0;
parent[0] = -1;
printf("\n--- Prim's MST ---\n");
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = 1;
for (int v = 0; v < V; v++)
if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
int totalWeight = 0;
for (int i = 1; i < V; i++) {
printf("%d -- %d \tw=%d\n",
parent[i], i, graph[i][parent[i]]);
totalWeight += graph[i][parent[i]];

97
 }
printf("Total weight (Prim) = %d\n", totalWeight);
}
int main() {
Edge edges[E] = {
{0, 1, 4}, {0, 7, 8}, {1, 2, 8},
{1, 7, 11}, {2, 3, 7}, {2, 8, 2},
{2, 5, 4}, {3, 4, 9}, {3, 5, 14},
{4, 5, 10}, {5, 6, 2}, {6, 7, 1},
{6, 8, 6}, {7, 8, 7}, {4, 8, 5}
};
int graph[V][V] = {0};
for (int i = 0; i < E; i++) {
int u = edges[i].src;
int v = edges[i].dest;
int w = edges[i].weight;
graph[u][v] = w;
graph[v][u] = w;
}
clock_t start, end;
start = clock();
kruskalMST(edges);
end = clock();
double kruskal_time = (double)(end - start) / CLOCKS_PER_SEC;

98
 start = clock();
primMST(graph);
end = clock();
double prim_time = (double)(end - start) / CLOCKS_PER_SEC;
printf("\n--- Performance Comparison ---\n");
printf("Kruskal Time: %.6f seconds\n", kruskal_time);
printf("Prim Time: %.6f seconds\n", prim_time);
return 0;
}
Output:
--- Kruskal's MST ---
6 -- 7 w=1
2 -- 8 w=2
5 -- 6 w=2
0 -- 1 w=4
2 -- 5 w=4
4 -- 8 w=5
2 -- 3 w=7
0 -- 7 w=8
Total weight (Kruskal) = 33

99
--- Prim's MST ---
0 -- 1 w=4
1 -- 2 w=8
2 -- 3 w=7
8 -- 4 w=5
2 -- 5 w=4
5 -- 6 w=2
6 -- 7 w=1
2 -- 8 w=2
0 -- 9 w=0
Total weight (Prim) = 33
--- Performance Comparison ---
Kruskal Time: 0.000256 seconds
Prim Time: 0.000092 seconds

100
101
102
103
104
105
106
107
108