Name of the Student: …………………………………………………...

Register Number: ……………………………………………………….

Year/ Semester: II -YEAR / III -

SEMESTER
Register No:

BONAFIDE CERTIFICATE

Certified that this is the Bonafide record of work done by Mr./Ms.

……………………………………………of …… semester [Link]. –
INFORMAION TECHNOLOGY in the DATA STRUCTURES Laboratory
during the academic year 2026

Staff – in – Charge Head of the Department

Submitted for the University Practical Examination held on …………………………

Internal Examiner External Examiner

 INDEX

[Link] DATE EXPERIMENT PAGE SIGNATURE

NO
SINGLE DIMENSIONAL ARRAY
1A
MULTI DIMENSIONAL ARRAY
1B
SINGLY LINKED LISTS
2A
DOUBLY LINKED LISTS
2B
CIRCULAR LINKED LISTS
2C
STRING REVERSE OPERATIONS
3A
EXPRESSION EVALUATION
3B
CIRCULAR QUEUE
4A

PRIORITY QUEUE
4B
TRAVERSAL OPERATION
5
AVL TREE ROTATION
6
QUERY AND UPDATE OPERATIONS ON
7 BALANCED BST’s
QUICK SORT
8A

HEAP SORT
8B

BINARY SEARCH
9A

HASHING TECHNIQUES
9B
BFS ALGORITHM
10A

DFS ALGORITHM
10B
MINIMUM SPANNING TREE
11A

SHORTEST PATH ALGORITHMS

11B
 EX NO :
1a. Implement a Single Dimensional Arrays using Linear Data Structure
Date :

Aim:
To develop a C program for implementing single-dimensional arrays and perform basic
operations.
Software Requirement
 Operating System: Windows/Linux
 Compiler: GCC / Turbo C / Code: Blocks / Visual Studio Code
 Language: C
Theory
An array is a collection of elements of the same data type stored in contiguous memory locations. Arrays
are one of the simplest linear data structures, where elements are arranged sequentially.
Single Dimensional Array
A single-dimensional array stores elements in a linear sequence and can be accessed using a single index.
Syntax
datatype array_name[size];
Example
int marks [5];
Algorithm
1. Start the program and declare the required variables and an array.
2. Read the number of elements to be stored in the array.
3. Input the array elements using a loop.
4. Traverse the array to display all the elements.
5. Compute the sum of all elements and identify the largest element.
6. Display the calculated sum and the largest element.
7. Stop the program.

Program
#include<stdio.h>
int main()
{
int a[100], n, i;
int sum = 0, max;
printf("Enter number of elements: ");
scanf("%d",&n);
printf("Enter the elements:\n");
 for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("\nArray Elements:\n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
max=a[0];
for(i=0;i<n;i++)
{
sum=sum+a[i];
if(a[i]>max)
max=a[i];
}
printf("\nSum = %d",sum);
printf("\nLargest Element = %d",max);
return 0;
}

Output
Enter number of elements: 5
Enter the elements:
10
20
30
40
50
Array Elements:
10 20 30 40 50
Sum = 150
Largest Element = 50

Viva Questions:
 1. What is an array in C?

2. Why is an array considered a linear data structure?

3. What is a single-dimensional array?

4. How do you declare a single-dimensional array in C?

5. What is the syntax for initializing an array?

6. What is array indexing? From which index does an array start in C?

Result
Thus, the C programs for implementing Single Dimensional Array using a linear data structure were
successfully developed and executed, and the expected output was verified.
 EX NO : 1b
Implement a Multi-Dimensional Arrays using Linear Data
DATE : Structure

Aim
To develop a C program for implementing multidimensional arrays and perform basic operations.
Software Requirement
 Operating System : Windows/Linux
 Compiler : GCC / Turbo C / Code::Blocks / Visual Studio Code
 Language : C
Theory
An array is a collection of elements of the same data type stored in contiguous memory locations. Arrays
are one of the simplest linear data structures, where elements are arranged sequentially.
Multidimensional Array
A multidimensional array consists of rows and columns. The most commonly used multidimensional array is
the two-dimensional array (matrix).
Syntax
datatype array_name[row][column];
Example
int matrix [3][3];

Algorithm
1. Start the program and declare a two-dimensional array along with the required variables.
2. Read the number of rows and columns of the matrix from the user.
3. Input the matrix elements using nested for loops.
4. Traverse the matrix using nested loops and display the elements in row and column format.
5. Perform the required operation (such as calculating the sum of all elements) while traversing the
matrix.
6. Display the computed result.
7. Stop the program.

Program
#include<stdio.h>

int main()
{
int a[10][10];
int row,col,i,j,sum=0;
 printf("Enter number of rows: ");
scanf("%d",&row);

printf("Enter number of columns: ");

scanf("%d",&col);

printf("Enter the matrix elements:\n");

for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
scanf("%d",&a[i][j]);
}
}

printf("\nMatrix:\n");

for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
printf("%4d",a[i][j]);
sum=sum+a[i][j];
}
printf("\n");
}

printf("\nSum of all elements = %d",sum);

return 0;
}

Output
Enter number of rows: 2
Enter number of columns: 3
Enter the matrix elements:
123
456
Matrix:
123
456
Sum of all elements = 21

Viva Questions:
1. What is a multidimensional array?

2. What is a two-dimensional array in C?

3. How do you declare a two-dimensional array?

4. What is the syntax for initializing a two-dimensional array?

5. How are elements stored in a two-dimensional array?

6. What are rows and columns in a two-dimensional array?

 7. How do you access an element in a two-dimensional array?

Result

Thus, the C programs for implementing Multidimensional Array using a linear data structure were
successfully developed and executed, and the expected output was verified.
 EX NO : 2.a
LINKED LIST IMPLEMENTATION OF LIST [SINGLY LINKED LIST]
DATE :

Aim:
To implement and study the operations of Singly Linked List using C programming language by
performing basic operations such as insertion, deletion, and searching.
Theory
1. Singly Linked List
A Singly Linked List (SLL) is a linear data structure in which each node contains two parts: data and a
pointer to the next node. The last node points to NULL, indicating the end of the list.
It allows sequential access of elements and is dynamically allocated, meaning memory is allocated
during runtime.
Features:
 One-way traversal only
 Each node has a single pointer (next)
 Efficient insertion and deletion at beginning
Applications:
 Memory management
 Stack and queue implementation
 Polynomial representation

Algorithm:

1. Start the program and define the structure with data and a pointer to the next node.

2. Create a new node and allocate memory dynamically.

3. Read the data to be inserted into the node.

4. If the list is empty, make the new node as the head.

5. Otherwise, traverse to the last node and link the new node to it.

6. Display the list by traversing from head to NULL.

7. Stop the program.

Program:

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

struct node {
int data;
struct node *next;
};

struct node *head = NULL;

// INSERT AT END
void insert(int value)
{
struct node *newnode = (struct node*)malloc(sizeof(struct node));
struct node *temp;

newnode->data = value;
newnode->next = NULL;

if(head == NULL)
{
head = newnode;
}
else
{
temp = head;
while(temp->next != NULL)
{
temp = temp->next;
}
temp->next = newnode;
}
}

