Geethanjali College of Engineering & Technology

Department of CSE | UGC Autonomous

Data Structures Laboratory — 25CS12L01
[Link] I Year, II Semester | 2025-2026

Week 1: Arrays of Structures & Nested Structures

a) Arrays of Structures
Aim: Write a C program to implement arrays of structures.

Program:
#include <stdio.h>

struct Student {
char name[30];
int rollno;
float marks;
};

int main() {
struct Student s[3];
int i;
for (i = 0; i < 3; i++) {
printf("Enter name rollno marks: ");
scanf("%s %d %f", s[i].name, &s[i].rollno, &s[i].marks);
}
printf("\nName\tRoll\tMarks\n");
for (i = 0; i < 3; i++)
printf("%s\t%d\t%.2f\n", s[i].name, s[i].rollno, s[i].marks);
return 0;
}

Output:
Enter name rollno marks: Alice 101 89.5
Enter name rollno marks: Bob 102 76.0
Enter name rollno marks: Carol 103 92.3

Name Roll Marks

Alice 101 89.50
Bob 102 76.00
Carol 103 92.30

b) Nested Structures
Aim: Write a C program to implement nested structures.

Program:
#include <stdio.h>

struct Date {
int day, month, year;
};

struct Student {
 char name[30];
int rollno;
struct Date dob;
};

int main() {
struct Student s;
printf("Enter name rollno dob(dd mm yyyy): ");
scanf("%s %d %d %d %d",
[Link], &[Link],
&[Link], &[Link], &[Link]);
printf("Name: %s\n", [Link]);
printf("Roll: %d\n", [Link]);
printf("DOB: %d/%d/%d\n", [Link], [Link], [Link]);
return 0;
}

Output:
Enter name rollno dob(dd mm yyyy): Alice 101 15 6 2005
Name: Alice
Roll: 101
DOB: 15/6/2005

Viva Questions

Q1. What is a structure in C?

A: A structure is a user-defined data type that groups different types of variables under one name
using the struct keyword.

Q2. What is an array of structures?

A: It is an array where each element is a structure, used to store multiple records of the same type.

Q3. Why do we use an array of structures?

A: To store many records (like student details) together instead of creating separate variables for
each.
Q4. What is a nested structure in C?
A: A structure inside another structure. The inner structure is used as a member of the outer one.

Q5. Can we create an array of nested structures?

A: Yes. We declare an array of the outer structure type and access inner members using the dot
operator twice, e.g., arr[i].[Link].
Week 2: Complex Number Operations using Structures

a) Addition of Two Complex Numbers

Aim: Write a C program to implement addition of two complex numbers using structures.

Program:
#include <stdio.h>

struct Complex {
float real, imag;
};

int main() {
struct Complex c1, c2, sum;
printf("Enter c1 (real imag): ");
scanf("%f %f", &[Link], &[Link]);
printf("Enter c2 (real imag): ");
scanf("%f %f", &[Link], &[Link]);
[Link] = [Link] + [Link];
[Link] = [Link] + [Link];
printf("Sum = %.2f + %.2fi\n", [Link], [Link]);
return 0;
}

Output:
Enter c1 (real imag): 3 4
Enter c2 (real imag): 1 2
Sum = 4.00 + 6.00i

b) Multiplication of Two Complex Numbers

Aim: Write a C program to implement multiplication of two complex numbers using structures.

Program:
#include <stdio.h>

struct Complex {
float real, imag;
};

int main() {
struct Complex c1, c2, prod;
printf("Enter c1 (real imag): ");
scanf("%f %f", &[Link], &[Link]);
printf("Enter c2 (real imag): ");
scanf("%f %f", &[Link], &[Link]);
[Link] = [Link]*[Link] - [Link]*[Link];
[Link] = [Link]*[Link] + [Link]*[Link];
printf("Product = %.2f + %.2fi\n", [Link], [Link]);
return 0;
}

Output:
Enter c1 (real imag): 3 2
Enter c2 (real imag): 1 4
Product = -5.00 + 14.00i
Week 3: Unions & Pointers to Structures

a) Store Student Info Using Union

Aim: Write a C program to store the information (name, rollno, and branch) of a student using unions.

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

union StudentInfo {
char name[30];
int rollno;
char branch[20];
};

int main() {
union StudentInfo u;
strcpy([Link], "Alice");
printf("Name: %s\n", [Link]);
[Link] = 101;
printf("Roll: %d\n", [Link]);
strcpy([Link], "AIML");
printf("Branch: %s\n", [Link]);
return 0;
}

