Data Structures and Algorithms Lab REG.

NO: 24MCA306

PART - A

Program No: 1
Program statement: Write a program to implement STACK with the following
operations.
a. Push
b. Pop
c. Display

Source code:

#include<stdio.h>
#include<stdlib.h>
#define MAX 5

int top=-1, a[MAX];

void push();
void pop();
void display();

void main()
{
int ch;
printf("1.PUSH \n 2.POP \n 3.DISPLAY \n 4.EXIT \n");
while(1)
{
printf(" \nEnter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
push();
break;

case 2:
pop();
break;

case 3:
display();
break;

case 4:
exit(0);

1st sem MCA/MSC 2024-2025 1|Page

Data Structures and Algorithms Lab REG.NO: 24MCA306

default:
printf("Invalid choice \n");
}
}
}

void push()
{
int data;
if(top == MAX-1)
printf("Stack Overflow \n");
else
{
printf("Enter the element to push: ");
scanf("%d",&data);
top++;
a[top]=data;
}
}

void pop()
{
if(top==-1)
printf("Stack Underflow \n");
else
{
printf("Popped element is:%d\n",a[top]);
--top;
}
}

void display()
{
int i;
if(top>=0)
{
printf("Elements are: \n");
for(i=top;i>=0;i--)
printf("%d \n",a[i]);
}
else
{
printf("Stack is empty \n");
}

1st sem MCA/MSC 2024-2025 2|Page

Data Structures and Algorithms Lab REG.NO: 24MCA306

Output:

1.PUSH
2.POP
3.DISPLAY
4.EXIT

Enter your choice 3

Stack is empty

Enter your choice 2

Stack is empty

Enter your choice 1

Enter the element to push 10

Enter your choice 3

Elements are:
10

Enter your choice 1

Enter the element to push 20

Enter your choice 1

Enter the element to push 30

Enter your choice 3

Elements are:
30
20
10

Enter your choice 2

Popped element is: 30

Enter your choice 3
Elements are:
20
10

Enter your choice 2

Popped element is:20
Enter your choice 3

1st sem MCA/MSC 2024-2025 3|Page

Data Structures and Algorithms Lab REG.NO: 24MCA306

Elements are:
10

Enter your choice 2

Popped element is:10

Enter your choice 2
Stack is empty

Enter your choice 3

Stack is empty

Enter your choice 4

1st sem MCA/MSC 2024-2025 4|Page

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 2
Program statement: Write a program to implement QUEUE with the following
operations
a. Enqueue
b. Dequeue
c. Display

Source code

#include <stdio.h>
#include<stdlib.h>
#define SIZE 10

void enqueue();
void dequeue();
void display();
int arr[SIZE];

int rear = - 1;
int front = - 1;

int main()
{
int choice;
while (1)
{
printf("\n1.Insert element to queue \n");
printf("2.Delete element from queue \n");
printf("3.Display all elements of queue \n");
printf("4.Quit \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
display();
break;

1st sem MCA/MSC 2024-2025 5|Page

Data Structures and Algorithms Lab REG.NO: 24MCA306

case 4:
exit(0);
default:
printf("Wrong choice \n");
}
}
}

void enqueue() {
int item;
if (rear == SIZE - 1)
printf("Queue Overflow \n");
else
{
if (front == - 1)
front = 0;
printf("Enter the element to be inserted: ");
scanf("%d",&item);
rear = rear + 1;
arr[rear] = item;
}
}

void dequeue() {
if (front == - 1 || front > rear)
printf("Queue Underflow \n");
else
{
printf("Element deleted from queue is : %d\n", arr[front]);
front = front + 1;
}
}

void display() {
if (front == - 1 || front > rear)
printf("Queue is empty \n");
else
{
printf("Queue is : \n");
for (int i = front; i <= rear; i++)
printf("%d ", arr[i]);
printf("\n");
}
}

1st sem MCA/MSC 2024-2025 6|Page

Data Structures and Algorithms Lab REG.NO: 24MCA306

Output:
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 3
Queue is empty

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 2
Queue Underflow

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 1
Enter the element to be inserted: 10

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 1
Enter the element to be inserted: 20

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 1
Enter the element to be inserted: 30

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 3
Queue is :
10 20 30

1st sem MCA/MSC 2024-2025 7|Page

Data Structures and Algorithms Lab REG.NO: 24MCA306

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 2
Element deleted from queue is : 10

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 2
Element deleted from queue is : 20

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 2
Element deleted from queue is : 30

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 2
Queue Underflow

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 3
Queue is empty

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 4

1st sem MCA/MSC 2024-2025 8|Page

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 3
Program statement: Write a program to implement Insertion Sort.

Source code:

#include <stdio.h>
void insertionSort(int a[], int n)
{
for (int i = 1; i < n; i++)
{
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key)
{
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = key;
}
}

int main()
{
int n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
int a[n];
printf("Enter the array elements:\n");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
insertionSort(a, n);
printf("\nSorted array: \n");
for (i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}

1st sem MCA/MSC 2024-2025 9|Page

Data Structures and Algorithms Lab REG.NO: 24MCA306

Output:

Enter the number of elements: 5

Enter the array elements:
9 11 45 0 -2

Sorted array:
-2 0 9 11 45

1st sem MCA/MSC 2024-2025 10 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 4
Program statement: Write a program to implement Selection Sort.

Source code:

#include <stdio.h>
void selectionSort(int a[], int n)
{
int i, j, min, temp;
for (i = 0; i < n-1; i++)
{
min = i;
for (j = i+1; j < n; j++)
{
if (a[j] < a[min])
{
min = j;
}
}
temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}

int main()
{
int n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
int a[n];
printf("Enter the array elements:\n");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);

selectionSort(a, n);
printf("Sorted array: \n");
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}

1st sem MCA/MSC 2024-2025 11 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Output:

Enter the number of elements: 5

Enter the array elements:
2 0 -1 6 9
Sorted array:
-1 0 2 6 9

1st sem MCA/MSC 2024-2025 12 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 5
Program statement: Write a program to implement Bubble Sort.

Source code:

#include <stdio.h>
void bubbleSort(int a[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}

int main()
{
int n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
int a[n];
printf("Enter the array elements:\n");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);

bubbleSort(a, n);
printf("\nSorted array: \n");
for (i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}

1st sem MCA/MSC 2024-2025 13 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Output:

Enter the number of elements: 5

Enter the array elements:
0 9 5 -12 3

Sorted array:
-12 0 3 5 9

1st sem MCA/MSC 2024-2025 14 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 6
Program statement: Write a program to implement Linear Search.

Source code:

#include <stdio.h>

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 n,arr[100],key;
printf("Enter the number of elements:");
scanf("%d",&n);
printf("Enter the elements:");
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf("Enter the key element:");
scanf("%d",&key);
int i = linearSearch(arr, n, key);
if (i == -1)
printf("Key Not Found");
else
printf("Key Found at Index: %d", i);
return 0;
}

1st sem MCA/MSC 2024-2025 15 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Output 1:
Enter the number of elements:5
Enter the elements:2 9 3 1 0
Enter the key element:9
Key Found at Index: 1

Output 2:
Enter the number of elements:5
Enter the elements:2 9 3 1 0
Enter the key element:5
Key Not Found

1st sem MCA/MSC 2024-2025 16 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 7
Program statement: Write a program to implement Binary Search.

Source code:

#include <stdio.h>

int binarySearch(int array[], int size, int target) {

int low = 0, high = size - 1;
while (low <= high)
{
int mid = low + (high - low) / 2;
if (array[mid] == target)
return mid;
if (array[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}

int main() {
int array[100],target,n,i;
printf("Enter the number of elements:");
scanf("%d",&n);
printf("Enter the array elements:");
for(i=0;i<n;i++)
{
scanf("%d",&array[i]);
}
printf("enter the target element:");
scanf("%d",&target);
int result = binarySearch(array, n ,target);
if (result == -1)
printf("Element is not present in the array”);
else
printf(“Element is present at index %d\n", result);
return 0;
}

1st sem MCA/MSC 2024-2025 17 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Output:

Enter the number of elements: 5

Enter the array elements: 1 2 3 4 5
Enter the target element: 3
Element is present at index 2

Enter the number of elements: 5

Enter the array elements: 1 2 3 4 5
Enter the target element: 6
Element is not present in the array

1st sem MCA/MSC 2024-2025 18 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 8
Program statement: Write a program to implement Breadth First Search.

Source code:

#include <stdio.h>

int adj[100][100], visited[100], queue[100], front = 0, rear = 0;

void bfs(int start, int n) {

queue[rear++] = start;
visited[start] = 1;

printf("BFS: ");
while (front < rear) {
int curr = queue[front++];
printf("%d ", curr);

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

if (adj[curr][i] && !visited[i]) {
queue[rear++] = i;
visited[i] = 1;
}
}
}
}

int main() {
int vertices, edges, start;

printf("Enter Vertices, Edges & Start Vertex: ");

scanf("%d%d%d", &vertices, &edges, &start);

printf("Enter the edges from (v1 -> v2):\n");

for (int i = 0; i < edges; i++) {
int v1, v2;
scanf("%d %d", &v1, &v2);
adj[v1][v2] = adj[v2][v1] = 1;
}
bfs(start, vertices);
return 0;
}

1st sem MCA/MSC 2024-2025 19 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Output:

Enter Vertices, Edges & Start Vertex: 7 6 1

Enter the edges from (v1 -> v2):
12
13
24
25
36
37
BFS: 1 2 3 4 5 6 7

1st sem MCA/MSC 2024-2025 20 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 9
Program statement: Write a program to implement Depth First Search.

Source code:

#include <stdio.h>

int adj[100][100], visited[100], stack[100], top = -1;

void dfs(int start, int vertices) {

stack[++top] = start;
visited[start] = 1;

printf("DFS: ");
while (top >= 0) {
int curr = stack[top--];
printf("%d ", curr);

for (int i = vertices; i >= 0; i--) {

if (adj[curr][i] && !visited[i]) {
stack[++top] = i;
visited[i] = 1;
}
}
}
printf("\n");
}

int main() {
int vertices, edges, v1, v2, start;

printf("Enter number of vertices and edges: ");

scanf("%d %d", &vertices, &edges);

printf("Enter the edges from (v1 -> v2):\n");

for (int i = 0; i < edges; i++) {
scanf("%d %d", &v1, &v2);
adj[v1][v2] = adj[v2][v1] = 1; // Undirected graph
}

1st sem MCA/MSC 2024-2025 21 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

printf("Enter the starting vertex: ");

scanf("%d", &start);

dfs(start, vertices);

return 0;
}

Output:

Enter number of vertices and edges: 7 6

Enter the edges from (v1 -> v2):
12
13
24
25
36
37
Enter the starting vertex: 1
DFS: 1 2 4 5 3 6 7

1st sem MCA/MSC 2024-2025 22 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

PART - B

Program No: 1
Program statement: Write a C program to evaluate postfix expression.

Source code:

#include<stdio.h>
#include<ctype.h>

int stack[20];
int top = -1;

void push(int x) {
stack[++top] = x;
}

int pop() {
return stack[top--];
}

int main() {
char exp[20];
char *e;
int n1, n2, n3, num;

printf("Enter the postfix expression: ");

scanf("%s", exp);
e = exp;

while (*e != '\0') {

if (isdigit(*e)) {
num = *e - 48; // Convert char to int
push(num);
}
else {
n1 = pop();
n2 = pop();
switch (*e) {
case '+':
n3 = n2 + n1;
break;

1st sem MCA/MSC 2024-2025 23 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

case '-':
n3 = n2 - n1;
break;
case '*':
n3 = n2 * n1;
break;
case '/':
n3 = n2 / n1;
break;
}
push(n3);
}
e++;
}
printf("The result of expression %s = %d\n", exp, pop());
return 0;
}

Output:

Enter the postfix expression: 243+*

The result of expression 243+* = 14

1st sem MCA/MSC 2024-2025 24 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 2
Program statement: Write a C program that converts infix expression to
postfix expression.

Source code:

#include<stdio.h>
#include<ctype.h>

char stack[20];
int top=-1;

void push(char x)
{
stack[++top]=x;
}

char pop()
{
if(top==-1)
return -1;
else
return stack[top--];
}

int priority(char x)
{
if(x=='(')
return 0;
if(x=='+' || x=='-')
return 1;
if(x=='*' || x=='/')
return 2;
if(x=='$')
return 3;
}

int main()
{
char exp[20];
char *e,x;
printf("Enter the Infix Expression:: ");

1st sem MCA/MSC 2024-2025 25 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

scanf("%s", exp);
e=exp;
printf("\nPostfix Expression:: ");
while(*e!='\0')
{
if(isalnum(*e))
printf("%c", *e);
else if(*e=='(')
push(*e);
else if(*e==')'){
while((x=pop()) != '(')
printf("%c", x);
}
else
{
while(priority(stack[top])>=priority(*e))
printf("%c", pop());
push(*e);
}
e++;
}
while(top!=-1){
printf("%c", pop());
}
printf("\n");
}

Output:

Enter the Infix Expression: (a+b)*(c+d)

Postfix Expression: ab+cd+*

1st sem MCA/MSC 2024-2025 26 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 3
Program statement: Write a program to implement Merge Sort.

Source code:

#include <stdio.h>
#include <stdlib.h>
void mergesort(int, int);
void merge(int, int, int);
int a[100];

int main() {
int i, n;
printf("Enter the range: ");
scanf("%d", &n);
printf("\nEnter the %d numbers: ", n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);

mergesort(0, n - 1);

printf("\nAfter sorting: ");

for (i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}

void mergesort(int low, int high) {

int mid;
if (low < high) {
mid = (low + high) / 2;
mergesort(low, mid);
mergesort(mid + 1, high);
merge(low, mid, high);
}
}

void merge(int low, int mid, int high) {

int i = low;
int j = mid + 1;
int k = low;
int c[100];

1st sem MCA/MSC 2024-2025 27 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

while ((i <= mid) && (j <= high)) {

if (a[i] < a[j]) {
c[k] = a[i];
k = k + 1;
i = i + 1;
} else {
c[k] = a[j];
k = k + 1;
j = j + 1;
}
}

while (i <= mid) {

c[k] = a[i];
k = k + 1;
i = i + 1;
}

while (j <= high) {

c[k] = a[j];
k = k + 1;
j = j + 1;
}

for (i = low; i < k; i++) {

a[i] = c[i];
}
}

Output:

Enter the range: 5

Enter the 5 numbers: 3 4 0 -2 7

After sorting: -2 0 3 4 7

1st sem MCA/MSC 2024-2025 28 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 4
Program statement: Write a C program to implement Dijkstra’s Algorithm.

Source code:

#include <stdio.h>
#include <limits.h>
#define MAX 100

int minDist(int dist[], int visited[], int n) {

int min = INT_MAX, idx;
for (int i = 0; i < n; i++) {
if (!visited[i] && dist[i] < min) {
min = dist[i];
idx = i;
}
}
return idx;
}

void printPath(int parent[], int j) {

if (j == -1) return;
printPath(parent, parent[j]);
printf("%d ", j);
}

void dijkstra(int graph[MAX][MAX], int n, int start) {

int dist[MAX], visited[MAX] = {0}, parent[MAX];
for (int i = 0; i < n; i++) {
dist[i] = INT_MAX;
parent[i] = -1;
}
dist[start] = 0;

for (int i = 0; i < n - 1; i++) {

int u = minDist(dist, visited, n);
visited[u] = 1;
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
parent[v] = u;

1st sem MCA/MSC 2024-2025 29 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

}
}
}

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

if (dist[i] == INT_MAX)
printf("Vertex %d: Unreachable\n", i);
else {
printf("Vertex %d, Distance: %d, Path: ", i, dist[i]);
printPath(parent, i);
printf("\n");
}
}
}

int main() {
int n, e, u, v, w;
int graph[MAX][MAX] = {0};

printf("Enter the number of vertices and edges: ");

scanf("%d %d", &n, &e);

printf("Enter edges (u v w):\n");

for (int i = 0; i < e; i++) {
scanf("%d %d %d", &u, &v, &w);
graph[u][v] = graph[v][u] = w;
}

printf("Enter the source vertex: ");

scanf("%d", &u);

dijkstra(graph, n, u);

return 0;
}

1st sem MCA/MSC 2024-2025 30 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Output:

Enter the number of vertices and edges: 5 6

Enter edges (u v w):
012
024
121
137
243
342
Enter the source vertex: 0
Vertex 0, Distance: 0, Path: 0
Vertex 1, Distance: 2, Path: 0 1
Vertex 2, Distance: 3, Path: 0 1 2
Vertex 3, Distance: 8, Path: 0 1 2 4 3
Vertex 4, Distance: 6, Path: 0 1 2 4

1st sem MCA/MSC 2024-2025 31 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 5
Program statement: Write a C program to implement Kruskal’s Algorithm.

Source code:

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

typedef struct {
int u, v, w;
} Edge;

int parent[MAX];

int find(int i) {
while (parent[i] != i)
i = parent[i];
return i;
}

void unionSets(int u, int v) {

int root_u = find(u);
int root_v = find(v);
parent[root_u] = root_v;
}

int compareEdges(const void* a, const void* b) {

return ((Edge*)a)->w - ((Edge*)b)->w;
}

void kruskal(Edge edges[], int n, int e) {

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

qsort(edges, e, sizeof(Edge), compareEdges);

int totalWeight = 0;
printf("Edges in the Minimum Spanning Tree:\n");

1st sem MCA/MSC 2024-2025 32 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

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

int u = edges[i].u;
int v = edges[i].v;
int w = edges[i].w;

if (find(u) != find(v)) {
printf("(%d, %d) -> %d\n", u, v, w);
totalWeight += w;
unionSets(u, v);
}
}
printf("Total weight of the Minimum Spanning Tree: %d\n", totalWeight);
}

int main() {
int n, e;

printf("Enter the number of vertices: ");

scanf("%d", &n);
printf("Enter the number of edges: ");
scanf("%d", &e);

Edge edges[MAX];

printf("Enter the edges (u v w):\n");

for (int i = 0; i < e; i++) {
scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
}

kruskal(edges, n, e);
return 0;
}

1st sem MCA/MSC 2024-2025 33 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Output:

Enter the number of vertices: 5

Enter the number of edges: 7
Enter the edges (u v w):
121
137
1 4 10
155
233
344
452
Edges in the Minimum Spanning Tree:
(1, 2) -> 1
(4, 5) -> 2
(2, 3) -> 3
(3, 4) -> 4
Total weight of the Minimum Spanning Tree: 10

1st sem MCA/MSC 2024-2025 34 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 6
Program statement: Write a C program to implement Prims Algorithm.

Source code:

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

int edges[100][3], visited[100] = {0}, n, m;

int find() {
int min_weight = INT_MAX, min_index = -1;
for (int i = 0; i < m; i++) {
if ((visited[edges[i][0]] && !visited[edges[i][1]]) ||
(visited[edges[i][1]] && !visited[edges[i][0]])) {
if (edges[i][2] < min_weight) {
min_weight = edges[i][2];
min_index = i;
}
}
}
return min_index;
}

int main() {
int total_weight = 0, count = 0;

printf("Enter number of vertices and edges: ");

scanf("%d %d", &n, &m);

printf("Enter edges (u v weight):\n");

for (int i = 0; i < m; i++)
scanf("%d %d %d", &edges[i][0], &edges[i][1], &edges[i][2]);

visited[1] = 1; // Start from vertex 1 (adjust indexing to match input)

printf("Edges in the Minimum Spanning Tree:\n");

while (count < n - 1) {
int min_index = find();
if (min_index == -1) break; // No more valid edges

1st sem MCA/MSC 2024-2025 35 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

printf("%d - %d = %d\n", edges[min_index][0], edges[min_index][1], edges[min_index][2]);

total_weight += edges[min_index][2];
visited[edges[min_index][0]] = visited[edges[min_index][1]] = 1;
count++;
}

printf("Total weight = %d\n", total_weight);

return 0;
}

Output:

Enter number of vertices and edges: 5 6

Enter edges (u v weight):
133
3 2 10
342
356
244
451
Edges in the Minimum Spanning Tree:
1-3=3
3-4=2
4-5=1
2-4=4
Total weight = 10

1st sem MCA/MSC 2024-2025 36 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 7
Program statement: Write a C program to perform Inorder, Preorder, and Postorder
traversal of the Binary tree.

Source code:

#include <stdio.h>
#define MAX_NODES 100

void inorder(int tree[], int index, int n) {

if (index >= n || tree[index] == -1) return;
inorder(tree, 2 * index + 1, n); // Visit left child (2*index + 1)
printf("%d ", tree[index]); // Visit root
inorder(tree, 2 * index + 2, n); // Visit right child (2*index + 2)
}

void preorder(int tree[], int index, int n) {

if (index >= n || tree[index] == -1) return;
printf("%d ", tree[index]); // Visit root
preorder(tree, 2 * index + 1, n); // Visit left child
preorder(tree, 2 * index + 2, n); // Visit right child
}

void postorder(int tree[], int index, int n) {

if (index >= n || tree[index] == -1) return;
postorder(tree, 2 * index + 1, n); // Visit left child
postorder(tree, 2 * index + 2, n); // Visit right child
printf("%d ", tree[index]); // Visit root
}

int main() {
int tree[MAX_NODES], n;
printf("Enter the number of nodes in the binary tree: ");
scanf("%d", &n);

printf("Enter the tree elements (use -1 for empty nodes):\n");

for (int i = 0; i < n; i++) {
scanf("%d", &tree[i]);
}

printf("\nInorder Traversal: ");

1st sem MCA/MSC 2024-2025 37 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

inorder(tree, 0, n);
printf("\n");

printf("Preorder Traversal: ");

preorder(tree, 0, n);
printf("\n");

printf("Postorder Traversal: ");

postorder(tree, 0, n);
printf("\n");

return 0;
}

Output:

Enter the number of nodes in the binary tree: 7

Enter the tree elements (use -1 for empty nodes):
1234567

Inorder Traversal: 4 2 5 1 6 3 7
Preorder Traversal: 1 2 4 5 3 6 7
Postorder Traversal: 4 5 2 6 7 3 1

1st sem MCA/MSC 2024-2025 38 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 8
Program statement: Write a C program to implement the Bellman-Ford algorithm.

Source code:

#include <stdio.h>
#include <limits.h>
#define MAX_EDGES 100
#define MAX_VERTICES 100

void printArr(int dist[], int n)

{
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}

void BellmanFord(int graph[MAX_EDGES][3], int V, int E, int src)

{
int dist[MAX_VERTICES];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;

for (int i = 1; i <= V - 1; i++)

{
for (int j = 0; j < E; j++)
{
int u = graph[j][0];
int v = graph[j][1];
int weight = graph[j][2];
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}

for (int i = 0; i < E; i++)

{
int u = graph[i][0];
int v = graph[i][1];
int weight = graph[i][2];

1st sem MCA/MSC 2024-2025 39 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

if (dist[u] != INT_MAX && dist[u] + weight < dist[v])

{
printf("Graph contains negative weight cycle\n");
return;
}
}
printArr(dist, V);
return;
}

int main()
{
int V, E;
printf("Enter the number of vertices: ");
scanf("%d", &V);
printf("Enter the number of edges: ");
scanf("%d", &E);

int graph[MAX_EDGES][3];

printf("Enter the edges (source destination weight):\n");

for (int i = 0; i < E; i++)
{
scanf("%d %d %d", &graph[i][0], &graph[i][1], &graph[i][2]);
}

int src;
printf("Enter the source vertex: ");
scanf("%d", &src);

BellmanFord(graph, V, E, src);

return 0;
}

1st sem MCA/MSC 2024-2025 40 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Output:

Enter the number of vertices: 5

Enter the number of edges: 5
Enter the edges (source destination weight):
132
4 3 -1
241
121
015
Enter the source vertex: 0
Vertex Distance from Source
0 0
1 5
2 6
3 6
4 7

1st sem MCA/MSC 2024-2025 41 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Program No: 9
Program statement: Write a c program to perform Singly Linked list operations
a) Insertion at the beginning
b) Deletion at the beginning
c) Insertion at the End
d) Deletion at the end
e) Traversing