// DELETE NODE
void deleteNode(int key)
{
struct node *temp = head, *prev = NULL;

if(temp != NULL && temp->data == key)

{
head = temp->next;
free(temp);
return;
}

while(temp != NULL && temp->data != key)

{
prev = temp;
temp = temp->next;
}

if(temp == NULL) return;

prev->next = temp->next;
free(temp);
}

// SEARCH
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 not found\n");
}

// DISPLAY
void display()
{
struct node *temp = head;
printf("SLL: ");
while(temp != NULL)
{
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main()
{
insert(10);
insert(20);
insert(30);

display();

search(20);

deleteNode(20);

display();

return 0;
}

Output

SLL: 10 -> 20 -> 30 -> NULL

Element 20 found at position 2
SLL: 10 -> 30 -> NULL
Viva questions:

1. What is a singly linked list?

2. What are the components of a node in a singly linked list?

3. Why is it called a linear data structure?

4. How is memory allocated in a singly linked list?

5. What is the role of the “next” pointer?

 6. Can we traverse backward in a singly linked list? Why?

7. What are the advantages and disadvantages of singly linked list?

Result

Thus, the C programs for Singly Linked List were successfully implemented. The operations such as
insertion, deletion, and searching were performed and verified successfully.

1. Singly Linked List follows one-way traversal and the last node points to NULL.

The output of all operations was executed successfully and verified with the expected results.
 EX NO : 2.b
Linked List Implementation of List [Doubly Linked List]
DATE :

Aim:
To implement and study the operations of Doubly Linked List using C programming language by
performing basic operations such as insertion, deletion, and searching.
Theory
1. Doubly Linked List
A Doubly Linked List (DLL) is a linear data structure in which each node contains data, a pointer to
the next node, and a pointer to the previous node.
This allows traversal in both forward and backward directions.
Features:
 Two-way traversal
 Each node has two pointers (Prev and next)
 Easier deletion compared to singly linked list
Applications:
 Browser history navigation
 Undo/Redo operations
 Doubly ended queues (Deque)

Algorithm:

1. Start the program and define a structure with data, previous pointer, and next pointer.

2. Create a new node and allocate memory dynamically.

3. Read the data and initialize pointers to NULL.

4. If the list is empty, make the new node as the head.

5. Otherwise, insert the node by updating both previous and next links accordingly.

6. Traverse forward using next pointer and backward using previous pointer to display the list.

7. Stop the program.

Program:

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

struct node {
int data;
struct node *prev;
struct node *next;
};

struct node *head = NULL;

// INSERT
void insert(int value)
{
struct node *newnode = (struct node*)malloc(sizeof(struct node));
struct node *temp;

newnode->data = value;
newnode->next = NULL;
newnode->prev = NULL;

if(head == NULL)
{
head = newnode;
}
else
{
temp = head;
while(temp->next != NULL)
{
temp = temp->next;
}
temp->next = newnode;
newnode->prev = temp;
}
}

// DELETE
void deleteNode(int key)
{
struct node *temp = head;

while(temp != NULL && temp->data != key)

{
temp = temp->next;
}

if(temp == NULL) return;

if(temp->prev != NULL)
temp->prev->next = temp->next;
else
head = temp->next;

if(temp->next != NULL)
temp->next->prev = temp->prev;

free(temp);
}

// SEARCH
void search(int key)
{
struct node *temp = head;
int pos = 1;

while(temp != NULL)
 {
if(temp->data == key)
{
printf("Found %d at position %d\n", key, pos);
return;
}
temp = temp->next;
pos++;
}
printf("Not Found\n");
}

// DISPLAY
void display()
{
struct node *temp = head;
printf("DLL: ");
while(temp != NULL)
{
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main()
{
insert(100);
insert(200);
insert(300);

display();

search(200);

deleteNode(200);

display();

return 0;
}

Output

DLL: 100 <-> 200 <-> 300 <-> NULL

Found 200 at position 2

DLL: 100 <-> 300 <-> NULL

 Viva Questions

1. What is a doubly linked list?

2. What are the fields present in a doubly linked list node?

3. How does a doubly linked list differ from a singly linked list?

4. What is the use of the “prev” pointer?

5. Why is deletion easier in a doubly linked list?

 6. Can we traverse both directions in a doubly linked list? Explain.

7. Where is doubly linked list used in real life applications?

Result

Thus, the C programs for Doubly Linked List were successfully implemented. The operations such as
insertion, deletion, and searching were performed and verified successfully.

2. Doubly Linked List supports two-way traversal using both previous and next pointers.

The output of all operations was executed successfully and verified with the expected results.
 EX NO : 2.C
Linked List Implementation of List [Circular Linked List]
DATE :

Aim:
To implement and study the operations of Circular Linked List using C programming language by
performing basic operations such as insertion, deletion, and searching.
Theory
1. Circular Linked List
A Circular Linked List (CLL) is a variation of a linked list in which the last node points back to the
first node (head) instead of NULL, forming a circular structure.
There is no starting or ending point in traversal; we stop when we reach the head again.
Features:
 No NULL at the end
 Continuous circular traversal
 Can be singly or doubly circular
Applications:
 CPU scheduling (Round Robin algorithm)
 Multiplayer games
 Continuous buffering systems

Algorithm:

1. Start the program and define a structure with data and a pointer to the next node.

2. Create a new node and allocate memory dynamically.

3. Read the data to be inserted.

4. If the list is empty, point the node to itself and make it as head.

5. Otherwise, traverse to the last node and link it to the new node.

6. Make the last node point back to the head to form a circular structure.

7. Traverse the list until it reaches the head again.

8. Stop the program.

Program:

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

struct node {
int data;
struct node *next;
};
struct node *head = NULL;

// INSERT
void insert(int value)
{
struct node *newnode = (struct node*)malloc(sizeof(struct node));
struct node *temp;

newnode->data = value;

if(head == NULL)
{
head = newnode;
newnode->next = head;
}
else
{
temp = head;
while(temp->next != head)
{
temp = temp->next;
}
temp->next = newnode;
newnode->next = head;
}
}

// DELETE
void deleteNode(int key)
{
struct node *curr = head, *prev = NULL;

if(head == NULL) return;

do {
if(curr->data == key)
{
if(curr == head)
{
struct node *temp = head;
while(temp->next != head)
temp = temp->next;

if(head == head->next)
{
head = NULL;
}
else
{
temp->next = head->next;
head = head->next;
}
}
else
{
prev->next = curr->next;
 }
free(curr);
return;
}
prev = curr;
curr = curr->next;
} while(curr != head);
}

// SEARCH
void search(int key)
{
struct node *temp = head;
int pos = 1;

if(head == NULL) return;

do {
if(temp->data == key)
{
printf("Found %d at position %d\n", key, pos);
return;
}
temp = temp->next;
pos++;
} while(temp != head);

printf("Not Found\n");
}

// DISPLAY
void display()
{
struct node *temp = head;

printf("CLL: ");

if(head == NULL)
{
printf("Empty\n");
return;
}

do {
printf("%d -> ", temp->data);
temp = temp->next;
} while(temp != head);

printf("(Head)\n");
}

int main()
{
insert(5);
insert(10);
insert(15);
 display();

search(10);

deleteNode(10);

display();

return 0;
}

Output

CLL: 5 -> 10 -> 15 -> (Head)

Found 10 at position 2
CLL: 5 -> 15 -> (Head)

Viva questions:

[Link] is a circular linked list?

[Link] are the types of circular linked lists?

[Link] are the purpose of the header pointer?

[Link] do you insert a node at the end ?

 [Link] is the structure of a node in a circular linked list?

[Link] do you delete the first node?

Result

Thus, the C programs for Circular Linked List were successfully implemented. The operations such as
insertion, deletion, and searching were performed and verified successfully.

1. Circular Linked List forms a loop structure, where the last node connects back to the head
node.

The output of all operations was executed successfully and verified with the expected results.
Aim
To write a C program to reverse a given string and display the reversed string.

Software Required
 Turbo C / GCC Compiler / Code::Blocks / Visual Studio Code

 Windows / Linux Operating System

Theory
A string is a sequence of characters terminated by the null character ('\0'). Reversing a string means
arranging its characters in the opposite order.
For example:
 Input: HELLO

 Output: OLLEH
A string can be reversed by swapping the first character with the last character, the second character with the
second-last character, and so on until the middle of the string is reached.

Syntax
strrev(string_name); // Turbo C only

Algorithm
1. Start the program.
2. Declare a character array to store the string.
3. Read the input string from the user.
4. Find the length of the string.
5. Initialize two variables:

EX NO: 3A
Implementation of String Reverse Operation
DATE:

o i=0

o j = length - 1

6. Swap the characters at positions i and j.

7. Increment i and decrement j.
8. Repeat Steps 6–7 until i >= j.
9. Display the reversed string.
10. Stop the program.

Program
#include <stdio.h>
#include <string.h>

int main()
{
char str[100], temp;
int i, j;

printf("Enter a string: ");

fgets(str, sizeof(str), stdin);

// Remove newline character if present

str[strcspn(str, "\n")] = '\0';

j = strlen(str) - 1;

for(i = 0; i < j; i++, j--)

{
temp = str[i];
str[i] = str[j];
str[j] = temp;
}
printf("Reversed string: %s\n", str);
return 0;
}

Output

Enter a string: Computer

Reversed string: retupmoC

Viva Question

1. Define a string in C.

2. Explain the concept of string reversal.

3. Use strlen() to determine string length.

4. Write a C program to reverse a string using loops.

5. Explain the time complexity of the string reversal algorithm.

Result
The C program to reverse a given string was executed successfully, and the reversed string was displayed
correctly.

[Link]:3B Implementation of Expression Evaluation

DATE:

Aim

To write a C program to evaluate a postfix expression using the stack data structure.

Software Required

 Turbo C / GCC Compiler / Code::Blocks / Visual Studio Code

 Windows / Linux Operating System
Theory

Expression evaluation is the process of computing the value of an arithmetic expression. In stack
applications, postfix (Reverse Polish Notation) expressions are easier to evaluate because they do not require
parentheses or operator precedence rules.
In postfix evaluation:
 Operands are pushed onto the stack.

 When an operator is encountered, the required operands are popped from the stack.
 The operation is performed, and the result is pushed back onto the stack.
 After processing the entire expression, the final result remains on the top of the stack.
Example:
Postfix Expression:
23*54*+9-
Evaluation:
2×3=6
5 × 4 = 20
6 + 20 = 26
26 – 9 = 17
Final Result = 17

Syntax

push(value);
pop();

switch(operator)
{
case '+': result = op1 + op2; break;
case '-': result = op1 - op2; break;
case '*': result = op1 * op2; break;
case '/': result = op1 / op2; break;
}
Algorithm

1. Start the program.

2. Read the postfix expression.
3. Initialize an empty stack.
4. Scan the expression from left to right.
5. If the symbol is an operand, push it onto the stack.
6. If the symbol is an operator:
o Pop the top two operands.

o Perform the operation.

o Push the result back onto the stack.

7. Repeat until the end of the expression.

8. Display the value at the top of the stack as the final result.
9. Stop the program.

Program

#include <stdio.h>
#include <ctype.h>\
int stack[100];
int top = -1;
void push(int value)
{
stack[++top] = value;
}
int pop()
{
return stack[top--];
}
int main()
{
char exp[100];
int i, op1, op2, result;
printf("Enter Postfix Expression: ");
scanf("%s", exp);

for(i = 0; exp[i] != '\0'; i++)

{
if(isdigit(exp[i]))
{
push(exp[i] - '0')
}
else
{
op2 = pop();
 op1 = pop();

switch(exp[i])
{
case '+':
push(op1 + op2);
break;
case '-':
push(op1 - op2);
break;
case '*':
push(op1 * op2);
break;
case '/':
push(op1 / op2);
break;
}
}
}

result = pop();
printf("Result = %d", result);
return 0;
}

Output

Enter Postfix Expression: 23*54*+9-

Result = 17

Viva Questions

1. What is an arithmetic expression?

2. What are the different types of expressions?

3. Which data structure is commonly used for postfix expression evaluation?

 4. Why is postfix expression evaluation easier than infix expression evaluation?

5. What are the basic operations performed on a stack?

Result
The C program to evaluate a postfix expression using a stack was executed successfully, and the correct
result was obtained.

EX NO:4A
Implementation of Circular Queue
DATE:

Aim

To write a C program to implement the operations of a Circular Queue such as insertion (enqueue), deletion
(dequeue), and display.

Software Required

 Turbo C / GCC Compiler / Code::Blocks / Visual Studio Code

 Windows / Linux Operating System

Theory

A Circular Queue is a linear data structure that follows the FIFO (First In, First Out) principle. Unlike a
linear queue, the last position of the queue is connected back to the first position, forming a circular
structure.
In a circular queue, when the rear reaches the last position of the array and there is free space at the
beginning, the rear wraps around to the first position. This makes efficient use of memory and avoids the
wastage of space that occurs in a linear queue.
The two pointers used are:
 Front – Points to the first element.

 Rear – Points to the last element.

The queue is full when:
(front == (rear + 1) % MAX)
The queue is empty when:
front == -1

Syntax

enqueue(value);
dequeue();
display();

Algorithm
Enqueue Operation
1. Start.
2. Check whether the queue is full.
3. If full, display Queue Overflow.
4. Otherwise:
o If the queue is empty, set front = rear = 0.
 o Else update rear = (rear + 1) % MAX.

5. Insert the element at queue[rear].

6. Stop.
Dequeue Operation
1. Start.
2. Check whether the queue is empty.
3. If empty, display Queue Underflow.
4. Otherwise delete the element at front.
5. If front == rear, set front = rear = -1.
6. Else update front = (front + 1) % MAX.
7. Stop.

Program

#include <stdio.h>

#define MAX 5

int queue[MAX];
int front = -1, rear = -1;

void enqueue(int value)

{
if ((rear + 1) % MAX == front)
{
printf("Queue Overflow\n");
return;
}

if (front == -1)
front = rear = 0;
else
rear = (rear + 1) % MAX;

queue[rear] = value;
}

void dequeue()
{
if (front == -1)
{
printf("Queue Underflow\n");
return;
}

printf("Deleted element: %d\n", queue[front]);

if (front == rear)
front = rear = -1;
else
 front = (front + 1) % MAX;
}

void display()
{
int i;

if (front == -1)
{
printf("Queue is Empty\n");
return;
}

printf("Queue Elements: ");

i = front;
while (1)
{
printf("%d ", queue[i]);

if (i == rear)
break;

i = (i + 1) % MAX;
}

printf("\n");
}

int main()
{
enqueue(10);
enqueue(20);
enqueue(30);
display();

dequeue();
display();

enqueue(40);
enqueue(50);
enqueue(60);
display();

return 0;
}

Output

Queue Elements: 10 20 30
Deleted element: 10
Queue Elements: 20 30
Queue Elements: 20 30 40 50 60

Viva Questions

1. What is a Circular Queue?

 2. What is the main advantage of a Circular Queue over a Linear Queue?

3. What condition indicates that a Circular Queue is full?

4. What condition indicates that a Circular Queue is empty?

5. Which principle does a Circular Queue follow? (FIFO or LIFO?)

Result
 The C program to implement the operations of a Circular Queue was executed successfully, and the
enqueue, dequeue, and display operations were performed correctly.

EX NO :4B
Implementation of Priority Queue
DATE:

Aim

To write a C program to implement the operations of a Priority Queue, such as insertion (enqueue), deletion
(dequeue), and display.

Software Required

 Turbo C / GCC Compiler / Code::Blocks / Visual Studio Code

 Windows / Linux Operating System

Theory

A Priority Queue is a special type of queue in which each element is associated with a priority. Elements
with higher priority are removed before elements with lower priority. If two elements have the same priority,
they are served according to the First In, First Out (FIFO) principle.
Unlike a normal queue, deletion is based on the priority of the elements rather than the order in which they
were inserted.
Operations of a Priority Queue:
 Insertion (Enqueue): Inserts an element along with its priority.

 Deletion (Dequeue): Removes the element with the highest priority.

 Display: Displays all the elements along with their priorities.

Syntax

enqueue(data, priority);
dequeue();
display();

Algorithm

Insertion (Enqueue)
1. Start.
2. Check whether the queue is full.
3. Read the element and its priority.
4. Insert the element into the queue.
5. Arrange the elements based on priority.
6. Stop.
Deletion (Dequeue)
 1. Start.
2. Check whether the queue is empty.
3. Remove the element with the highest priority.
4. Shift the remaining elements.
5. Display the deleted element.
6. Stop.

Program

#include <stdio.h>
#define MAX 5
struct PriorityQueue
{
int data;
int priority;
};
struct PriorityQueue pq[MAX];
int size = 0;
void enqueue(int value, int priority)
{
int i;
if(size == MAX)
{
printf("Queue Overflow\n");
return;
}
i = size - 1;

while(i >= 0 && pq[i].priority > priority)

{
pq[i + 1] = pq[i];
i--;
}
pq[i + 1].data = value;
pq[i + 1].priority = priority;
size++;
}
void dequeue()
{
int i;
if(size == 0)
{
printf("Queue Underflow\n");
return;

printf("Deleted Element: %d\n", pq[0].data);

for(i = 0; i < size - 1; i++)
{
pq[i] = pq[i + 1];
}
size--;
}
void display()
{
int i;
if(size == 0)
{
printf("Queue is Empty\n");
return;
}
printf("Element\tPriority\n");
for(i = 0; i < size; i++)
{
printf("%d\t%d\n", pq[i].data, pq[i].priority);
}
}
int main()
{
enqueue(10, 3);
enqueue(20, 1);
enqueue(30, 2);
display();
dequeue();
display();
return 0;
}

Output

Element Priority
20 1
30 2
10 3
Deleted Element: 20
Element Priority
30 2
10 3

Viva Questions

1. What is a Priority Queue?

2. How does a Priority Queue differ from a normal queue?

3. What is meant by the priority of an element?

 4. What happens if two elements have the same priority?

5. Mention two real-world applications of a Priority Queue.

Result

The C program to implement the operations of a Priority Queue was executed successfully, and the
 insertion, deletion, and display operations were performed correctly based on element priority.

EX NO :5
Traversal Operation in One Dimensional Array
DATE:

Aim

To write a C program to perform the traversal operation on a one-dimensional array and display all its
elements.

Software Required

 Turbo C / GCC Compiler / Code::Blocks / Visual Studio Code

 Windows / Linux Operating System

Theory

Traversal is one of the fundamental operations performed on an array. It involves visiting each element of
the array exactly once to process or display its value.
During traversal, the program starts from the first element and continues sequentially until the last element.
Since arrays store elements in contiguous memory locations, traversal is efficient and is commonly
implemented using a for loop.
Traversal is widely used for displaying, searching, updating, and processing array elements.

Syntax

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

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

Algorithm

1. Start the program.

2. Declare an array and a variable to store the number of elements.
3. Read the size of the array.
4. Read the array elements from the user.
5. Use a for loop to visit each element from the first to the last.
6. Display each element.
7. Stop the program.

Program
#include <stdio.h>

int main()
{
int arr[100], n, i;

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

scanf("%d", &n);

printf("Enter the array elements:\n");

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

printf("Array elements are:\n");

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

return 0;
}

Output

Enter the number of elements: 5

Enter the array elements:
10
20
30
40
50

Array elements are:

10 20 30 40 50

Viva Questions

1. What is traversal in an array?

2. Why is the traversal operation performed?

3. Which loop is commonly used for array traversal in C?

 4. What is the time complexity of array traversal?

5. Can traversal be performed on an empty array? Why?

Result
 The C program to perform the traversal operation on a one-dimensional array was executed
successfully, and all the array elements were displayed correctly.

EX NO :6
Implementation of AVL Tree Rotation
DATE

Aim

To implement AVL Tree rotations and perform insertion operations to maintain a balanced Binary Search
Tree using AVL Tree rotations.

Software Required

 Operating System: Windows/Linux

 Compiler: GCC (GNU Compiler Collection) or Turbo C/C++
 Programming Language: C
 IDE (Optional): Code::Blocks, Dev-C++, Visual Studio Code

Theory

An AVL Tree (Adelson-Velsky and Landis Tree) is a self-balancing Binary Search Tree (BST) in which
the difference between the heights of the left and right subtrees of any node is called the Balance Factor.
Balance Factor = Height of Left Subtree − Height of Right Subtree
For every node in an AVL tree, the balance factor must be -1, 0, or +1.
Whenever an insertion or deletion causes the balance factor to become less than -1 or greater than +1, the
tree becomes unbalanced. To restore balance, AVL trees perform one of the following rotations:
1. Left Rotation (LL Rotation)
2. Right Rotation (RR Rotation)
3. Left-Right Rotation (LR Rotation)
4. Right-Left Rotation (RL Rotation)
These rotations ensure that the height of the tree remains approximately O(log n), making search, insertion,
and deletion operations efficient.

Advantages
 Maintains a balanced tree automatically.

 Faster searching compared to an unbalanced BST.

 Search, insertion, and deletion operations take O(log n) time.

Applications
 Database indexing

 Memory management
 Dictionary implementation
  Compiler symbol tables
 Routing tables

Syntax

Structure Declaration
struct Node
{
int data;
struct Node *left;
struct Node *right;
int height;
};
Left Rotation
struct Node* leftRotate(struct Node *x);
Right Rotation
struct Node* rightRotate(struct Node *y);
Insert Function
struct Node* insert(struct Node *node, int key);

Algorithm

1. Start.
2. Create a new node with the given key.
3. If the tree is empty, make the new node the root.
4. Insert the node following Binary Search Tree rules.
5. Update the height of each ancestor node.
6. Calculate the balance factor.
7. If the balance factor is greater than 1 or less than -1:
o Perform Right Rotation (LL Case).

o Perform Left Rotation (RR Case).

o Perform Left-Right Rotation (LR Case).

o Perform Right-Left Rotation (RL Case).

8. Return the balanced tree.

9. Display the tree using inorder traversal.
10. Stop.

Program

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

struct Node
{
int data;
struct Node *left;
 struct Node *right;
int height;
};

int height(struct Node *N)

{
if (N == NULL)
return 0;
return 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->data = key;
node->left = NULL;
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;
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->data)
 node->left = insert(node->left, key);
else if (key > node->data)
node->right = insert(node->right, key);
else
return node;
node->height = 1 + max(height(node->left), height(node->right));
int balance = getBalance(node);
// LL Case
if (balance > 1 && key < node->left->data)
return rightRotate(node);
// RR Case
if (balance < -1 && key > node->right->data)
return leftRotate(node);
// LR Case
if (balance > 1 && key > node->left->data)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
// RL Case
if (balance < -1 && key < node->right->data)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void inorder(struct Node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main()
{
struct Node *root = NULL;
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 10);
root = insert(root, 25);
root = insert(root, 40);
root = insert(root, 50);

printf("Inorder Traversal of AVL Tree:\n");

inorder(root);

return 0;
}

Output

Inorder Traversal of AVL Tree:

10 20 25 30 40 50
Viva Questions

What is an AVL Tree?

What is the balance factor in an AVL Tree, and how is it calculated?

What are the four types of rotations performed in an AVL Tree?

Why are rotations necessary in an AVL Tree?

What is the time complexity of search, insertion, and deletion operations in an AVL Tree?

Result

Thus, the program to implement AVL Tree Rotations was successfully executed. The AVL Tree remained
balanced after every insertion by performing the required rotations, and the inorder traversal displayed the
elements in sorted order.
 EX NO :7
Query And Update Operations on Balanced BST’s
DATE :

Aim

To implement query and update operations on a Balanced Binary Search Tree (BST) and analyze their
efficiency.

Software Required

 Operating System: Windows/Linux

 Compiler: GCC (GNU Compiler Collection) or Turbo C/C++
 Programming Language: C
 IDE (Optional): Code::Blocks, Dev-C++, Visual Studio Code

Theory

A Balanced Binary Search Tree (Balanced BST) is a Binary Search Tree in which the height of the tree is
maintained close to log₂(n). Examples include AVL Trees and Red-Black Trees. Keeping the tree balanced
ensures that searching, insertion, deletion, and update operations remain efficient.
Query Operations
Query operations retrieve information from the tree without modifying its structure. Common query
operations include:
 Searching for a key.

 Finding the minimum and maximum elements.

 Performing inorder, preorder, and postorder traversals.
Update Operations
Update operations modify the contents or structure of the tree. They include:
 Inserting a new node.

 Deleting an existing node.

 Updating the value of a node (typically by deleting the old key and inserting the new key while
maintaining BST properties).
A balanced BST maintains its height after every update, ensuring that all operations execute efficiently.
Advantages
 Fast search operations.

 Efficient insertion and deletion.

 Maintains sorted data automatically.
 Guarantees O(log n) time complexity for most operations.
Applications
  Database indexing
 File systems
 Memory management
 Symbol tables in compilers
 Search engines

Syntax

Structure Declaration
struct Node
{
int data;
struct Node *left;
struct Node *right;
};
Search Function
struct Node* search(struct Node *root, int key);
Insert Function
struct Node* insert(struct Node *root, int key);
Delete Function
struct Node* deleteNode(struct Node *root, int key);

Algorithm

1. Start.
2. Create an empty BST.
3. Insert the required elements into the tree.
4. Accept the user's choice.
5. If the choice is Search, locate the required key.
6. If the choice is Insert, insert the new key while maintaining BST properties.
7. If the choice is Delete, remove the specified key and rearrange the tree.
8. Display the inorder traversal after every update.
9. Repeat until the user exits.
10. Stop.

Program

#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *left, *right;
};
struct Node* newNode(int item)
{
 struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
struct Node* insert(struct Node* root, int key)
{
if(root == NULL)
return newNode(key);
if(key < root->data)
root->left = insert(root->left, key);
else if(key > root->data)
root->right = insert(root->right, key);
return root;
}
struct Node* search(struct Node* root, int key)
{
if(root == NULL || root->data == key)
return root;
if(key < root->data)
return search(root->left, key);
return search(root->right, key);
}
void inorder(struct Node* root)
{
if(root != NULL)
{
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main()
{
struct Node *root = NULL;
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);
int key = 40;
if(search(root, key))
printf("\nElement %d found.", key);
else
printf("\nElement %d not found.", key);
return 0;
}

Output

Inorder Traversal: 20 30 40 50 60 70 80
Element 40 found.

Viva Questions

1. What is a Balanced Binary Search Tree (BST)?

2. What is the difference between query operations and update operations in a BST?

3. Why is balancing important in a Binary Search Tree?

4. What is the average time complexity of search, insertion, and deletion in a

balanced BST?

5. Name any two self-balancing Binary Search Trees.

Result
Thus, the program to perform Query and Update Operations on a Balanced BST was successfully
executed. The search, insertion, and update operations were performed correctly while preserving the Binary
Search Tree properties.
 EX NO :8
Implementation Of Quick Sort Algorithm
DATE:

Aim:

To implement the Quick Sort algorithm for sorting a list of elements in ascending order.

Software Required

 Operating System: Windows/Linux

 Compiler: GCC (GNU Compiler Collection) or Turbo C/C++
 Programming Language: C
 IDE (Optional): Code::Blocks, Dev-C++, Visual Studio Code

Theory

Quick Sort is an efficient divide-and-conquer sorting algorithm. It works by selecting a pivot element
from the array and partitioning the remaining elements into two subarrays:
 Elements smaller than the pivot are placed to its left.

 Elements greater than the pivot are placed to its right.

The same process is recursively applied to the left and right subarrays until the entire array is sorted.
Advantages
 Efficient for large datasets.

 In-place sorting algorithm (requires very little extra memory).

 Average time complexity is O(n log n).
Disadvantages
 Worst-case time complexity is O(n²) when the pivot is chosen poorly.

 Recursive implementation may use additional stack space.

Applications
 Database sorting

 Searching algorithms
 Operating systems
 Scientific computing
 Large-scale data processing

Syntax

Quick Sort Function

void quickSort(int arr[], int low, int high);
Partition Function
int partition(int arr[], int low, int high);

Algorithm

1. Start.
2. Read the number of elements in the array.
3. Read the array elements.
4. Select the last element as the pivot.
5. Partition the array so that elements smaller than the pivot are placed before it and larger elements
after it.
6. Recursively apply Quick Sort to the left subarray.
7. Recursively apply Quick Sort to the right subarray.
8. Repeat until the entire array is sorted.
9. Display the sorted array.
10. Stop.

Program

#include <stdio.h>

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[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

quickSort(arr, 0, n - 1);

printf("Sorted array: ");

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

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

return 0;
}

Output

Sorted array: 11 12 22 25 34 64 90

Viva Questions

1. What is the principle used in the Quick Sort algorithm?

2. What is the role of the pivot element in Quick Sort?

3. What are the best, average, and worst-case time complexities of Quick Sort?

4. Why is Quick Sort considered an in-place sorting algorithm?

 5. What is the difference between Quick Sort and Merge Sort?

Result
Thus, the program to implement the Quick Sort algorithm was executed successfully, and the given array
was sorted in ascending order.

EX NO:8B
Implementation Of Heap Sort Algorithm
DATE:

Aim

To implement the Heap Sort algorithm for sorting a list of elements in ascending order.

Software Required

 Operating System: Windows/Linux

 Compiler: GCC (GNU Compiler Collection) or Turbo C/C++
 Programming Language: C
 IDE (Optional): Code::Blocks, Dev-C++, Visual Studio Code

Theory

Heap Sort is a comparison-based sorting algorithm that uses the Binary Heap data structure. A binary heap
is a complete binary tree that satisfies the heap property.
In Max Heap, the value of the parent node is greater than or equal to its child nodes. Heap Sort first builds a
max heap from the given array. The largest element (root of the heap) is then swapped with the last element
of the heap, and the heap size is reduced by one. The process is repeated until all elements are sorted.
Heap Sort performs sorting in-place, requiring no additional memory for another array.
Advantages
 Guaranteed time complexity of O(n log n).

 Efficient for large datasets.

 In-place sorting algorithm.
 Does not require additional memory.
Disadvantages
 Not a stable sorting algorithm.

 Usually slower than Quick Sort in practice.

Applications
 Priority Queue implementation

 Operating Systems (CPU Scheduling)

 Graph Algorithms
 Database systems
 Embedded systems
Syntax

Heapify Function
void heapify(int arr[], int n, int i);
Heap Sort Function
void heapSort(int arr[], int n);

Algorithm

1. Start.
2. Read the number of elements in the array.
3. Read the array elements.
4. Build a Max Heap from the given array.
5. Swap the root element with the last element.
6. Reduce the heap size by one.
7. Heapify the root element to restore the heap property.
8. Repeat Steps 5–7 until all elements are sorted.
9. Display the sorted array.
10. Stop.

Program

#include <stdio.h>

void swap(int *a, int *b)

{
int temp = *a;
*a = *b;
*b = temp;
}

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

{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

if (largest != i)
{
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
 }
}

void heapSort(int arr[], int n)

{
int i;

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

heapify(arr, n, i);

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

{
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}

int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);

heapSort(arr, n);

printf("Sorted array:\n");

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

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

return 0;
}

Output

Sorted array:
5 6 7 11 12 13

Viva Questions

1. What is a Binary Heap?

2. What is the difference between a Max Heap and a Min Heap?

 3. What is the time complexity of Heap Sort in the best, average, and worst cases?

4. Why is Heap Sort considered an in-place sorting algorithm?

5. Is Heap Sort a stable sorting algorithm? Why or why not?

Result
Thus, the program to implement the Heap Sort algorithm was executed successfully, and the given array
was sorted in ascending order.
 EX NO:9A
Implementation of Binary Search Algorithm
DATE:

Aim

To implement the Binary Search algorithm to search for a given element in a sorted array.

Software Required

 Operating System: Windows/Linux

 Compiler: GCC (GNU Compiler Collection) or Turbo C/C++
 Programming Language: C
 IDE (Optional): Code::Blocks, Dev-C++, Visual Studio Code

Theory

Binary Search is an efficient searching algorithm used to find the position of a target element in a sorted
array. It works by repeatedly dividing the search interval into two halves.
The algorithm begins by comparing the target element with the middle element of the array:
 If the target is equal to the middle element, the search is successful.

 If the target is smaller, the search continues in the left half.

 If the target is larger, the search continues in the right half.
This process is repeated until the element is found or the search interval becomes empty.

Advantages
 Faster than Linear Search for sorted data.

 Requires fewer comparisons.

 Time complexity is O(log n).

Disadvantages
 Works only on sorted arrays.

 Not suitable for frequently changing datasets without sorting.

Applications
 Database indexing

 Dictionary lookup
 Searching in sorted files
 Library management systems
  Searching records in large datasets

Syntax

Binary Search Function

int binarySearch(int arr[], int low, int high, int key);

Algorithm

1. Start.
2. Read the number of elements in the array.
3. Read the array elements in sorted order.
4. Read the element to be searched.
5. Set low = 0 and high = n - 1.
6. Calculate the middle index:
o mid = (low + high) / 2

7. Compare the key with arr[mid].

8. If the key is equal to arr[mid], display the position of the element.
9. If the key is smaller, set high = mid - 1.
10. If the key is greater, set low = mid + 1.
11. Repeat Steps 6–10 until the element is found or low > high.
12. If the element is not found, display an appropriate message.
13. Stop.

Program

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int key)

{
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, 60, 70};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 40;

int result = binarySearch(arr, 0, n - 1, key);

if (result == -1)
printf("Element not found.");
else
printf("Element %d found at position %d.", key, result + 1);

return 0;

Output

Element 40 found at position 4.

Viva Questions

1. What is Binary Search?

2. What is the prerequisite for performing Binary Search?

3. What is the time complexity of Binary Search?

 4. How does Binary Search differ from Linear Search?

5. What happens if Binary Search is applied to an unsorted array?

Result
Thus, the program to implement the Binary Search algorithm was executed successfully, and the specified
element was searched efficiently in the sorted array.

EX NO : 9B
Implementation of Hashing Technique
DATE:

Aim

To implement the Hashing technique using a hash table to perform insertion and searching of elements.

Software Required

 Operating System: Windows/Linux

 Compiler: GCC (GNU Compiler Collection) or Turbo C/C++
 Programming Language: C
 IDE (Optional): Code::Blocks, Dev-C++, Visual Studio Code

Theory

Hashing is a technique used to store and retrieve data efficiently. It uses a hash function to map a key to an
index in a hash table, allowing fast insertion, deletion, and searching operations.
A hash function converts a key into an array index. A commonly used hash function is:
Hash Index = Key % Table Size
Sometimes, two different keys may produce the same hash index. This situation is called a collision. Various
collision resolution techniques are used, such as:
 Linear Probing

 Quadratic Probing
 Double Hashing
 Separate Chaining
In this experiment, Linear Probing is used to resolve collisions.
Advantages
 Fast insertion and searching.

 Average time complexity is O(1).

 Efficient memory access.
 Suitable for large datasets.
Disadvantages
 Performance decreases when many collisions occur.

 Requires a good hash function.

 Hash table size affects efficiency.
Applications
 Database indexing
  Compiler symbol tables
 Password verification
 Dictionary implementation
 Caching systems

Syntax

Hash Function
int hashFunction(int key)
{
return key % SIZE;
}
Insert Function
void insert(int key);
Search Function
int search(int key);

Algorithm

1. Start.
2. Declare a hash table and initialize all locations to -1.
3. Read the elements to be inserted.
4. Compute the hash index using:
o Index = Key % Table Size

5. If the location is empty, insert the element.

6. Otherwise, move to the next location using Linear Probing until an empty location is found.
7. To search for an element, compute its hash index.
8. Compare the key with the table entry.
9. If found, display its position; otherwise, continue linear probing until the key is found or the table is
fully searched.
10. Stop.

Program

#include <stdio.h>

#define SIZE 10

int hashTable[SIZE];

void initialize()
{
for(int i = 0; i < SIZE; i++)
hashTable[i] = -1;
}
void insert(int key)
{
int index = key % SIZE;

while(hashTable[index] != -1)
index = (index + 1) % SIZE;

hashTable[index] = key;
}

int search(int key)

{
int index = key % SIZE;
int start = index;

while(hashTable[index] != -1)
{
if(hashTable[index] == key)
return index;

index = (index + 1) % SIZE;

if(index == start)
break;
}

return -1;
}

int main()
{
initialize();

insert(25);
insert(35);
insert(15);
insert(45);

int key = 35;

int pos = search(key);

if(pos != -1)
printf("Element %d found at index %d", key, pos);
else
printf("Element not found");

return 0;
}

Output

Element 35 found at index 6

Hash Table after insertion
Index Value
0 -1
1 -1
Index Value
2 -1
3 -1
4 -1
5 25
6 35
7 15
8 45
9 -1

Viva Questions

1. What is hashing?

2. What is a hash function?

3. What is a collision in hashing?

4. Name any two collision resolution techniques.

5. What is the average time complexity of searching in a hash table?

Result
Thus, the program to implement the Hashing Technique using Linear Probing was executed successfully.
The elements were inserted into the hash table, and the required element was searched efficiently.
EX NO:10A
Implement the Breadth First Search Algorithm
DATE:

Aim

To implement the Breadth First Search (BFS) algorithm to traverse the vertices of a graph.

Software Required

 Operating System: Windows/Linux

 Compiler: GCC (GNU Compiler Collection) or Turbo C/C++
 Programming Language: C
 IDE (Optional): Code::Blocks, Dev-C++, Visual Studio Code

Theory

Breadth First Search (BFS) is a graph traversal algorithm that visits all the vertices of a graph level by
level. It starts from a source vertex, visits all its adjacent vertices first, and then moves to the next level of
vertices. BFS uses a Queue (FIFO - First In, First Out) data structure to keep track of the vertices that
need to be explored.
The algorithm marks each visited vertex to avoid revisiting it. BFS guarantees that the shortest path (in terms
of the number of edges) from the source vertex to every other reachable vertex is found in an unweighted
graph.
Advantages

 Finds the shortest path in an unweighted graph.

 Visits each vertex only once.
 Simple and efficient for graph traversal.
Disadvantages
 Requires additional memory for the queue.

 Not suitable for weighted shortest path problems.

Applications
 Shortest path in unweighted graphs.

 Social networking applications.

 Web crawling.
 Network broadcasting.
 GPS and routing systems.
Syntax

BFS Function
void BFS(int graph[][MAX], int start, int vertices);
Queue Operations
void enqueue(int item);
int dequeue();

Algorithm

1. Start.
2. Create a graph using an adjacency matrix.
3. Initialize all vertices as unvisited.
4. Select the starting vertex.
5. Mark the starting vertex as visited and insert it into the queue.
6. Repeat until the queue becomes empty:
o Remove a vertex from the front of the queue.

o Display the vertex.

o Visit all adjacent unvisited vertices.

o Mark each adjacent vertex as visited.

o Insert each visited vertex into the queue.

7. Stop.

Program

#include <stdio.h>

#define MAX 10

int graph[MAX][MAX];
int visited[MAX];
int queue[MAX];
int front = -1, rear = -1;

void enqueue(int item)

{
if (rear == MAX - 1)
return;

if (front == -1)
front = 0;

queue[++rear] = item;
}

int dequeue()
{
if (front == -1)
return -1;
int item = queue[front];

if (front == rear)
front = rear = -1;
else
front++;

return item;
}

void BFS(int start, int vertices)

{
enqueue(start);
visited[start] = 1;

while (front != -1)

{
int current = dequeue();
printf("%d ", current);

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

{
if (graph[current][i] == 1 && !visited[i])
{
visited[i] = 1;
enqueue(i);
}
}
}
}

int main()
{
int vertices = 5;

int g[5][5] = {
{0,1,1,0,0},
{1,0,0,1,1},
{1,0,0,0,0},
{0,1,0,0,0},
{0,1,0,0,0}
};

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

for(int j = 0; j < vertices; j++)
graph[i][j] = g[i][j];

printf("BFS Traversal starting from vertex 0:\n");

BFS(0, vertices);

return 0;
}

Output
BFS Traversal starting from vertex 0:
01234

Viva Questions

1. What is Breadth First Search (BFS)?

2. Which data structure is used in the BFS algorithm?

3. What is the time complexity of the BFS algorithm?

4. What is the difference between BFS and DFS?

5. What are the applications of the BFS algorithm?

Result
Thus, the program to implement the Breadth First Search (BFS) Algorithm was executed successfully.
The graph was traversed in level-by-level order using a queue, and all reachable vertices were visited.

EX NO:10B

DATE: Implementation of Depth First Search Algorithm

Aim

To implement the Depth First Search (DFS) algorithm to traverse the vertices of a graph.

Software Required

 Operating System: Windows/Linux

 Compiler: GCC (GNU Compiler Collection) or Turbo C/C++
 Programming Language: C
 IDE (Optional): Code::Blocks, Dev-C++, Visual Studio Code

Theory

Depth First Search (DFS) is a graph traversal algorithm that explores a graph by visiting a vertex and then
recursively visiting one of its unvisited adjacent vertices before backtracking. Unlike Breadth First Search
(BFS), which explores vertices level by level, DFS goes as deep as possible along a branch before moving to
another branch.
DFS uses either a Stack (LIFO - Last In, First Out) data structure or recursion to keep track of the
vertices to be explored. It marks each visited vertex to avoid revisiting the same vertex.
The time complexity of DFS is O(V + E), where V is the number of vertices and E is the number of edges.
Advantages
 Simple and easy to implement using recursion.

 Requires less memory than BFS for deep graphs.

 Useful for solving many graph-related problems.
Disadvantages
 Does not always find the shortest path.

 Recursive implementation may cause stack overflow for very large graphs.
Applications
 Topological sorting.

 Cycle detection in graphs.

 Path finding.
 Solving mazes.
 Connected component identification.

Syntax

DFS Function
void DFS(int vertex);
Recursive Function
void DFS(int vertex)
{
visited[vertex] = 1;
printf("%d ", vertex);

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

{
if(graph[vertex][i] == 1 && !visited[i])
DFS(i);
}
}

Algorithm

1. Start.
2. Create a graph using an adjacency matrix.
3. Initialize all vertices as unvisited.
4. Select the starting vertex.
5. Mark the starting vertex as visited.
6. Display the current vertex.
7. Visit each adjacent unvisited vertex recursively.
8. Repeat the process until all reachable vertices are visited.
9. Stop.

Program

#include <stdio.h>

#define MAX 10

int graph[MAX][MAX];
int visited[MAX];
int vertices = 5;

void DFS(int vertex)

{
visited[vertex] = 1;
printf("%d ", vertex);

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

{
if(graph[vertex][i] == 1 && !visited[i])
{
DFS(i);
}
}
}

int main()
{
 int g[5][5] = {
{0,1,1,0,0},
{1,0,0,1,1},
{1,0,0,0,0},
{0,1,0,0,0},
{0,1,0,0,0}
};

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

{
for(int j = 0; j < vertices; j++)
{
graph[i][j] = g[i][j];
}
}

printf("DFS Traversal starting from vertex 0:\n");

DFS(0);

return 0;
}

Output

DFS Traversal starting from vertex 0:

01342

Viva Questions

1. What is Depth First Search (DFS)?

2. Which data structure is used in the DFS algorithm?

3. What is the time complexity of the DFS algorithm?

 4. What is the difference between BFS and DFS?

5. Mention any two applications of the DFS algorithm.

Result
Thus, the program to implement the Depth First Search (DFS) Algorithm was executed successfully. The
graph was traversed by visiting each vertex as deep as possible before backtracking, and all reachable
vertices were visited successfully.

EX NO: 11A Implementation of Minimum Spanning Tree

DATE:

Aim

To implement Prim's Algorithm to find the Minimum Spanning Tree (MST) of a connected weighted
graph.

Software Required

 Operating System: Windows/Linux

 Compiler: GCC (GNU Compiler Collection) or Turbo C/C++
 Programming Language: C
 IDE (Optional): Code::Blocks, Dev-C++, Visual Studio Code

Theory

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, weighted, and undirected graph
that connects all the vertices without forming any cycles and has the minimum possible total edge weight.
Prim's Algorithm is a greedy algorithm that constructs the MST by starting from any vertex and repeatedly
selecting the edge with the minimum weight that connects a visited vertex to an unvisited vertex until all
vertices are included in the tree.
The time complexity of Prim's Algorithm is:
 O(V²) using an adjacency matrix.

 O(E log V) using a priority queue.

Advantages
 Produces a Minimum Spanning Tree with minimum cost.

 Efficient for dense graphs.

 Simple to implement.
Disadvantages
 Applicable only to connected, weighted, and undirected graphs.

 Less efficient than Kruskal's Algorithm for sparse graphs.

Applications

 Designing communication networks.

 Road and railway network planning.
 Electrical power distribution.
 Computer network design.
  Water pipeline construction.

Syntax

Prim's Function
void primMST(int graph[V][V]);
Minimum Key Function
int minKey(int key[], int mstSet[]);

Algorithm

1. Start.
2. Read the weighted graph using an adjacency matrix.
3. Select any vertex as the starting vertex.
4. Mark the starting vertex as visited.
5. Find the minimum weight edge connecting a visited vertex to an unvisited vertex.
6. Add the selected edge to the Minimum Spanning Tree.
7. Mark the new vertex as visited.
8. Repeat Steps 5–7 until all vertices are included in the MST.
9. Display the edges of the Minimum Spanning Tree and the total minimum cost.
10. Stop.

Program

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

#define V 5

int minKey(int key[], int mstSet[])

{
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

{
if (mstSet[v] == 0 && key[v] < min)
{
min = key[v];
min_index = v;
}
}

return min_index;
}

void printMST(int parent[], int graph[V][V])

{
printf("Edge \tWeight\n");
 for (int i = 1; i < V; i++)
printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
}

void primMST(int graph[V][V])

{
int parent[V];
int key[V];
int mstSet[V];

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

{
key[i] = INT_MAX;
mstSet[i] = 0;
}

key[0] = 0;
parent[0] = -1;

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] == 0 &&
graph[u][v] < key[v])
{
parent[v] = u;
key[v] = graph[u][v];
}
}
}

printMST(parent, graph);
}