Output:
Name: Alice
Roll: 101
Branch: AIML

b) Passing Pointer to Structure (Inter-function Communication)

Aim: Write a C program to implement inter function communication by passing pointers to a
structure.

Program:
#include <stdio.h>

struct Student {
char name[30];
int rollno;
float marks;
};

void read(struct Student *s) {

printf("Enter name rollno marks: ");
scanf("%s %d %f", s->name, &s->rollno, &s->marks);
}

void print(struct Student *s) {

printf("Name: %s Roll: %d Marks: %.2f\n",
s->name, s->rollno, s->marks);
}

int main() {
 struct Student s;
read(&s);
print(&s);
return 0;
}

Output:
Enter name rollno marks: Bob 102 88.5
Name: Bob Roll: 102 Marks: 88.50
Week 4: File Handling – Copy & Merge Files

a) Copy Data from One File to Another

Aim: Write a C program to copy data from one file to another.

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

int main() {
FILE *src, *dest;
char ch;
src = fopen("[Link]", "r");
dest = fopen("[Link]", "w");
if (src == NULL || dest == NULL) {
printf("Error opening file.\n");
exit(1);
}
while ((ch = fgetc(src)) != EOF)
fputc(ch, dest);
fclose(src);
fclose(dest);
printf("File copied successfully.\n");
return 0;
}

Output:
File copied successfully.

b) Merge Two Files

Aim: Write a C program to merge two files.

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

int main() {
FILE *f1, *f2, *f3;
char ch;
f1 = fopen("[Link]", "r");
f2 = fopen("[Link]", "r");
f3 = fopen("[Link]", "w");
if (!f1 || !f2 || !f3) {
printf("Error opening files.\n");
exit(1);
}
while ((ch = fgetc(f1)) != EOF) fputc(ch, f3);
while ((ch = fgetc(f2)) != EOF) fputc(ch, f3);
fclose(f1); fclose(f2); fclose(f3);
printf("Files merged into [Link]\n");
return 0;
}

Output:
Files merged into [Link]
Week 5: File Operations using Command Line Arguments

a) Copy File using Command Line Arguments

Aim: Write a C program to copy data from one file to another using command line arguments.

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

int main(int argc, char *argv[]) {

FILE *src, *dest;
char ch;
if (argc != 3) {
printf("Usage: %s source dest\n", argv[0]);
exit(1);
}
src = fopen(argv[1], "r");
dest = fopen(argv[2], "w");
if (!src || !dest) {
printf("Error opening files.\n");
exit(1);
}
while ((ch = fgetc(src)) != EOF)
fputc(ch, dest);
fclose(src); fclose(dest);
printf("Copied %s to %s\n", argv[1], argv[2]);
return 0;
}

Output:
$ ./[Link] [Link] [Link]
Copied [Link] to [Link]

b) Merge Two Files using Command Line Arguments

Aim: Write a C program to merge two files using command line arguments.

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

int main(int argc, char *argv[]) {

FILE *f1, *f2, *f3;
char ch;
if (argc != 4) {
printf("Usage: %s f1 f2 merged\n", argv[0]);
exit(1);
}
f1 = fopen(argv[1], "r");
f2 = fopen(argv[2], "r");
f3 = fopen(argv[3], "w");
if (!f1 || !f2 || !f3) {
printf("Error opening files.\n");
exit(1);
}
while ((ch = fgetc(f1)) != EOF) fputc(ch, f3);
 while ((ch = fgetc(f2)) != EOF) fputc(ch, f3);
fclose(f1); fclose(f2); fclose(f3);
printf("Merged into %s\n", argv[3]);
return 0;
}

Output:
$ ./[Link] [Link] [Link] [Link]
Merged into [Link]

Viva Questions

Q1. What is a file in C?

A: A file is a named storage on disk used to permanently save data even after the program ends.

Q2. Why are files used in programming?

A: Files allow data to be stored permanently so it can be retrieved and reused even after the program
closes.

Q3. What is the difference between r, w, and a modes?

A: 'r' opens a file for reading only; 'w' opens for writing (creates or overwrites); 'a' opens for appending
data to the end of the file.

Q4. What are command line arguments?

A: Values passed to a program at the time of execution from the terminal, received via argc and argv[]
in main().

Q5. How are command line arguments passed to a program in C?