Source code:

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

void insertAtBeginning(int list[], int *size, int data) {

if (*size >= MAX) {
printf("List is full. Cannot insert at the beginning.\n");
return;
}
for (int i = *size; i > 0; i--) {
list[i] = list[i - 1];
}
list[0] = data; // Insert new data at the beginning
(*size)++;
}

void insertAtEnd(int list[], int *size, int data) {

if (*size >= MAX) {
printf("List is full. Cannot insert at the end.\n");
return;
}
list[*size] = data; // Insert new data at the end
(*size)++;
}

void deleteFromBeginning(int list[], int *size) {

if (*size == 0) {
printf("List is empty. Nothing to delete from the beginning.\n");
return;
}
for (int i = 0; i < *size - 1; i++) {
list[i] = list[i + 1];

1st sem MCA/MSC 2024-2025 42 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

}
(*size)--; // Decrease size
}

void deleteFromEnd(int list[], int *size) {

if (*size == 0) {
printf("List is empty. Nothing to delete from the end.\n");
return;
}
(*size)--; // Decrease size
}

void printList(int list[], int size) {

for (int i = 0; i < size; i++) {
printf("%d -> ", list[i]);
}
printf("NULL\n");
}

int main() {
int list[MAX];
int size = 0;
int choice, data;

while (1) {
printf("\n1. Insert at Beginning\n");
printf("2. Insert at End\n");
printf("3. Delete from Beginning\n");
printf("4. Delete from End\n");
printf("5. Print List\n");
printf("6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter data to insert at the beginning: ");
scanf("%d", &data);
insertAtBeginning(list, &size, data);
break;

1st sem MCA/MSC 2024-2025 43 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

case 2:
printf("Enter data to insert at the end: ");
scanf("%d", &data);
insertAtEnd(list, &size, data);
break;
case 3:
deleteFromBeginning(list, &size);
break;
case 4:
deleteFromEnd(list, &size);
break;
case 5:
printList(list, size);
break;
case 6:
exit(0);
default:
printf("Invalid choice. Please try again.\n");
}
}
return 0;
}

Output:

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit
Enter your choice: 5
NULL

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit

1st sem MCA/MSC 2024-2025 44 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

Enter your choice: 1

Enter data to insert at the beginning: 10

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit
Enter your choice: 5
10 -> NULL

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit
Enter your choice: 1
Enter data to insert at the beginning: 20

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit
Enter your choice: 5
20 -> 10 -> NULL

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit
Enter your choice: 2
Enter data to insert at the end: 30

1st sem MCA/MSC 2024-2025 45 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit
Enter your choice: 5
20 -> 10 -> 30 -> NULL

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit
Enter your choice: 3

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit
Enter your choice: 5
10 -> 30 -> NULL

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit
Enter your choice: 4

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit
Enter your choice: 5
10 -> NULL

1st sem MCA/MSC 2024-2025 46 | P a g e

Data Structures and Algorithms Lab REG.NO: 24MCA306

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit
Enter your choice: 3

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit
Enter your choice: 3
List is empty. Nothing to delete from the beginning.

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit
Enter your choice: 4
List is empty. Nothing to delete from the end.

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit
Enter your choice: 5
NULL

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Print List
6. Exit
Enter your choice: 6

1st sem MCA/MSC 2024-2025 47 | P a g e