int main()
{
int graph[V][V] =
{
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}
};

primMST(graph);

return 0;
}
Output

Edge Weight
0-1 2
1-2 3
0-3 6
1-4 5
Total Minimum Cost = 16

Viva Questions

1. What is a Minimum Spanning Tree (MST)?

2. Which type of graph is required for Prim's Algorithm?

3. What is the difference between Prim's Algorithm and Kruskal's Algorithm?

4. What is the time complexity of Prim's Algorithm using an adjacency matrix?

5. Mention any two real-world applications of the Minimum Spanning Tree.

Result
Thus, the program to implement Prim's Algorithm for finding the Minimum Spanning Tree (MST) was
executed successfully. The minimum spanning tree was generated, and the total minimum cost of connecting
all the vertices was obtained.
EX NO :11B
Implementation of Shortest Path Algorrithm
DATE:

Aim

To implement Dijkstra's Algorithm to find the shortest path from a source vertex to all other vertices in a
weighted graph.

Software Required

 Operating System: Windows/Linux

 Compiler: GCC (GNU Compiler Collection) or Turbo C/C++
 Programming Language: C
 IDE (Optional): Code::Blocks, Dev-C++, Visual Studio Code

Theory

The Shortest Path Algorithm is used to determine the minimum distance between a source vertex and all
other vertices in a weighted graph. Dijkstra's Algorithm is one of the most widely used shortest path
algorithms for graphs with non-negative edge weights.
The algorithm starts from a source vertex and repeatedly selects the unvisited vertex with the smallest known
distance. It then updates the distances of its adjacent vertices if a shorter path is found. This process
continues until the shortest distance to every vertex is determined.
The time complexity of Dijkstra's Algorithm is:
 O(V²) using an adjacency matrix.

 O((V + E) log V) using a priority queue.