A: By declaring main() as int main(int argc, char *argv[]). argc holds the count of arguments (including
program name), and argv[] holds each argument as a string.
Week 6: Singly Linked List – Creation, Insertion, Deletion, Traversal

Aim: Write a program that uses functions to perform the following operations on singly linked list: i)
Creation ii) Insertion iii) Deletion iv) Traversal

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

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

struct Node *head = NULL;

void insert(int val) {

struct Node *n = (struct Node*)malloc(sizeof(struct Node));
n->data = val;
n->next = NULL;
if (head == NULL) { head = n; return; }
struct Node *temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = n;
}

void delete(int val) {

if (head == NULL) { printf("List is empty.\n"); return; }
if (head->data == val) { head = head->next; return; }
struct Node *temp = head;
while (temp->next != NULL && temp->next->data != val)
temp = temp->next;
if (temp->next == NULL) { printf("Not found.\n"); return; }
temp->next = temp->next->next;
}

void traverse() {
struct Node *temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main() {
insert(10); insert(20); insert(30);
printf("List: "); traverse();
delete(20);
printf("After deleting 20: "); traverse();
return 0;
}

Output:
List: 10 -> 20 -> 30 -> NULL
After deleting 20: 10 -> 30 -> NULL
Week 7: Doubly Linked List – Creation, Insertion, Deletion, Traversal

Aim: Write a program that uses functions to perform the following operations on doubly linked list: i)
Creation ii) Insertion iii) Deletion iv) Traversal

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

struct Node {
int data;
struct Node *prev, *next;
};

struct Node *head = NULL;

void insert(int val) {

struct Node *n = (struct Node*)malloc(sizeof(struct Node));
n->data = val; n->prev = NULL; n->next = NULL;
if (head == NULL) { head = n; return; }
struct Node *temp = head;
while (temp->next != NULL) temp = temp->next;
temp->next = n;
n->prev = temp;
}

void delete(int val) {

struct Node *temp = head;
while (temp != NULL && temp->data != val)
temp = temp->next;
if (temp == NULL) { printf("Not found.\n"); 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);
}

void traverse() {
struct Node *temp = head;
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main() {
insert(10); insert(20); insert(30);
printf("List: "); traverse();
delete(20);
printf("After deleting 20: "); traverse();
return 0;
}

Output:
List: 10 <-> 20 <-> 30 <-> NULL
After deleting 20: 10 <-> 30 <-> NULL
Week 8: Circular Linked List – Creation, Insertion, Deletion, Traversal

Aim: Write a program that uses functions to perform the following operations on circular linked list: i)
Creation ii) Insertion iii) Deletion iv) Traversal

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

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

struct Node *head = NULL;

void insert(int val) {

struct Node *n = (struct Node*)malloc(sizeof(struct Node));
n->data = val;
if (head == NULL) { n->next = n; head = n; return; }
struct Node *temp = head;
while (temp->next != head) temp = temp->next;
temp->next = n;
n->next = head;
}

void delete(int val) {

if (head == NULL) return;
struct Node *temp = head, *prev = NULL;
while (temp->data != val && temp->next != head) {
prev = temp; temp = temp->next;
}
if (temp->data != val) { printf("Not found.\n"); return; }
if (temp == head) {
struct Node *last = head;
while (last->next != head) last = last->next;
head = head->next;
last->next = head;
} else {
prev->next = temp->next;
}
free(temp);
}

void traverse() {
if (head == NULL) return;
struct Node *temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(head)\n");
}

int main() {
insert(10); insert(20); insert(30);
printf("List: "); traverse();
 delete(20);
printf("After deleting 20: "); traverse();
return 0;
}

Output:
List: 10 -> 20 -> 30 -> (head)
After deleting 20: 10 -> 30 -> (head)

Viva Questions

Q1. What is a linked list?

A: A linked list is a dynamic data structure where each element (node) stores data and a pointer to the
next node. Nodes are not stored in contiguous memory.

Q2. What are the advantages of a linked list over arrays?

A: Linked lists have dynamic size, support efficient insertion and deletion without shifting elements,
and can grow or shrink at runtime.

Q3. Why can't we access the last node directly in a singly linked list?
A: There is no index or direct address to the last node. We must start from head and traverse one by
one until we reach the node whose next pointer is NULL.

Q4. What will happen if the last node's pointer is not set to NULL?
A: The list will not have a proper terminator. Traversal will go beyond the last node into garbage
memory, causing undefined behaviour or an infinite loop.

