0 ratings0% found this document useful (0 votes)
6 views57 pagesDAA Practical File
The document discusses asymptotic notation, time complexity, and space complexity in algorithm analysis, comparing Big O, Big Omega, and Big Theta notations. It also explores four major algorithm design techniques: Divide and Conquer, Greedy Algorithms, Dynamic Programming, and Backtracking, detailing their aims, typical algorithms, and complexities. Additionally, it includes implementations and analyses of Insertion Sort and Quick Sort algorithms with varying inputs.
Uploaded by
rahil902740Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0 ratings0% found this document useful (0 votes)
6 views57 pagesDAA Practical File
The document discusses asymptotic notation, time complexity, and space complexity in algorithm analysis, comparing Big O, Big Omega, and Big Theta notations. It also explores four major algorithm design techniques: Divide and Conquer, Greedy Algorithms, Dynamic Programming, and Backtracking, detailing their aims, typical algorithms, and complexities. Additionally, it includes implementations and analyses of Insertion Sort and Quick Sort algorithms with varying inputs.
Uploaded by
rahil902740Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 57
DAA practical file
1.Study and compare different asymptotic notation.
Aim:
In algorithm analysis, asymptotic notation is essential for understanding how an algorithm's
performance scales with input size. This can be a crucial factor in determining an
algorithm's efficiency in both time and space. Here, Ill explain and compare different
asymptotic notations: Big 0 (0), Big Omega (Q), and Theta (@). Then, Ill look at how they
relate to time complexity, space complexity, and some examples in C programming.
Time Complexity:
Refers to how the execution time of an algorithm increases with the size of the input.
Common complexities include:
0(1) - Constant time, such as accessing an element in an array.
O(n) ~ Linear time, such as iterating through an array.
O(n*2) - Quadratic time, such as a nested loop structure.
O(log n) ~ Logarithmic time, common in binary search.
O(n * log n) - Linearithmic time, typical for efficient sorting algorithms like mergesort and
heapsort,
Space complexity:
Measures the amount of memory an algorithm requires in relation to the input size.
Like time complexity, it uses asymptotic notations.
Algorithms may require space:
0(1) - Constant space, meaning space required does not grow with input size
O(n) - Linear space, such as using an array of size nnn.
0(n*2) ~ Quadratic space, typically seen in multidimensional data structures
Space complexity: The three main asymptotic notations used to describe the space
complexity of an algorithm are big 0, big Theta (6), and big Omega (0),
+ BigO
Used to describe the worst-case scenario of an algorithm's space complexity. It's the most
commonly used notation in algorithm analysis.
OF Seamed with OFEW Sanne + Big Theta
Used to describe the average-case scenario of an algorithm's space complexity. I's used
when the running time is the same for all cases
+ Big Omega
Used to describe the best-case scenario of an algorithm's space complexity. I's used to
describe the lower bound of an algorithm's running time.
Asymptotic notations are mathematical tools used to describe how an algorithm's efficiency
changes based on the size of its input. They can be used to compare multiple algorithms
and choose the best one.
Space complexity is the amount of memory an algorithm requires to solve a problem,
including the memory used by its inputs and any other memory used during execution.
CODE:
#include
// Example 1: 0(1) time complexity
void printFirstElement(int arr], int n) {
printf("%d\n", arr[0]); // Constant time operation
}
// Example 2: O(n) time complexity
void printAllElements(int arr, int n) {
for (inti = 0; i
void merge(int arr], int left, int mid, int right) {
intn1 = mid - left + 1;
int n2 = right - mid,
int L[n1], Rin],
for (int i= 0;i< n1;i++)
Uf] = arr[left + i];
for (int j = 0;)
void findMinCoins(int coins[], int n, int amount) {
inti, count = 0;
printf(‘Coins used: ");
for (/=n-1;i>=0;i-){
while (amount >= coins|il) {
amount -= coins[il;
printf(’sed ", coins[i]);
count++;
}
printf("\nTotal coins used: %d\n", count);
}
int main( {
int coins{] = (1, 5, 10, 25};
int amount = 63;
int n= sizeof(coins) / sizeof(coins{0));
findMinCoins(coins, n, amount);
return 0;
}
Output:
OF Seamed with OFEW Sanne eee
ee ae ee
ne
een ne
a a
emu a
a ese aeee
4, Backtracking
+ Aim: To solve problems incrementally, one decision at a time, and revert decisions
(backtrack) if a decision leads to a suboptimal solution
+ Algorithms: N-Queens, Sudoku Solver, Subset Sum, Hamiltonian Circuit
+ Time Complexity: Typically exponential 0(2n)0(2'n)O(2n), due to the exhaustive
search of all possibilities.
© Seamed wih ox scree + Space Complexity: Often 0(n)O(n)O(n) for recursion stack.
CODE:
include
#define N4
void printSolution(int board[NJIN]) {
for (int i= 0; 1< Ns i++) {
for (int j = 0; j < N; j++) {
printf(" %d", boardfili);
}
printf("\n");,
}
int isSafe(int boardNIIN, int row, int col) {
for (int i = 0; i< col; i++)
if (boardfrow)[i]) return 0;
for (int i= row, j = col:i >= 0 && | >= 0;
if (board[i]fi) return 0;
for (int i = row, j = col; j >= 0 &&i< N:i++, j-)
if (boardfilf}) return 0;
return 1;
int solveNQUEil(int board[NIINI, int col) {
if (col >= N) return 1;
for (int i = 0; 1< N; i++) {
if (isSafe(board, i col)) {
board[il[col] = 1;
if (solveNQUIIl(board, col + 1)) return 1;
board[ilicol] = 0;
OF Seamed with OFEW Sanne return 0;
}
void solveNQ0 {
int board[NJIN] = {{ 0, 0, 0, 0}, (0, 0, 0, 0}, 0, 0, 0,0}, { 0, 0, 0, 0}};
if (solveNQUIil(board, 0) == 0) {
printf("Solution does not exist");
return;
}
printSolution(board);
}
int maind {
solveNQ();
return 0;
}
Output:
OF Seamed with OFEW Sanne ce
a] ao
a)
a
O
Conan sistae
3. Implement the insertion sort and analyze the algorithm with different
inputs.
Aim:
To implement the insertion sort algorithm and analyze its time and space complexity with
different inputs.
Algorithm:
Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a
time. Itis much less efficient on large lists then other algorithms such as quicksort, heapsort,
© seamed nth oxen scree or merge sort. However, insertion sort has advantages in certain scenarios, especially when
working with small data sets or nearly sorted data.
Time Complexity:
1. Best Case: 0(n)O(n)O(n) - When the array is already sorted. Only n-1n- 1n~1
comparisons are needed.
2. Average Case: 0(n2)0(n*2)0(n2) - For a random array, the algorithm will perform.
about n24\frac{n*2}{4}4n2 comparisons and shifts.
3. Worst Case: 0(n2)0(n"2)0(n2) - When the array is sorted in reverse order, every
element has to be compared with all previous elements.
Space Complexity:
The space complexity is 0(1)0(1)0(1), as insertion sort is an in-place sorting
algorithm. It requires only a constant amount of extra memory space.
Code:
#include
// Function to implement insertion sort
void insertionSort(int arr[], int n) {
inti key, j;
for (i= 1; < ny i++) {
key = aril;
// Shift elements of arr{0..i-1] that are greater than key to one position ahead
while (j >= 0 && arr] > key) {
arrlj #11 = arti);
arti +11 key,
© seamed nth oxen scree // Function to print the array
void printArray(int arr[], int n) {
for (int i = 0;i
// Function to swap two elements
void swap(int *a, int *b) {
int temp = *a;
*a=*b;
*b= temp;
}
// Partition function to place the pivot element at the correct position
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choosing the last element as the pivot
inti=(low- 1); // Index of smaller element
© sean for (int j = low; j <= high - 1; j++) {
// \f current element is smaller than or equal to pivot
if (arrli] <= pivot) {
itt;
swap(8arr(i], &arr{j});
}
swap(&arr[i + 1], &arr[high]);
return (i+ 1);
}
// Quick Sort function
void quickSort(int arrf], int low, int high) {
if (low < high) {
// piis the partitioning index, arr[pi] is now at the right place
int pi = partition(arr, low, high);
// Recursively sort elements before and after partition
quickSort(arr, low, pi- 1);
quickSort(arr, pi + 1, high);
}
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", ari);
© seamed nth oxen scree printf("\n");
}
// Main function
int main {
int arrl] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr{0]);
printf(‘Original array: ");
printArray(arr, n);
quickSort(arr, 0, n- 1);
printf(‘Sorted array: ");
printArray(arr, n);
return 0;
Output:
© seamed nth oxen scree Se
=
«<1
Conse steerer
Complexity Analysis with Different Inputs
Best Case (Random or WellDistributed Elements): When the pivot divides the array into two
equal halves repeatedly.
© Time Complexity: O(nlog n)0(n \log n)O(nlogn)
Example: [3, 8, 2, 5, 1,7, 6,4]
‘Average Case (Random Array): For a random array, Quick Sort generally performs
O(nlog _n)O(n \log n)O(nlogn) on average
© Seamed wih ox scree Example: [10, 80, 30, 90, 40, 50, 70]
Worst Case (Sorted Array or Reversely Sorted Array): If the array is already sorted and the
pivot is the largest or smallest element each time
0 Time Complexity: 0(n2)0(n*2)0(n2)
o Example: [1, 2, 3, 4,5, 6, 7, 8]
5.implement to merge sort and analyze the algorithim with different
inputs.
1. Aim:
The aim of Merge Sort is to sort an array or list by dividing it into halves, sorting each half,
and then merging the sorted halves. This divide-and-conquer approach is effective because
it minimizes comparisons and makes the algorithm stable, ensuring that elements with
equal keys appear in the same order as in the input.
2. Algorithm:
Merge Sort recursively divides an array into two halves until each subarray contains only one
element (which is inherently sorted). It then merges these sorted subarrays to produce a
single sorted array.
3. Time Complexity:
Best Case: O(nlog _n)O(n \log n)O(nlogn)
Average Case: O(nlog_n)O(n \log n)O(nlogn)
Worst Case: O(nlog n)O(n \log n)O(nlogn)
Merge Sort consistently achieves O(nlog__n)O(n \log n)O(nlogn) because it always divides
the array in half and then merges, regardless of the initial ordering of elements.
4. Space Complexity:
Space Complexity: 0(n)O(n)O(n)
Merge Sort requires additional space for merging, as temporary arrays are used to hold the
divided arrays before merging. This makes the space complexity O(n)O(n)O(n), where nnn is
the number of elements in the array.
Code:
#include
// Function to merge two halves into a sorted array
void merge(int arr[], int left, int mid, int right) {
© sean int nt = mid- left +1;
int n2 = right - mid;
int Lint], R[n2];
for (int i= 0;i <1; i++)
Lfi] = arrlleft + i];
for (int j = 0; j
void bubbleSort(int arr{], int n) {
inti, j, temp;
int swapped;
for (i= 0;i arrfj + 1) {
// Swap arrli] and arrlj+1]
temp = arr[j];
arf] = arr{j + 1];
arr{j + 1] = temp;
swapped = 1;
}
// If no elements were swapped, break early
if (swapped == 0) break;
}
void printArray(int arr(), int n) {
for (inti = 0;i Onin
Eee ae
cme
Ce traeae
Pere)
ee
11 12 22 25 34 64 90
ome eee
code Analysis with Different Inputs:
Input 1: Random Order
Array: (64, 34, 25, 12, 22, 11, 90}
cn
// Funetion to perform selection sort
void selectionSort(int arrf], int n) {
inti, j, minldx, temp;
// Move the boundary of the unsorted subarray
for (i= O;i
#include
// Define the structure for a binary tree node
struct Node {
int data;
struct Node* left;
struct Node* right;
© same i
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof{(struct Node));
newNode-data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// Function for In-Order Traversal (Left, Root, Right)
void inOrderTraversal(struct Node* root) {
if (Foot = NULL) {
inOrderTraversal(root-left);
printf("%d ", root >data);
inOrderTraversal(root->right);
}
// Function for Pre-Order Traversal (Root, Left, Right)
void preOrderTraversal(struct Node* root) {
if (root != NULL) {
printf(‘%d ", root->data);
preOrderTraversal(root>left);
preOrderTraversal(root right);
OF Seamed with OFEW Sanne // Function for Post-Order Traversal (Left, Right, Root)
void postOrderTraversal(struct Node* root) {
if (root = NULL) {
postOrderTraversal(root>left);
postOrderTraversal(root->right);
printf("%d ", root >data);
}
// Function to insert a node in the binary tree
struct Node* insert(struct Node* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root-left = insert(root-left, data);
yelse{
root->right = insert(root->right, data);
}
return root;
}
// Function to search for a node in the binary tree
struct Node* search(struct Node* root, int key) {
if (root == NULL || root->data == key)
OF Seamed with OFEW Sanne return root;
if (key < root->data)
return search(root->left, key);
return search(root->right, key);
}
// Main function to test the binary tree operations
int main {
struct Node* root = NULL
// Inserting nodes into the binary tree
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
// Print in-order traversal of the binary tree
printf("In-Order Traversal: ");
inOrderTraversal(root);
printf("\n");
// Print pre-order traversal of the binary tree
printf('Pre-Order Traversal: ");
preOrderTraversal(root);
printf("\n");
© seamed nth oxen scree // Print post-order traversal of the binary tree
printf('Post-Order Traversal: ");
postOrderTraversal(root);
printf("\n");
1/ Search for a node in the tree
int key = 40;
struct Node* result = search(root, key);
if (result != NULL) {
printf(’Node with value %d found.\n', key);
yelse{
printf(’Node with value %d not found.\n’, key);
}
return 0;
}
Output:
© scomed win nen Sane =
a | a)
Eee EE
ee ee ee)
ea ee ee ee
Seer ete Ce
9.implement the binary search tree.
Aim
The aim of implementing a Binary Search Tree (BST) is to create an ordered data structure
that allows efficient searching, insertion, and deletion of nodes. In a BST, for any given node,
all the nodes in its left subtree have smaller values, and all the nodes in its right subtree have
larger values.
© Seamed wih ox scree Algorithm
Insertion:
If the tree is empty, create the root node.
© If the tree is not empty, compare the value to be inserted with the
current node.
+ Ifthe value is smaller than the current node, move to the left
child.{f the value is larger than the current node, move to the
right child.
© Repeat the process until the correct position is found (null).
Searching
Compare the value to be searched with the current node.If the value is
smaller than the current node, move to the left child,
© Ifthe value is larger than the current node, move .|f the value matches
the current node, return the node.
2.Deletion
Find the node to delete_If the node has no children, simply remove it.
If the node has one child, replace the node with its child.
If the node has two children, find the in-order successor (smallest node in the
right subtree).replace the node to be deleted with the in-order successor, and delete the in-
order successor.
Time Complexity
Best Case: O(log n), when the tree is balanced.
‘Average Case: O(log n), when the tree is relatively balanced,
Worst Case: O(n), when the tree is skewed (i.¢., degenerate into a linked list).
Space Complexity
O(n): Space complexity for storing nodes in the tree, where n is the number of nodes in the
tree, The space complexity for recursive calls (due to function calls in the case of insertion,
deletion, and search) is O(h), where h is the height of the tree,
© same Code:
#include
#include
// Structure for a node in the binary search tree
struct Node {
int data;
struct Node* left;
struct Node* right;
‘
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloo(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Funetion to insert a node into the BST
struct Node* insert(struct Node* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insert(root->left, data);
yelse{
© seamed nth oxen scree root->right = insert(root>right, data);
}
return root;
,
// Function to search for a value in the BST
struct Node* search(struct Node* root, int key) {
if (roo
NULL || root >data == key) {
return root;
}
if (key < root >data) {
return search(root-left, key);
}
return search(root->right, key);
}
// Function to find the minimum value node in the BST
struct Node* findMin(struct Node* root) {
while (root>left != NULL) {
root = rootleft;
}
return root;
}
// Function to delete a node from the BST
struct Node* deleteNode(struct Node* root, int key) {
if (root == NULL) {
return root;
OF Seamed with OFEW Sanne }
if (key < root >data) {
root left = deleteNode(root-eft, key);
} else if (key > root>data) {
root->right = deleteNode(root->right, key);
}else{
// Node with one or no child
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct Node* temp = root left;
free(root);
return temp;
}
// Node with two children: Get the inorder successor (smallest in the right
subtree)
struct Node* temp = findMin(root->right);
// Copy the inorder successor's content to this node
root->data = temp->date;
// Delete the inorder successor
rootright = deleteNode(rootright, temp->data);
}
return root;
© seamed nth oxen scree // Function to perform inorder traversal of the tree
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d *, root >data);
inorder(root->right);
}
// Main function
int main() {
‘struct Node* root = NULL;
// Inserting nodes into the BST
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
printf(‘Inorder traversal of the BST: ");
inorder(root);
printf(\n");
1/ Searching for a value
struct Node* searchResult = search(root, 40);
© seamed nth oxen scree if (searchResult != NULL) {
printf(‘Found node with value %éd\n", searchResult->data);
yelse{
printf(’Node with value 40 not found\n");
}
// Deleting a node
root = deleteNode(root, 20);
printf(‘Inorder traversal after deletion of 20:");
inorder(root);
printf(\n");
return 0;
}
Output
OF Seamed with OFEW Sanne > Onin
ere en eer
ae comon
a] ry]
ee eo RI)
re ere eee)
eee ose ee
10.Implement Matrix Chain Multiplication (MCM) using Dynamic
Programming
Aim:
The aim of the Matrix Chain Multiplication problem is to find the most efficient way
to multiply a given sequence of matrices. The goal is to determine the
parenthesization of matrix products that minimizes the number of scalar
multiplications,
© seamed nth oxen scree Algorithm:
Define the problem: Given a sequence of matrices A1, A2, A3, ..., An, where the
dimensions of matrix Ai are p(i-1) x pi, we want to find the optimal way to multiply the
matrices such that the number of scalar multiplications is minimized.
Define subproblem: Let mil be the minimum number of scalar multiplication needed to
compute the product of matrices Ai* Ai#1 *... *Aj
Recursive Relation: For each pair of matrices Ai and Aj, we will compute the minimum cost
by trying every possible place k to split the product into two subproblems:
mililf}=min {mli]k}+mfk+1][]}+p(i~1)+p(k)+pG)}milli] = \min \{ mlillKl + mlk+1]f] + pC) * p(k)
* pi) \Jen[illi]=min{m[ilfk}+m{k+1]f]+p(i-1)*p(k)*p()}where i <= k
#include
1/ Matrix Ai has dimension pli-1] x pli]
WM for
© scan int MatrixChainOrder(int pl, int i, int j)
{
id
return 0;
intk,
int min = INT_MAX;
int count,
// Place parenthesis at different places
// between first and last matrix,
// recursively calculate count of multiplications
// for each parenthesis placement
// and return the minimum count
for (k= isk
include
int les(char *X, char *Y) {
int m= strlen(X);
int n = strlen(Y);
int dplm + 1]ln + 1h
//\nitialize the DP table
for (int i = 0; i <= 1m; i++) {
for (int j = 0; j <= 1; j+4) {
if (== Ol ==0)
dplilli] = 0;
else if (x{i-1] == YU-1)
plil) = dpli- Mi - 1+ 15
else
pli] = (Ali - 1] > dL - 11) ? dpli- 1G: él - 11:
}
// Retum the length of LCS
return dplmlink
}
int maind {
char Xi] = "ABCDGI
char Yl] = “AEDFHR’;
printf('Length of LCS: %d\n’, les(X, Y));
return 0;
© seamed wth oFEn sioner Output
oe
pee
ema?
de Execution Successful
© seamed wth oFEn sioner 12.implement BFS for given graph G.
Aim:
To implement the BFS traversal algorithm for a given graph GGG using C programming
BFS Algorithm:
BFS is a graph traversal algorithm that explores the graph layer by layer. Starting from a
source node, it explores all its neighboring nodes, then moves on to the next layer of
neighbors. BFS is often implemented using a queue to track nodes to be explored.
Steps
1. Initialize: Start by marking the source node as visited and enqueue it.
2. Loop:
© Dequeue a node from the front of the queue.
‘© For each unvisited neighbor of this node:
+ Markit as visited
+ Enqueveit.
3. End: Continue until the queue is empty.
Time Complexity:
© O(V+E), where:
© WWis the number of vertices (nodes).
© EEE is the number of edges.
+ This complexity arises because each node is enqueued and dequeued once, and
each edge is processed once.
Space Complexity:
+ 0(V) for storing the visited nodes and queue.
Code: #include
include
#define MAX 100 // Define maximum number of vertices
// Queue structure
© same struct Queue {
int items[MAX];
int front;
int rear,
k
typedef struct Queue Queue;
1/ Function to create a queue
Queue* createQueue() {
Queue* q = (Queue*)malloc(sizeof(Queue));
qofront =-1;
q>rear =
return q;
11 Check if the queue is empty
int isEmpty(Queue* q) {
return q->rear
}
// Enqueue function
void enqueue(Queue* g, int value) {
MAX-1)
printf("\nqueue is ful
if (q>rear
else{
if (q>front
q>front
q>reart;
qpitems|q->rear] = value;
}
// Dequeue function
int dequeue(Queue* q) {
OF Seamed with OFEW Sanne int item;
if (isEmpty(q)) {
printf("Queue is empty’
item
Felse{
item = q->itemsiq-front);
fronts;
if (q>front > q->rear) {
qefront = q>rear = -1;
}
return item;
y
// Graph structure
struct Graph {
int numVertices;
int adjMatrix;
int* visited;
k
// Function to create a graph
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof (struct Graph));
graph->numVertices = vertices;
graph->adjMatrix = (int**)malloc(vertices * sizeof(int*));
graph->visited = (int*)malloc(vertices * sizeof{int));
for (int i = 0; i< vertices; i++) {
graph->adjMatrix(i] = (int*)malloc(vertices * sizeof(int));
graph->visited[i] = 0;
for (int
graph->adiMatrixll = 0;
|< vertices; j++)
© seamed wth oFEn sioner return graph;
// Function to add an edge to the graph
void addEdge(struct Graph* graph, int sro, int dest) {
graph->adjMatrix{srel{dest]
graph->adjMatrix[dest][src] = 1; // For undirected graph
}
1 BFS algorithm
void bfs(struct Graph* graph, int startVertex) {
Queue* q = createQueue();
graph->visited[startVertex)
enqueue(q, startVertex);
while (lisEmpty(q)) {
int currentVertex = dequeue(q);
printf ("Visited %d\n", currentVertex);
// Traverse the adjacency matrix of currentVertex
for (int i = 0; < graph->numVertices; i++) {
if (graph->adjMatrix{currentVertex][i] == 1 88 !graph->visited{i) {
greph-visited{] = 1;
enqueue(q, i);
int mainO {
int vertices = 6;
struct Graph* graph = createGraph(vertices);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
© seamed wth oFEn sioner addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 2, 4):
addEdge(graph, 3, 5);
printf(’BFS starting from vertex 0:\n");
bfs(graph, 0);
return 0;
}
Output:
xP om
See
Cee eae
est
heer
eter
Visited 3
eee)
eee)
Cote scat
# < (by
© seamed nth oxen scree 13.implement DFS for a given graph G.
Depth-First Search (DFS) Algorithm for Graphs:
DFS (Depth First Search) is an algorithm for traversing or searching tree or graph data
structures. Starting at the root node (or some arbitrary node in the case of a graph), DFS
explores as far as possible along each branch before backtracking.
Aim:
‘The aim of DFS is to traverse all the nodes of a graph by exploring as deep as possible
before backtracking, making it useful for tasks like pathfinding, topological sorting, and
detecting cycles in directed graphs.
DFS Algorithm:
1. Start at the root node or any arbitrary node.
2. Mark the current node as visited.
3. Recursively visit all adjacent unvisited nodes.
4
Backtrack to the previous node when no unvisited adjacent nodes remain.
Time Complexity:
+ Time Complexity: O(V+E)O(V + E)O(V+E)
© Wis the number of vertices.
© EEE is the number of edges.
© Each vertex and edge is visited once in the worst case.
Space Complexity:
+ Space Complexity: 0(V)O(V)O(V)
© Due to the space required for the recursion stack in the case of recursive DFS
(or the explicit stack in an iterative version)
Code:
#include
#include
#define MAX 100 // Maximum number of vertices
© sean // Define a structure for the adjacency list node
struct Node {
int vertex;
struct Node* next;
k
1/ Define a structure for the adjacency list
struct Graph {
int numVertices;
struct Node** adjLists;
int* visited;
k
// Function to create a node
struct Node* createNode(int vertex) {
struct Node* newNode = malloc(sizeof(struct Node));
newNode->vertex = vert
newNode->next = NULL;
return newNode;
}
// Function to create a graph
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct Node*));
graph->visited = malloc(vertices * sizeof(int));
for (int i = 0; < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited{i)
}
return graph;
© seamed nth oxen scree 1/ Function to add an edge to the graph
void addedge(struct Graph* graph, int sro, int dest) {
1/ Add edge from src to dest
struct Node* newNode = createNode(dest);
newNode-next = graph->adjLists[src];
graph->adjLists|src] = newNode;
// Add edge from dest to src for undirected graph
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
y
1 DFS algorithm
void DFS(struct Graph* graph, int vertex) {
struct Node* adjList = graph->adjLists|vertex];
struct Node* temp = adjList;
graph->visited{vertexl
printf(‘Visited %d\n’, vertex);
while (temp != NULL) {
int connectedVertex = temp->vertex;
if (graph->visited[connectedVertex] == 0) {
DFS(graph, connectedVertex);
}
temp = temp->next;
}
int main( {
struct Graph* graph = createGraph(4);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
© seamed nth oxen scree addEdge(graph, 2, 3);
printf('Depth First Search starting from vertex 0:\n");
DFS(graph, 0);
return 0;
}
Output:
P Onin x
Caper ee ces
eco ee
et
ery
Visited
een]
© seamed wth oFEn sioner
You might also like
- Design and Analysis of Algorithms - 23CSH-282No ratings yetDesign and Analysis of Algorithms - 23CSH-28272 pages
- Thanks To: Prof. Shafi Goldwasser Prof. Erik DemaineNo ratings yetThanks To: Prof. Shafi Goldwasser Prof. Erik Demaine53 pages
- Btech Degree Examination, May2014 Cs010 601 Design and Analysis of Algorithms Answer Key Part-A 1No ratings yetBtech Degree Examination, May2014 Cs010 601 Design and Analysis of Algorithms Answer Key Part-A 114 pages
- Unit-1 DAA Notes - Daa Unit 1 Note Unit-1 DAA Notes - Daa Unit 1 NoteNo ratings yetUnit-1 DAA Notes - Daa Unit 1 Note Unit-1 DAA Notes - Daa Unit 1 Note26 pages
- CMP3501 Analysis of Algorithms: Lecture Notes 5 - Divide and Conquer AlgorithmsNo ratings yetCMP3501 Analysis of Algorithms: Lecture Notes 5 - Divide and Conquer Algorithms38 pages
- Design and Analysis of Algorithm: Unit 1No ratings yetDesign and Analysis of Algorithm: Unit 180 pages
- Algorithm Analysis & Asymptotic PerformanceNo ratings yetAlgorithm Analysis & Asymptotic Performance99 pages
- Asymptotic Analysis (Big-O Notation) : Big O Notation Is Used in Computer Science To Describe The PerformanceNo ratings yetAsymptotic Analysis (Big-O Notation) : Big O Notation Is Used in Computer Science To Describe The Performance10 pages
- Analysis & Design of Algorithm (DCA7104)No ratings yetAnalysis & Design of Algorithm (DCA7104)13 pages
- COL 106: Data-Structures: Course Coordinator: Amit KumarNo ratings yetCOL 106: Data-Structures: Course Coordinator: Amit Kumar37 pages
