1: Insertion sort

#include
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("Insertion Sort Result: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf(" \nAnirudh Tripathi : 2401640100185");
return 0;
}
#include
void recursiveInsertionSort(int arr[], int n) {
if (n <= 1)
return;
recursiveInsertionSort(arr, n - 1);
int last = arr[n - 1];
int j = n - 2;
while (j >= 0 && arr[j] > last) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = last;
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
recursiveInsertionSort(arr, n);
printf("Recursive Insertion Sort: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf(" \nAnirudh Tripathi : 2401640100185");
return 0;
}
2:Selection sort
#include
void selectionSort(int arr[], int n) {
int i, j, min_idx;
for (i = 0; i < n - 1; i++) {
min_idx = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx])
min_idx = j;
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
printf("Selection Sort Result: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf(" \nAnirudh Tripathi : 2401640100185");
return 0;
}
#include
int findMinIndex(int arr[], int start, int n) {
if (start == n - 1)
return start;
int min_rest = findMinIndex(arr, start + 1, n);
return (arr[start] < arr[min_rest]) ? start : min_rest;
}
void recursiveSelectionSort(int arr[], int start, int n) {
if (start >= n - 1)
return;
int minIndex = findMinIndex(arr, start, n);
int temp = arr[start];
arr[start] = arr[minIndex];
arr[minIndex] = temp;
recursiveSelectionSort(arr, start + 1, n);
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
recursiveSelectionSort(arr, 0, n);
printf("Recursive Selection Sort: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf(" \nAnirudh Tripathi : 2401640100185");
return 0;
}
3: Bubble Sort
#include
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {5, 1, 4, 2, 8};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Bubble Sort Result: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf(" \nAnirudh Tripathi : 2401640100185");
return 0;
}
#include
void recursiveBubbleSort(int arr[], int n) {
if (n == 1)
return;
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
recursiveBubbleSort(arr, n - 1);
}
int main() {
int arr[] = {5, 1, 4, 2, 8};
int n = sizeof(arr) / sizeof(arr[0]);
recursiveBubbleSort(arr, n);
printf("Recursive Bubble Sort: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf(" \nAnirudh Tripathi : 2401640100185");
return 0;
}
4:Quick Sort
#include
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr;[i], &arr;[j]);
}
}
swap(&arr;[i + 1], &arr;[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Quick Sort Result: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf(" \nAnirudh Tripathi : 2401640100185");
return 0;
}
5: Merge Sort
#include
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int i = 0; i < n2; i++)
R[i] = arr[m + 1 + i];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
printf("Merge Sort Result: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf(" \nAnirudh Tripathi : 2401640100185");
return 0;
}
6: Counting sort
#include
void countingSort(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
int count[max + 1];
for (int i = 0; i <= max; i++)
count[i] = 0;
for (int i = 0; i < n; i++)
count[arr[i]]++;
int index = 0;
for (int i = 0; i <= max; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i] --;
}
}
}
int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
countingSort(arr, n);
printf("Counting Sort Result: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf(" \nAnirudh Tripathi : 2401640100185");
return 0;
}
7: Linear Search
#include
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key)
return i;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 30;
int result = linearSearch(arr, n, key);
if (result != -1)
printf("Element found at index %d \n", result);
else
printf("Element not found \n");
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
#include
int linearSearchRecursive(int arr[], int index, int n, int key) {
if (index == n)
return -1; // element not found
if (arr[index] == key)
return index; // element found
return linearSearchRecursive(arr, index + 1, n, key);
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 40;
int result = linearSearchRecursive(arr, 0, n, key);
if (result != -1)
printf("Element found at index %d \n", result);
else
printf("Element not found \n");
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
8: Binary Search
#include
int binarySearchIterative(int arr[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 40;
int result = binarySearchIterative(arr, n, key);
if (result != -1)
printf("Element found at index %d \n", result);
else
printf("Element not found \n");
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
#include
int binarySearchRecursive(int arr[], int low, int high, int key) {
if (low > high)
return -1;
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
if (key < arr[mid])
return binarySearchRecursive(arr, low, mid - 1, key);
return binarySearchRecursive(arr, mid + 1, high, key);
}
int main() {
int arr[] = {5, 10, 15, 20, 25, 30};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 25;
int result = binarySearchRecursive(arr, 0, n - 1, key);
if (result != -1)
printf("Element found at index %d \n", result);
else
printf("Element not found \n");
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
9: FULL SINGLY LINKED LIST IMPLEMENTATION (C PROGRAM)
#include
#include
struct Node {
int data;
struct Node* next;
};
struct Node* head = NULL;
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode ->data = data;
newNode ->next = NULL;
return newNode;
}
// INSERTION AT BEGINNING
void insertAtBeginning(int data) {
struct Node* newNode = createNode(data);
newNode ->next = head;
head = newNode;
}
// INSERTION AT END
void insertAtEnd(int data) {
struct Node* newNode = createNode(data);
if (head == NULL) {
head = newNode;
return;
}
struct Node* temp = head;
while (temp ->next != NULL)
temp = temp ->next;
temp ->next = newNode;
}
// INSERTION AT ANY POSITION
void insertAtPosition(int data, int pos) {
struct Node* newNode = createNode(data);
if (pos == 1) {
newNode ->next = head;
head = newNode;
return;
}
struct Node* temp = head;
for (int i = 1; i < pos - 1 && temp != NULL; i++)
temp = temp ->next;
if (temp == NULL) {
printf("Position out of range! \n");
return;
}
newNode ->next = temp ->next;
temp ->next = newNode;
}
// DELETION AT BEGINNING
void deleteAtBeginning() {
if (head == NULL) {
printf("List is empty! \n");
return;
}
struct Node* temp = head;
head = head ->next;
free(temp);
}
// DELETION AT END
void deleteAtEnd() {
if (head == NULL) {
printf("List is empty! \n");
return;
}
if (head ->next == NULL) {
free(head);
head = NULL;
return;
}
struct Node* temp = head;
while (temp ->next ->next != NULL)
temp = temp ->next;
free(temp ->next);
temp ->next = NULL;
}
// DELETION AT ANY POSITION
void deleteAtPosition(int pos) {
if (head == NULL) {
printf("List is empty! \n");
return;
}
struct Node* temp = head;
if (pos == 1) {
head = head ->next;
free(temp);
return;
}
for (int i = 1; i < pos - 1 && temp != NULL; i++)
temp = temp ->next;
if (temp == NULL || temp ->next == NULL) {
printf("Position out of range! \n");
return;
}
struct Node* del = temp ->next;
temp ->next = del ->next;
free(del);
}
// TRAVERSAL (FORWARD)
void traverse() {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp ->data);
temp = temp ->next;
}
printf("NULL \n");
}
// TRAVERSAL IN REVERSE ORDER (RECURSIVE)
void traverseReverse(struct Node* node) {
if (node == NULL)
return;
traverseReverse(node ->next);
printf("%d -> ", node ->data);
}
// SEARCHING AN ELEMENT
void search(int key) {
struct Node* temp = head;
int pos = 1;
while (temp != NULL) {
if (temp ->data == key) {
printf("Element %d found at position %d \n", key, pos);
return;
}
temp = temp ->next;
pos++;
}
printf("Element %d not found in the list. \n", key);
}
// MAIN FUNCTION
int main() {
insertAtBeginning(30);
insertAtBeginning(20);
insertAtBeginning(10);
insertAtEnd(40);
insertAtEnd(50);
insertAtPosition(25, 3); // Insert at position 3
printf("Traversal (Forward): ");
traverse();
printf("Traversal (Reverse): ");
traverseReverse(head);
printf("NULL \n");
search(40);
search(100);
deleteAtBeginning();
deleteAtEnd();
deleteAtPosition(2);
printf(" \nList after deletions: ");
traverse();
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
10: CIRCULAR LINKED LIST (SINGLY)
#include
#include
struct Node {
int data;
struct Node* next;
};
struct Node* head = NULL;
// Create node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode ->data = data;
newNode ->next = NULL;
return newNode;
}
// INSERT AT BEGINNING
void insertAtBeginning(int data) {
struct Node* newNode = createNode(data);
if (head == NULL) {
head = newNode;
head ->next = head;
return;
}
struct Node* temp = head;
while (temp ->next != head)
temp = temp ->next;
newNode ->next = head;
temp ->next = newNode;
head = newNode;
}
// INSERT AT END
void insertAtEnd(int data) {
struct Node* newNode = createNode(data);
if (head == NULL) {
head = newNode;
head ->next = head;
return;
}
struct Node* temp = head;
while (temp ->next != head)
temp = temp ->next;
temp ->next = newNode;
newNode ->next = head;
}
// INSERT AT POSITION
void insertAtPosition(int data, int pos) {
if (pos == 1) {
insertAtBeginning(data);
return;
}
struct Node* newNode = createNode(data);
struct Node* temp = head;
for (int i = 1; i < pos - 1 && temp ->next != head; i++)
temp = temp ->next;
newNode ->next = temp ->next;
temp ->next = newNode;
}
// DELETE AT BEGINNING
void deleteAtBeginning() {
if (head == NULL)
return;
if (head ->next == head) {
free(head);
head = NULL;
return;
}
struct Node* temp = head, *last = head;
while (last ->next != head)
last = last ->next;
head = head ->next;
last->next = head;
free(temp);
}
// DELETE AT END
void deleteAtEnd() {
if (head == NULL)
return;
if (head ->next == head) {
free(head);
head = NULL;
return;
}
struct Node* temp = head;
while (temp ->next ->next != head)
temp = temp ->next;
struct Node* last = temp ->next;
temp ->next = head;
free(last);
}
// DELETE AT POSITION
void deleteAtPosition(int pos) {
if (head == NULL)
return;
if (pos == 1) {
deleteAtBeginning();
return;
}
struct Node* temp = head;
for (int i = 1; i < pos - 1 && temp ->next != head; i++)
temp = temp ->next;
struct Node* del = temp ->next;
temp ->next = del ->next;
free(del);
}
// TRAVERSAL
void traverse() {
if (head == NULL) {
printf("List is empty \n");
return;
}
struct Node* temp = head;
do {
printf("%d -> ", temp ->data);
temp = temp ->next;
} while (temp != head);
printf("(HEAD) \n");
}
int main() {
insertAtBeginning(20);
insertAtBeginning(10);
insertAtEnd(30);
insertAtPosition(25, 3);
printf("Circular Linked List Traversal: ");
traverse();
deleteAtBeginning();
deleteAtEnd();
deleteAtPosition(2);
printf("After Deletions: ");
traverse();
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
11: DOUBLY LINKED LIST
#include
#include
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
struct Node* head = NULL;
// Create node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode ->data = data;
newNode ->prev = NULL;
newNode ->next = NULL;
return newNode;
}
// INSERT AT BEGINNING
void insertAtBeginning(int data) {
struct Node* newNode = createNode(data);
newNode ->next = head;
if (head != NULL)
head ->prev = newNode;
head = newNode;
}
// INSERT AT END
void insertAtEnd(int data) {
struct Node* newNode = createNode(data);
if (head == NULL) {
head = newNode;
return;
}
struct Node* temp = head;
while (temp ->next != NULL)
temp = temp ->next;
temp ->next = newNode;
newNode ->prev = temp;
}
// INSERT AT POSITION
void insertAtPosition(int data, int pos) {
if (pos == 1) {
insertAtBeginning(data);
return;
}
struct Node* newNode = createNode(data);
struct Node* temp = head;
for (int i = 1; i < pos - 1 && temp != NULL; i++)
temp = temp ->next;
if (temp == NULL) {
printf("Position out of range! \n");
return;
}
newNode ->next = temp ->next;
newNode ->prev = temp;
if (temp ->next != NULL)
temp ->next ->prev = newNode;
temp ->next = newNode;
}
// DELETE AT BEGINNING
void deleteAtBeginning() {
if (head == NULL)
return;
struct Node* temp = head;
head = head ->next;
if (head != NULL)
head ->prev = NULL;
free(temp);
}
// DELETE AT END
void deleteAtEnd() {
if (head == NULL)
return;
struct Node* temp = head;
if (temp ->next == NULL) {
free(head);
head = NULL;
return;
}
while (temp ->next != NULL)
temp = temp ->next;
temp ->prev ->next = NULL;
free(temp);
}
// DELETE AT POSITION
void deleteAtPosition(int pos) {
if (head == NULL)
return;
struct Node* temp = head;
if (pos == 1) {
deleteAtBeginning();
return;
}
for (int i = 1; i < pos && temp != NULL; i++)
temp = temp ->next;
if (temp == NULL) {
printf("Position out of range! \n");
return;
}
if (temp ->prev != NULL)
temp ->prev ->next = temp ->next;
if (temp ->next != NULL)
temp ->next ->prev = temp ->prev;
free(temp);
}
// TRAVERSAL FORWARD
void traverseForward() {
struct Node* temp = head;
while (temp != NULL) {
printf("%d < -> ", temp ->data);
temp = temp ->next;
}
printf("NULL \n");
}
// TRAVERSAL BACKWARD
void traverseBackward() {
if (head == NULL) {
printf("List is empty \n");
return;
}
struct Node* temp = head;
while (temp ->next != NULL)
temp = temp ->next;
while (temp != NULL) {
printf("%d < -> ", temp ->data);
temp = temp ->prev;
}
printf("NULL \n");
}
int main() {
insertAtBeginning(20);
insertAtBeginning(10);
insertAtEnd(30);
insertAtPosition(25, 3);
printf("Forward Traversal: ");
traverseForward();
printf("Backward Traversal: ");
traverseBackward();
deleteAtBeginning();
deleteAtEnd();
deleteAtPosition(2);
printf(" \nAfter Deletions (Forward): ");
traverseForward();
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
12: Polynomial Addition
#include
#include
struct PolyNode {
int coeff, power;
struct PolyNode* next;
};
struct PolyNode* createNode(int coeff, int power) {
struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));
newNode ->coeff = coeff;
newNode ->power = power;
newNode ->next = NULL;
return newNode;
}
void insertTerm(struct PolyNode** poly, int coeff, int power) {
struct PolyNode* newNode = createNode(coeff, power);
if (*poly == NULL || (*poly) ->power < power) {
newNode ->next = *poly;
*poly = newNode;
return;
}
struct PolyNode* temp = *poly;
while (temp ->next != NULL && temp ->next ->power > power) {
temp = temp ->next;
}
if (temp ->next != NULL && temp ->next ->power == power) {
temp ->next ->coeff += coeff;
} else {
newNode ->next = temp ->next;
temp ->next = newNode;
}
}
void displayPoly(struct PolyNode* poly) {
if (poly == NULL) {
printf("0 \n");
return;
}
while (poly != NULL) {
printf("%dx^%d", poly ->coeff, poly ->power);
poly = poly ->next;
if (poly != NULL)
printf(" + ");
}
printf(" \n");
}
struct PolyNode* addPoly(struct PolyNode* p1, struct PolyNode* p2) {
struct PolyNode* result = NULL;
while (p1 != NULL && p2 != NULL) {
if (p1 ->power > p2 ->power) {
insertTerm(&result;, p1 ->coeff, p1 ->power);
p1 = p1 ->next;
}
else if (p1 ->power < p2 ->power) {
insertTerm(&result;, p2 ->coeff, p2 ->power);
p2 = p2 ->next;
}
else {
insertTerm(&result;, p1 ->coeff + p2 ->coeff, p1 ->power);
p1 = p1 ->next;
p2 = p2 ->next;
}
}
while (p1 != NULL) {
insertTerm(&result;, p1 ->coeff, p1 ->power);
p1 = p1 ->next;
}
while (p2 != NULL) {
insertTerm(&result;, p2 ->coeff, p2 ->power);
p2 = p2 ->next;
}
return result;
}
int main() {
struct PolyNode *poly1 = NULL, *poly2 = NULL, *sum = NULL;
insertTerm(&poly1;, 3, 3);
insertTerm(&poly1;, 2, 1);
insertTerm(&poly1;, 1, 0);
insertTerm(&poly2;, 4, 2);
insertTerm(&poly2;, 3, 1);
insertTerm(&poly2;, 2, 0);
printf("Polynomial 1: ");
displayPoly(poly1);
printf("Polynomial 2: ");
displayPoly(poly2);
sum = addPoly(poly1, poly2);
printf("Sum: ");
displayPoly(sum);
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
13: Merging Two Sorted Linked Lists
#include
#include
struct Node {
int data;
struct Node* next;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode ->data = data;
newNode ->next = NULL;
return newNode;
}
void insertEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp ->next != NULL)
temp = temp ->next;
temp ->next = newNode;
}
void display(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head ->data);
head = head ->next;
}
printf("NULL \n");
}
struct Node* mergeLists(struct Node* l1, struct Node* l2) {
struct Node* result = NULL;
struct Node* tail = NULL;
while (l1 != NULL && l2 != NULL) {
struct Node* temp;
if (l1 ->data <= l2 ->data) {
temp = l1;
l1 = l1 ->next;
} else {
temp = l2;
l2 = l2 ->next;
}
if (result == NULL) {
result = temp;
tail = temp;
} else {
tail->next = temp;
tail = temp;
}
}
if (l1 != NULL) tail ->next = l1;
if (l2 != NULL) tail ->next = l2;
return result;
}
int main() {
struct Node *list1 = NULL, *list2 = NULL, *merged = NULL;
insertEnd(&list1;, 1);
insertEnd(&list1;, 3);
insertEnd(&list1;, 5);
insertEnd(&list2;, 2);
insertEnd(&list2;, 4);
insertEnd(&list2;, 6);
printf("List 1: ");
display(list1);
printf("List 2: ");
display(list2);
merged = mergeLists(list1, list2);
printf("Merged List: ");
display(merged);
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
14: STACK IMPLEMENTATION USING ARRAY
#include
#include
#define MAX 100
int stack[MAX];
int top = -1;
void push(int value) {
if (top == MAX - 1) {
printf("Stack Overflow! \n");
return;
}
stack[++top] = value;
}
int pop() {
if (top == -1) {
printf("Stack Underflow! \n");
return -1;
}
return stack[top --];
}
int peek() {
if (top == -1) {
printf("Stack is Empty! \n");
return -1;
}
return stack[top];
}
void display() {
if (top == -1) {
printf("Stack is Empty! \n");
return;
}
for (int i = top; i >= 0; i --)
printf("%d ", stack[i]);
printf(" \n");
}
int main() {
push(10);
push(20);
push(30);
printf("Stack elements: ");
display();
printf("Popped: %d \n", pop());
printf("Peek: %d \n", peek());
printf("Stack after operations: ");
display();
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
15: STACK IMPLEMENTATION USING LINKED LIST
#include
#include
struct Node {
int data;
struct Node* next;
};
struct Node* top = NULL;
void push(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode ->data = value;
newNode ->next = top;
top = newNode;
}
int pop() {
if (top == NULL) {
printf("Stack Underflow! \n");
return -1;
}
struct Node* temp = top;
int x = temp ->data;
top = top ->next;
free(temp);
return x;
}
int peek() {
if (top == NULL) {
printf("Stack is Empty! \n");
return -1;
}
return top ->data;
}
void display() {
struct Node* temp = top;
if (temp == NULL) {
printf("Stack is Empty! \n");
return;
}
while (temp != NULL) {
printf("%d ", temp ->data);
temp = temp ->next;
}
printf(" \n");
}
int main() {
push(5);
push(15);
push(25);
printf("Stack elements: ");
display();
printf("Popped: %d \n", pop());
printf("Peek: %d \n", peek());
printf("Stack after operations: ");
display();
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
16: INFIX TO POSTFIX USING STACK
#include
#include
#include
#define MAX 100
char stack[MAX];
int top = -1;
void push(char x) {
stack[++top] = x;
}
char pop() {
if (top == -1) return -1;
return stack[top --];
}
int precedence(char x) {
if (x == '(') return 0;
if (x == '+' || x == ' -') return 1;
if (x == '*' || x == '/' || x == '%') return 2;
return 0;
}
int main() {
char infix[100], postfix[100], ch;
int i = 0, j = 0;
printf("Enter infix expression: ");
scanf("%s", infix);
while ((ch = infix[i++]) != ' \0') {
if (isalnum(ch))
postfix[j++] = ch;
else if (ch == '(')
push(ch);
else if (ch == ')') {
while ((ch = pop()) != '(')
postfix[j++] = ch;
}
else {
while (precedence(stack[top]) >= precedence(ch))
postfix[j++] = pop();
push(ch);
}
}
while (top != -1)
postfix[j++] = pop();
postfix[j] = ' \0';
printf("Postfix Expression: %s \n", postfix);
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
17: POSTFIX EXPRESSION EVALUATION USING STACK
#include
#include
#define MAX 100
int stack[MAX];
int top = -1;
void push(int x) {
stack[++top] = x;
}
int pop() {
return stack[top --];
}
int main() {
char postfix[100];
int i = 0, a, b, result;
printf("Enter postfix expression: ");
scanf("%s", postfix);
while (postfix[i] != ' \0') {
if (isdigit(postfix[i])) {
push(postfix[i] - '0');
} else {
b = pop();
a = pop();
switch (postfix[i]) {
case '+': result = a + b; break;
case ' -': result = a - b; break;
case '*': result = a * b; break;
case '/': result = a / b; break;
}
push(result);
}
i++;
}
printf("Evaluated Result: %d \n", pop());
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
18: PARENTHESIS BALANCING USING STACK
#include
#include
#define MAX 100
char stack[MAX];
int top = -1;
void push(char x) {
stack[++top] = x;
}
char pop() {
if (top == -1) return -1;
return stack[top --];
}
int match(char a, char b) {
if (a == '(' && b == ')') return 1;
if (a == '{' && b == '}') return 1;
if (a == '[' && b == ']') return 1;
return 0;
}
int main() {
char exp[100], temp;
int i;
printf("Enter expression: ");
scanf("%s", exp);
for (i = 0; i < strlen(exp); i++) {
if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
push(exp[i]);
else if (exp[i] == ')' || exp[i] == '}' || exp[i] == ']') {
temp = pop();
if (!match(temp, exp[i])) {
printf("Not Balanced \n");
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
}
}
if (top == -1)
printf("Balanced Expression \n");
else
printf("Not Balanced \n");
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
19: Towers of Hanoi Program (Recursive)
#include
void towerOfHanoi(int n, char source, char auxiliary, char destination) {
if (n == 1) {
printf("Move disk 1 from %c to %c \n", source, destination);
return;
}
towerOfHanoi(n - 1, source, destination, auxiliary);
printf("Move disk %d from %c to %c \n", n, source, destination);
towerOfHanoi(n - 1, auxiliary, source, destination);
}
int main() {
int n;
printf("Enter number of disks: ");
scanf("%d", &n;);
printf(" \nSteps to solve Towers of Hanoi: \n");
towerOfHanoi(n, 'A', 'B', 'C');
printf(" \nAnirudh Tripathi : 2401640100185");
return 0;
}
20: LINEAR QUEUE USING ARRAY
#include
#include
#define MAX 100
int queue[MAX];
int front = -1, rear = -1;
void enqueue(int value) {
if (rear == MAX - 1) {
printf("Queue Overflow! \n");
return;
}
if (front == -1)
front = 0;
queue[++rear] = value;
}
int dequeue() {
if (front == -1 || front > rear) {
printf("Queue Underflow! \n");
return -1;
}
return queue[front++];
}
int peek() {
if (front == -1 || front > rear) {
printf("Queue is Empty! \n");
return -1;
}
return queue[front];
}
void display() {
if (front == -1 || front > rear) {
printf("Queue is Empty! \n");
return;
}
for (int i = front; i <= rear; i++)
printf("%d ", queue[i]);
printf(" \n");
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
printf("Queue elements: ");
display();
printf("Dequeued: %d \n", dequeue());
printf("Peek: %d \n", peek());
printf("Queue after operations: ");
display();
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
21: LINEAR QUEUE USING LINKED LIST
#include
#include
struct Node {
int data;
struct Node* next;
};
struct Node *front = NULL, *rear = NULL;
void enqueue(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode ->data = value;
newNode ->next = NULL;
if (rear == NULL) {
front = rear = newNode;
return;
}
rear->next = newNode;
rear = newNode;
}
int dequeue() {
if (front == NULL) {
printf("Queue Underflow! \n");
return -1;
}
struct Node* temp = front;
int val = temp ->data;
front = front ->next;
if (front == NULL)
rear = NULL;
free(temp);
return val;
}
int peek() {
if (front == NULL) {
printf("Queue is Empty! \n");
return -1;
}
return front ->data;
}
void display() {
struct Node* temp = front;
if (temp == NULL) {
printf("Queue is Empty! \n");
return;
}
while (temp != NULL) {
printf("%d ", temp ->data);
temp = temp ->next;
}
printf(" \n");
}
int main() {
enqueue(5);
enqueue(15);
enqueue(25);
printf("Queue elements: ");
display();
printf("Dequeued: %d \n", dequeue());
printf("Peek: %d \n", peek());
printf("Queue after operations: ");
display();
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
22: CIRCULAR QUEUE USING ARRAY
#include
#include
#define MAX 5
int cqueue[MAX];
int front = -1, rear = -1;
void enqueue(int value) {
if ((front == 0 && rear == MAX - 1) || (rear + 1) % MAX == front) {
printf("Circular Queue Overflow! \n");
return;
}
if (front == -1)
front = rear = 0;
else
rear = (rear + 1) % MAX;
cqueue[rear] = value;
}
int dequeue() {
if (front == -1) {
printf("Circular Queue Underflow! \n");
return -1;
}
int val = cqueue[front];
if (front == rear)
front = rear = -1;
else
front = (front + 1) % MAX;
return val;
}
void display() {
if (front == -1) {
printf("Circular Queue is Empty! \n");
return;
}
int i = front;
while (1) {
printf("%d ", cqueue[i]);
if (i == rear) break;
i = (i + 1) % MAX;
}
printf(" \n");
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50);
printf("Circular Queue: ");
display();
printf("Dequeued: %d \n", dequeue());
printf("After Dequeue: ");
display();
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
23: DOUBLE ENDED QUEUE (DEQUE) USING ARRAY
#include
#include
#define MAX 5
int deque[MAX];
int front = -1, rear = -1;
void insertFront(int x) {
if ((front == 0 && rear == MAX - 1) || (front - 1 == rear)) {
printf("DEQUE Overflow! \n");
return;
}
if (front == -1)
front = rear = 0;
else if (front == 0)
front = MAX - 1;
else
front --;
deque[front] = x;
}
void insertRear(int x) {
if ((front == 0 && rear == MAX - 1) || (rear + 1 == front)) {
printf("DEQUE Overflow! \n");
return;
}
if (front == -1)
front = rear = 0;
else if (rear == MAX - 1)
rear = 0;
else
rear++;
deque[rear] = x;
}
int deleteFront() {
if (front == -1) {
printf("DEQUE Underflow! \n");
return -1;
}
int val = deque[front];
if (front == rear)
front = rear = -1;
else if (front == MAX - 1)
front = 0;
else
front++;
return val;
}
int deleteRear() {
if (rear == -1) {
printf("DEQUE Underflow! \n");
return -1;
}
int val = deque[rear];
if (front == rear)
front = rear = -1;
else if (rear == 0)
rear = MAX - 1;
else
rear--;
return val;
}
void display() {
if (front == -1) {
printf("DEQUE is Empty! \n");
return;
}
int i = front;
while (1) {
printf("%d ", deque[i]);
if (i == rear) break;
i = (i + 1) % MAX;
}
printf(" \n");
}
int main() {
insertRear(10);
insertRear(20);
insertFront(5);
insertFront(2);
printf("DEQUE: ");
display();
printf("Deleted from Rear: %d \n", deleteRear());
printf("Deleted from Front: %d \n", deleteFront());
printf("After Deletions: ");
display();
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
24: PRIORITY QUEUE USING ARRAY (Ascending Priority)
#include
#include
#define MAX 100
int pqueue[MAX];
int size = 0;
void insert(int value) {
if (size == MAX) {
printf("Priority Queue Overflow! \n");
return;
}
int i = size - 1;
while (i >= 0 && pqueue[i] > value) {
pqueue[i + 1] = pqueue[i];
i--;
}
pqueue[i + 1] = value;
size++;
}
int delete() {
if (size == 0) {
printf("Priority Queue Underflow! \n");
return -1;
}
int val = pqueue[0];
for (int i = 1; i < size; i++)
pqueue[i - 1] = pqueue[i];
size--;
return val;
}
void display() {
if (size == 0) {
printf("Priority Queue is Empty! \n");
return;
}
for (int i = 0; i < size; i++)
printf("%d ", pqueue[i]);
printf(" \n");
}
int main() {
insert(30);
insert(10);
insert(20);
insert(5);
printf("Priority Queue: ");
display();
printf("Deleted (Highest Priority): %d \n", delete());
printf("After Deletion: ");
display();
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
25: FULL BST IMPLEMENTATION IN C
#include
#include
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Create new node
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode ->data = value;
newNode ->left = newNode ->right = NULL;
return newNode;
}
// Insert a node in BST
struct Node* insert(struct Node* root, int value) {
if (root == NULL)
return createNode(value);
if (value < root ->data)
root ->left = insert(root ->left, value);
else
root ->right = insert(root ->right, value);
return root;
}
// Find minimum value in BST
struct Node* findMin(struct Node* root) {
while (root ->left != NULL)
root = root ->left;
return root;
}
// Delete a node
struct Node* deleteNode(struct Node* root, int value) {
if (root == NULL)
return root;
if (value < root ->data)
root ->left = deleteNode(root ->left, value);
else if (value > root ->data)
root ->right = deleteNode(root ->right, value);
else {
// Case 1: No child
if (root ->left == NULL && root ->right == NULL)
return NULL;
// Case 2: One child
else if (root ->left == NULL)
return root ->right;
else if (root ->right == NULL)
return root ->left;
// Case 3: Two children
struct Node* temp = findMin(root ->right);
root ->data = temp ->data;
root ->right = deleteNode(root ->right, temp ->data);
}
return root;
}
// Traversals
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root ->left);
printf("%d ", root ->data);
inorder(root ->right);
}
}
void preorder(struct Node* root) {
if (root != NULL) {
printf("%d ", root ->data);
preorder(root ->left);
preorder(root ->right);
}
}
void postorder(struct Node* root) {
if (root != NULL) {
postorder(root ->left);
postorder(root ->right);
printf("%d ", root ->data);
}
}
// Count total nodes
int countNodes(struct Node* root) {
if (root == NULL) return 0;
return 1 + countNodes(root ->left) + countNodes(root ->right);
}
// Count internal nodes
int countInternal(struct Node* root) {
if (root == NULL || (root ->left == NULL && root ->right == NULL))
return 0;
return 1 + countInternal(root ->left) + countInternal(root ->right);
}
// Count external (leaf) nodes
int countExternal(struct Node* root) {
if (root == NULL)
return 0;
if (root ->left == NULL && root ->right == NULL)
return 1;
return countExternal(root ->left) + countExternal(root ->right);
}
// Height of tree
int height(struct Node* root) {
if (root == NULL)
return -1;
int left_h = height(root ->left);
int right_h = height(root ->right);
return (left_h > right_h ? left_h : right_h) + 1;
}
// Find smallest node
int findSmallest(struct Node* root) {
while (root ->left != NULL)
root = root ->left;
return root ->data;
}
// Find largest node
int findLargest(struct Node* root) {
while (root ->right != NULL)
root = root ->right;
return root ->data;
}
int main() {
struct Node* root = NULL;
// Creating BST
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);
printf("Inorder Traversal: ");
inorder(root);
printf(" \n");
printf("Preorder Traversal: ");
preorder(root);
printf(" \n");
printf("Postorder Traversal: ");
postorder(root);
printf(" \n");
printf("Total Nodes: %d \n", countNodes(root));
printf("Internal Nodes: %d \n", countInternal(root));
printf("External Nodes: %d \n", countExternal(root));
printf("Height of Tree: %d \n", height(root));
printf("Smallest Node: %d \n", findSmallest(root));
printf("Largest Node: %d \n", findLargest(root));
// Deleting node 30
root = deleteNode(root, 30);
printf("After deleting 30 (Inorder): ");
inorder(root);
printf(" \n");
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
26: COMBINED MAX HEAP + MIN HEAP WITH ASSIGNMENT LINE
#include
#define MAX 50
int heap[MAX];
int size = 0;
/* ================================
MAX HEAP FUNCTIONS
================================ */
// Reheap Up (Max Heap)
void maxReheapUp(int index) {
int parent = (index - 1) / 2;
if (index > 0 && heap[index] > heap[parent]) {
int temp = heap[index];
heap[index] = heap[parent];
heap[parent] = temp;
maxReheapUp(parent);
}
}
// Reheap Down (Max Heap)
void maxReheapDown(int index) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int largest = index;
if (left < size && heap[left] > heap[largest])
largest = left;
if (right < size && heap[right] > heap[largest])
largest = right;
if (largest != index) {
int temp = heap[index];
heap[index] = heap[largest];
heap[largest] = temp;
maxReheapDown(largest);
}
}
// Insert into Max Heap
void insertMax(int value) {
if (size == MAX) {
printf("Heap is full! \n");
return;
}
heap[size] = value;
maxReheapUp(size);
size++;
}
// Delete root of Max Heap
int deleteMax() {
if (size <= 0) {
printf("Heap is empty! \n");
return -1;
}
int root = heap[0];
heap[0] = heap[size - 1];
size--;
maxReheapDown(0);
return root;
}
// Build Max Heap
void buildMaxHeap(int arr[], int n) {
size = n;
for (int i = 0; i < n; i++)
heap[i] = arr[i];
for (int i = size / 2 - 1; i >= 0; i --)
maxReheapDown(i);
}
/* ================================
MIN HEAP FUNCTIONS
================================ */
// Reheap Up (Min Heap)
void minReheapUp(int index) {
int parent = (index - 1) / 2;
if (index > 0 && heap[index] < heap[parent]) {
int temp = heap[index];
heap[index] = heap[parent];
heap[parent] = temp;
minReheapUp(parent);
}
}
// Reheap Down (Min Heap)
void minReheapDown(int index) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int smallest = index;
if (left < size && heap[left] < heap[smallest])
smallest = left;
if (right < size && heap[right] < heap[smallest])
smallest = right;
if (smallest != index) {
int temp = heap[index];
heap[index] = heap[smallest];
heap[smallest] = temp;
minReheapDown(smallest);
}
}
// Insert into Min Heap
void insertMin(int value) {
if (size == MAX) {
printf("Heap is full! \n");
return;
}
heap[size] = value;
minReheapUp(size);
size++;
}
// Delete root of Min Heap
int deleteMin() {
if (size <= 0) {
printf("Heap is empty! \n");
return -1;
}
int root = heap[0];
heap[0] = heap[size - 1];
size--;
minReheapDown(0);
return root;
}
// Build Min Heap
void buildMinHeap(int arr[], int n) {
size = n;
for (int i = 0; i < n; i++)
heap[i] = arr[i];
for (int i = size / 2 - 1; i >= 0; i --)
minReheapDown(i);
}
/* ================================
HEAP SORT USING MAX HEAP
================================ */
void heapSort() {
int tempSize = size;
for (int i = tempSize - 1; i >= 0; i --) {
int temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
size--;
maxReheapDown(0);
}
size = tempSize;
}
/* ================================
MAIN
================================ */
int main() {
int n, arr[MAX];
printf("Enter number of elements: ");
scanf("%d", &n;);
printf("Enter elements: \n");
for (int i = 0; i < n; i++)
scanf("%d", &arr;[i]);
/* ---------- MAX HEAP ---------- */
buildMaxHeap(arr, n);
printf(" \nMax Heap: ");
for (int i = 0; i < size; i++)
printf("%d ", heap[i]);
heapSort();
printf(" \nSorted Array: ");
for (int i = 0; i < size; i++)
printf("%d ", heap[i]);
/* ---------- MIN HEAP DEMO ---------- */
buildMinHeap(arr, n);
printf(" \n\nMin Heap: ");
for (int i = 0; i < size; i++)
printf("%d ", heap[i]);
/* ---------- ASSIGNMENT LINE ---------- */
printf(" \n\nAnirudh Tripathi : 2401640100185");
return 0;
}
27: Graph Traversal: BFS & DFS (C Program)
#include
#include
#define MAX 100
int visited[MAX]; // For DFS
// Queue for BFS
int queue[MAX];
int front = -1, rear = -1;
void enqueue(int v) {
queue[++rear] = v;
if (front == -1) front = 0;
}
int dequeue() {
if (front == -1) return -1;
int val = queue[front];
if (front == rear) front = rear = -1;
else front++;
return val;
}
int isEmpty() {
return front == -1;
}
// BFS function
void BFS(int n, int adj[n][n], int start) {
int visitedBFS[n];
for (int i = 0; i < n; i++) visitedBFS[i] = 0;
enqueue(start);
visitedBFS[start] = 1;
printf("BFS Traversal: ");
while (!isEmpty()) {
int u = dequeue();
printf("%d ", u);
for (int v = 0; v < n; v++) {
if (adj[u][v] && !visitedBFS[v]) {
enqueue(v);
visitedBFS[v] = 1;
}
}
}
printf(" \n");
}
// DFS function (recursive)
void DFS(int n, int adj[n][n], int v) {
visited[v] = 1;
printf("%d ", v);
for (int i = 0; i < n; i++) {
if (adj[v][i] && !visited[i])
DFS(n, adj, i);
}
}
int main() {
int n, e;
printf("Enter number of vertices: ");
scanf("%d", &n;);
printf("Enter number of edges: ");
scanf("%d", &e;);
int adj[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
adj[i][j] = 0;
printf("Enter edges (u v): \n");
for (int i = 0; i < e; i++) {
int u, v;
scanf("%d %d", &u;, &v;);
adj[u][v] = 1;
adj[v][u] = 1; // For undirected graph
}
// BFS
BFS(n, adj, 0);
// DFS
for (int i = 0; i < n; i++) visited[i] = 0;
printf("DFS Traversal: ");
DFS(n, adj, 0);
printf(" \n");
// Assignment line
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
28: PRIM’S ALGORITHM (C Program)
#include
#include
#define MAX 100
int main() {
int n;
printf("Enter number of vertices: ");
scanf("%d", &n;);
int graph[MAX][MAX];
printf("Enter adjacency matrix (use 0 if no edge): \n");
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &graph;[i][j]);
int parent[n]; // Stores MST
int key[n]; // Key values to pick minimum weight edge
int mstSet[n]; // To represent set of vertices included in MST
for (int i = 0; i < n; i++) {
key[i] = INT_MAX;
mstSet[i] = 0;
}
key[0] = 0; // Start from first vertex
parent[0] = -1; // First node is root
for (int count = 0; count < n - 1; count++) {
int min = INT_MAX, u;
for (int v = 0; v < n; v++)
if (!mstSet[v] && key[v] < min) {
min = key[v];
u = v;
}
mstSet[u] = 1;
for (int v = 0; v < n; v++)
if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
printf("Edge \tWeight \n");
for (int i = 1; i < n; i++)
printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
29: KRUSKAL’S ALGORITHM (C Program)
#include
#include
#define MAX 100
struct Edge {
int u, v, weight;
};
int parent[MAX];
// Find function for union -find
int find(int i) {
while (parent[i] != i)
i = parent[i];
return i;
}
// Union function
void unionSet(int i, int j) {
int a = find(i);
int b = find(j);
parent[a] = b;
}
// Comparator for sorting edges
int compare(const void* a, const void* b) {
struct Edge* e1 = (struct Edge*)a;
struct Edge* e2 = (struct Edge*)b;
return e1 ->weight - e2->weight;
}
int main() {
int n, e;
printf("Enter number of vertices: ");
scanf("%d", &n;);
printf("Enter number of edges: ");
scanf("%d", &e;);
struct Edge edges[e];
printf("Enter edges (u v weight): \n");
for (int i = 0; i < e; i++)
scanf("%d %d %d", &edges;[i].u, &edges;[i].v, &edges;[i].weight);
// Initialize parent array
for (int i = 0; i < n; i++)
parent[i] = i;
// Sort edges based on weight
qsort(edges, e, sizeof(struct Edge), compare);
printf("Edges in MST: \n");
int count = 0;
for (int i = 0; i < e && count < n - 1; i++) {
int u = edges[i].u;
int v = edges[i].v;
int set_u = find(u);
int set_v = find(v);
if (set_u != set_v) {
printf("%d - %d \t%d\n", u, v, edges[i].weight);
unionSet(set_u, set_v);
count++;
}
}
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
30 : DIJKSTRA’S ALGORITHM
#include
#include
#define MAX 100
int minDistance(int dist[], int sptSet[], int n) {
int min = INT_MAX, min_index;
for (int v = 0; v < n; v++)
if (!sptSet[v] && dist[v] <= min) {
min = dist[v];
min_index = v;
}
return min_index;
}
void dijkstra(int n, int graph[n][n], int src) {
int dist[n]; // Shortest distances
int sptSet[n]; // Visited vertices
for (int i = 0; i < n; i++) {
dist[i] = INT_MAX;
sptSet[i] = 0;
}
dist[src] = 0;
for (int count = 0; count < n - 1; count++) {
int u = minDistance(dist, sptSet, n);
sptSet[u] = 1;
for (int v = 0; v < n; v++)
if (!sptSet[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 < n; i++)
printf("%d \t%d\n", i, dist[i]);
}
int main() {
int n;
printf("Enter number of vertices: ");
scanf("%d", &n;);
int graph[n][n];
printf("Enter adjacency matrix (0 if no edge): \n");
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &graph;[i][j]);
int src;
printf("Enter source vertex: ");
scanf("%d", &src;);
dijkstra(n, graph, src);
printf("Anirudh Tripathi : 2401640100185");
return 0;
}
31: FLOYD -WARSHALL ALGORITHM
#include
#define MAX 100
#define INF 99999
int main() {
int n;
printf("Enter number of vertices: ");
scanf("%d", &n;);
int dist[n][n];
printf("Enter adjacency matrix (use 0 if no edge): \n");
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
scanf("%d", &dist;[i][j]);
if (i != j && dist[i][j] == 0)
dist[i][j] = INF;
}
// Floyd -Warshall algorithm
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
printf("Shortest distances between every pair of vertices: \n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] == INF)
printf("INF ");
else
printf("%d ", dist[i][j]);
}
printf(" \n");
}
printf("Anirudh Tripathi : 2401640100185");
return 0;
}