Q5. What will happen if we do not use free() after deleting a node?
A: The deleted node's memory is not returned to the system, causing a memory leak. Over time this
wastes heap memory.
Week 9: Stack Operations using i) Arrays ii) ADT

i) Stack using Array

Aim: Write a program that implements stack operations using arrays.

Program:
#include <stdio.h>
#define MAX 5

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

void push(int val) {

if (top == MAX - 1) printf("Stack Overflow!\n");
else stack[++top] = val;
}

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

void display() {
int i;
if (top == -1) { printf("Stack is empty.\n"); return; }
for (i = top; i >= 0; i--) printf("%d ", stack[i]);
printf("\n");
}

int main() {
push(10); push(20); push(30);
printf("Stack: "); display();
pop();
printf("Stack: "); display();
return 0;
}

Output:
Stack: 30 20 10
Popped: 30
Stack: 20 10

ii) Stack using ADT (Linked List)

Aim: Write a program that implements stack operations using ADT.

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

struct Node {
int data;
struct Node *next;
};
struct Node *top = NULL;
 void push(int val) {
struct Node *n = (struct Node*)malloc(sizeof(struct Node));
n->data = val; n->next = top; top = n;
printf("Pushed: %d\n", val);
}

void pop() {
if (top == NULL) { printf("Stack Underflow!\n"); return; }
printf("Popped: %d\n", top->data);
top = top->next;
}

void display() {
struct Node *t = top;
while (t != NULL) { printf("%d ", t->data); t = t->next; }
printf("\n");
}

int main() {
push(10); push(20); push(30);
printf("Stack: "); display();
pop();
printf("Stack: "); display();
return 0;
}

Output:
Pushed: 10
Pushed: 20
Pushed: 30
Stack: 30 20 10
Popped: 30
Stack: 20 10

Viva Questions

Q1. What is a stack?

A: A stack is a linear data structure that works on LIFO — Last In First Out. The last element inserted
is the first one to be removed.

Q2. What is stack underflow?

A: It occurs when we try to pop from an empty stack (top == -1 in array implementation).

Q3. What is the time complexity of push and pop operations?

A: Both push and pop run in O(1) — constant time — because they only operate on the top of the
stack.

Q4. What are the applications of stacks?

A: Function call management, expression conversion and evaluation, undo/redo operations,
backtracking, and balanced parentheses checking.

Q5. Where is a stack used in real life?

A: Browser back button (page history), undo feature in text editors, and the CPU call stack for
managing function calls.
Week 10: Queue Operations using i) Arrays ii) ADT

i) Queue using Array

Aim: Write a program that implements queue operations using arrays.

Program:
#include <stdio.h>
#define MAX 5

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

void enqueue(int val) {

if (rear == MAX - 1) { printf("Queue Full!\n"); return; }
if (front == -1) front = 0;
queue[++rear] = val;
printf("Inserted: %d\n", val);
}

void dequeue() {
if (front == -1 || front > rear) printf("Queue Empty!\n");
else printf("Deleted: %d\n", queue[front++]);
}

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

int main() {
enqueue(10); enqueue(20); enqueue(30);
printf("Queue: "); display();
dequeue();
printf("Queue: "); display();
return 0;
}

Output:
Inserted: 10
Inserted: 20
Inserted: 30
Queue: 10 20 30
Deleted: 10
Queue: 20 30

ii) Queue using ADT (Linked List)

Aim: Write a program that implements queue operations using ADT.

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

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

 struct Node *front = NULL, *rear = NULL;

void enqueue(int val) {

struct Node *n = (struct Node*)malloc(sizeof(struct Node));
n->data = val; n->next = NULL;
if (rear == NULL) { front = rear = n; }
else { rear->next = n; rear = n; }
printf("Inserted: %d\n", val);
}

void dequeue() {
if (front == NULL) { printf("Queue Empty!\n"); return; }
printf("Deleted: %d\n", front->data);
front = front->next;
if (front == NULL) rear = NULL;
}

void display() {
struct Node *t = front;
while (t != NULL) { printf("%d ", t->data); t = t->next; }
printf("\n");
}

int main() {
enqueue(10); enqueue(20); enqueue(30);
printf("Queue: "); display();
dequeue();
printf("Queue: "); display();
return 0;
}

Output:
Inserted: 10
Inserted: 20
Inserted: 30
Queue: 10 20 30
Deleted: 10
Queue: 20 30