Advantages
 Efficient for graphs with non-negative edge weights.

 Finds the shortest path from one source to all other vertices.
 Simple and widely used in graph applications.
Disadvantages
 Does not work correctly with negative edge weights.

 Can be slower for very large sparse graphs when implemented without a priority queue.
Applications

 GPS navigation systems.

 Computer network routing.
 Airline route planning.
 Robot path planning.
  Transportation and logistics.

Syntax

Dijkstra Function
void dijkstra(int graph[V][V], int source);
Minimum Distance Function
int minDistance(int dist[], int visited[]);

Algorithm

1. Start.
2. Read the weighted graph using an adjacency matrix.
3. Initialize the distance of all vertices as infinity.
4. Set the distance of the source vertex to 0.
5. Mark all vertices as unvisited.
6. Select the unvisited vertex with the smallest distance.
7. Mark the selected vertex as visited.
8. Update the distances of all adjacent vertices if a shorter path is found.
9. Repeat Steps 6–8 until all vertices are visited.
10. Display the shortest distance from the source to every vertex.
11. Stop.
Program

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

#define V 5

int minDistance(int dist[], int visited[])

{
int min = INT_MAX, min_index;

for(int v = 0; v < V; v++)

{
if(!visited[v] && dist[v] <= min)
{
min = dist[v];
min_index = v;
}
}

return min_index;
}

void dijkstra(int graph[V][V], int source)

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

dist[source] = 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,10,0,30,100},
{10,0,50,0,0},
{0,50,0,20,10},
{30,0,20,0,60},
{100,0,10,60,0}
};

dijkstra(graph, 0);

return 0;
}

Output

Vertex Distance from Source

0 0
1 10
2 50
3 30
4 60
Viva Questions

1. What is the purpose of Dijkstra's Algorithm?

2. Can Dijkstra's Algorithm be used for graphs with negative edge weights? Why?

3. What is the time complexity of Dijkstra's Algorithm using an adjacency matrix?

4. What is the difference between Dijkstra's Algorithm and Bellman-Ford Algorithm?

5. Mention any two real-world applications of the shortest path algorithm.

Result
Thus, the program to implement Dijkstra's Shortest Path Algorithm was executed successfully. The
shortest distance from the source vertex to all other vertices in the weighted graph was computed correctly.