Viva Questions

Q1. What is a queue?

A: A queue is a linear data structure that follows FIFO — First In First Out. Elements are added at the
rear and removed from the front.

Q2. What is queue overflow?

A: It occurs when we try to insert into a full queue (rear == MAX-1 in array implementation).

Q3. What is the time complexity of enqueue and dequeue operations?

A: Both enqueue and dequeue run in O(1) — constant time.

Q4. Where are queues used in real life?

A: Printer spooling, CPU process scheduling, call centre waiting lines, and keyboard input buffers.

Q5. What will happen if we insert elements continuously in a simple queue implemented using an
array?
A: Once rear reaches the last index, no more insertions are allowed even if front positions are free
after deletions. This wastes space. A circular queue solves this.
Week 11: Infix to Postfix Conversion & Postfix Evaluation using Stack

Aim: Write a C program to convert infix expression to postfix notation and evaluate postfix expression
using stack.

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

/* --- Operator Stack (char) --- */

char opStack[100];
int opTop = -1;
void opPush(char c) { opStack[++opTop] = c; }
char opPop() { return opStack[opTop--]; }
char opPeek() { return opStack[opTop]; }

int precedence(char c) {
if (c == '+' || c == '-') return 1;
if (c == '*' || c == '/') return 2;
return 0;
}

void infixToPostfix(char *exp, char *result) {

int j = 0, i;
for (i = 0; exp[i] != '\0'; i++) {
char c = exp[i];
if (isalnum(c)) {
result[j++] = c;
} else if (c == '(') {
opPush(c);
} else if (c == ')') {
while (opTop != -1 && opPeek() != '(')
result[j++] = opPop();
opPop();
} else {
while (opTop != -1 && precedence(opPeek()) >= precedence(c))
result[j++] = opPop();
opPush(c);
}
}
while (opTop != -1) result[j++] = opPop();
result[j] = '\0';
}

/* --- Number Stack (int) --- */

int numStack[100];
int numTop = -1;
void numPush(int v) { numStack[++numTop] = v; }
int numPop() { return numStack[numTop--]; }

int evaluatePostfix(char *exp) {

int i;
for (i = 0; exp[i] != '\0'; i++) {
if (isdigit(exp[i])) {
numPush(exp[i] - '0');
} else {
 int b = numPop(), a = numPop();
if (exp[i] == '+') numPush(a + b);
if (exp[i] == '-') numPush(a - b);
if (exp[i] == '*') numPush(a * b);
if (exp[i] == '/') numPush(a / b);
}
}
return numPop();
}

int main() {
char infix[100], postfix[100];
printf("Enter infix expression: ");
scanf("%s", infix);
infixToPostfix(infix, postfix);
printf("Postfix: %s\n", postfix);
printf("Result: %d\n", evaluatePostfix(postfix));
return 0;
}

Output:
Enter infix expression: 3+4*2
Postfix: 342*+
Result: 11
Week 12: Binary Tree Traversal (Recursive & Non-Recursive)

i) Recursive Tree Traversal

Aim: Write a program to implement tree traversal methods (Recursive).

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

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

struct Node* createNode(int val) {

struct Node *n = (struct Node*)malloc(sizeof(struct Node));
n->data = val; n->left = n->right = NULL;
return n;
}

void inorder(struct Node *root) {

if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}

void preorder(struct Node *root) {

if (root == NULL) return;
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}

void postorder(struct Node *root) {

if (root == NULL) return;
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}

int main() {
/* 1
/ \
2 3
/ \
4 5 */
struct Node *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);

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

printf("Preorder: "); preorder(root); printf("\n");
printf("Postorder: "); postorder(root); printf("\n");
 return 0;
}

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

ii) Non-Recursive Inorder Traversal

Aim: Write a program to implement tree traversal methods (Non-Recursive).

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

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

struct Node* createNode(int val) {

struct Node *n = (struct Node*)malloc(sizeof(struct Node));
n->data = val; n->left = n->right = NULL;
return n;
}

void inorderIterative(struct Node *root) {

struct Node *stack[100];
int top = -1;
struct Node *curr = root;
while (curr != NULL || top != -1) {
while (curr != NULL) {
stack[++top] = curr;
curr = curr->left;
}
curr = stack[top--];
printf("%d ", curr->data);
curr = curr->right;
}
printf("\n");
}

int main() {
struct Node *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Inorder (non-recursive): ");
inorderIterative(root);
return 0;
}

Output:
Inorder (non-recursive): 4 2 5 1 3
Viva Questions

Q1. What is a tree in data structures?

A: A tree is a hierarchical non-linear data structure with a root node and subtrees of children, where
each node has at most one parent.

Q2. What is the height of a tree?

A: The number of edges on the longest path from the root to a leaf node.

Q3. What are the types of tree traversal?

A: Inorder (Left-Root-Right), Preorder (Root-Left-Right), Postorder (Left-Right-Root), and Level-Order
(Breadth-First).

Q4. Where are trees used in real life?

A: File systems (folder hierarchy), HTML/XML DOM, database indexing (B-trees), and compiler syntax
trees.

Q5. What is the maximum number of nodes at level l in a binary tree?

A: 2^l nodes (where the root is at level 0).

Q6. What is the maximum number of nodes in a binary tree of height h?

A: 2^(h+1) - 1 nodes (a full binary tree).
Week 13: Graph Traversal – DFS (Depth First Search)

Aim: Write a program to implement graph traversal method: DFS.

Program:
#include <stdio.h>
#define MAX 10

int adj[MAX][MAX];
int visited[MAX];
int n;

void dfs(int v) {
visited[v] = 1;
printf("%d ", v);
int i;
for (i = 0; i < n; i++)
if (adj[v][i] == 1 && visited[i] == 0)
dfs(i);
}

int main() {
int e, u, v, i;
printf("Enter number of vertices and edges: ");
scanf("%d %d", &n, &e);
printf("Enter edges (u v):\n");
for (i = 0; i < e; i++) {
scanf("%d %d", &u, &v);
adj[u][v] = 1;
adj[v][u] = 1;
}
printf("DFS starting from vertex 0: ");
dfs(0);
printf("\n");
return 0;
}

Output:
Enter number of vertices and edges: 4 4
Enter edges (u v):
0 1
0 2
1 3
2 3
DFS starting from vertex 0: 0 1 3 2
Week 14: Graph Traversal – BFS (Breadth First Search)

Aim: Write a program to implement graph traversal method: BFS.

Program:
#include <stdio.h>
#define MAX 10

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

void enqueue(int v) { queue[++rear] = v; }

int dequeue() { return queue[++front]; }
int isEmpty() { return front == rear; }

void bfs(int start) {

int i;
visited[start] = 1;
enqueue(start);
while (!isEmpty()) {
int v = dequeue();
printf("%d ", v);
for (i = 0; i < n; i++)
if (adj[v][i] == 1 && visited[i] == 0) {
visited[i] = 1;
enqueue(i);
}
}
}

int main() {
int e, u, v, i;
printf("Enter number of vertices and edges: ");
scanf("%d %d", &n, &e);
printf("Enter edges (u v):\n");
for (i = 0; i < e; i++) {
scanf("%d %d", &u, &v);
adj[u][v] = 1;
adj[v][u] = 1;
}
printf("BFS starting from vertex 0: ");
bfs(0);
printf("\n");
return 0;
}

Output:
Enter number of vertices and edges: 4 4
Enter edges (u v):
0 1
0 2
1 3
2 3
BFS starting from vertex 0: 0 1 2 3
Viva Questions

Q1. What is a graph in data structures?

A: A graph is a collection of vertices (nodes) connected by edges. It can be directed or undirected,
weighted or unweighted.

Q2. What are the components of a graph?

A: A graph has two components: vertices (nodes) and edges (connections between vertices).

Q3. What is a vertex?

A: A vertex is a fundamental unit of a graph, representing an entity or a point. Also called a node.

Q4. What is the degree of a vertex?

A: The number of edges connected to that vertex. In a directed graph, in-degree counts incoming and
out-degree counts outgoing edges.

Q5. How can graphs be represented in memory?

A: Using an adjacency matrix (2D array where adj[i][j]=1 means an edge exists) or an adjacency list
(array of linked lists storing neighbours).

Q6. What are the two main graph traversal algorithms?

A: DFS (Depth First Search) and BFS (Breadth First Search).

Q7. Which data structure is used in BFS?

A: A Queue (FIFO). Discovered neighbours are enqueued and visited in the order they were found.

Q8. Which data structure is used in DFS?

A: A Stack — either implicitly via recursion or using an explicit stack.

Q9. Where are graphs used in real life?

A: Maps and navigation (Google Maps), social networks, internet routing, dependency resolution, and
airline route planning.