Complexity Analysis:

Complexity analysis in data structures refers to the process of

evaluating the performance of algorithms in terms of the resources
they consume (primarily time and space). It provides a way to
estimate how an algorithm will scale as the size of the input data
grows. This is essential for understanding the efficiency of
algorithms and selecting the most appropriate one for a given
problem.

Key Concepts in Complexity Analysis

1. Time Complexity
Time complexity measures the amount of time an algorithm
takes to complete as a function of the size of the input data
(n). It focuses on how the number of operations grows with
input size.

o Common notations:

O(1): Constant time, e.g., accessing an array element.

O(logn): Logarithmic time, e.g., binary search.

O(n): Linear time, e.g., traversing a list.

O(n2): Quadratic time, e.g., nested loops for matrix

multiplication.

2. Space Complexity
Space complexity measures the amount of memory an
algorithm for its complete execution, including the input
data,and call function.

o It is important when working with memory-constrained

systems or large datasets.

o Example: Recursive algorithms may use O(n)O(n)O(n)

 additional space for the call stack.

3. Best Case, Worst Case, and Average Case

o Best Case: Minimum time/space an algorithm can take

for a specific input.

o Worst Case: Maximum time/space an algorithm can

take for the most challenging input.

o Average Case: Expected time/space over all possible

inputs

Goals of Complexity Analysis

 To determine the scalability of an algorithm.
 To choose the most efficient data structure or algorithm for a
given problem.
 To predict an algorithm's performance under varying input
sizes.

Implementation of Stack using Array

#include <iostream>

using namespace std;

#define SIZE 5 // Maximum size of the stack

class Stack {

public:

intarr[SIZE];

int top;

public:

Stack() : top(-1) {} // Declare Constructor initializes the stack as empty

 // Push operation

void push(int value) {

if (top == SIZE - 1)

cout<< "Stack is Full"<<endl;

else

arr[++top] = value;

cout<< value << " pushed onto stack"<<endl;

// Pop operation

void pop() {

if (top == -1)

cout<< "Stack is empty"<<endl;

else

cout<<arr[top--] << " popped from stack"<<endl;

// Peek operation

int peek()

if (top == -1)

cout<< "Stack is empty"<<endl;

return -1;

else

{
returnarr[top];

// Check if stack is empty

boolisEmpty() {

return top == -1;

};

int main() {

Stack s;

s.push(10);

s.push(20);

s.push(30);

s.push(40);

s.push(50);

s.push(60); //this item will not added

cout<< "Top element is: " <<s.peek() <<endl;

s.pop();

s.pop();

s.pop();

s.pop();

return 0;

Example 2:

#include <iostream>

using namespace std;

/* The Stack class */

class Stack
{

public:

int object; // The data element

int current; // Index of the array

int size; // max size of the array

int A[10]; // Array of 10 elements

//constructor

Stack()

size = 10;

current = -1;

// The pop function

int pop()

return A[current--];

// The push function

void push(int x)

{A[++current] = x;

// The top function

int top()

return A[current];

// Will return true when stack is empty

intisEmpty()

{return ( current == -1 );

// Will return true when stack is full

intisFull()

return ( current == size-1);

}
};

// The main method

int main()

Stack s; // creating a stack object

// pushing the 10 elements to the stack

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

if(!s.isFull()) // checking stack is full or not

s.push(i); // push the element at the top

else

cout<<"\n Stack is full, can't insert new element";

// pop the elements at the stack

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

if(!s.isEmpty()) // checking stack is empty or not

cout<< "\n The popped element = " <<s.pop();

else

cout<<"\n Stack is empty, can't pop";

Implementation of Stack using Linked List

#include <iostream>
using namespace std;

// Node structure for linked list

class Node {
public:
int data; // Data stored in the node
Node* next; // Pointer to the next node

Node(int value) : data(value), next(nullptr) {} // Constructor to initialize node

};

// Stack class using linked list

class Stack {
public:
Node* top; // Pointer to the top of the stack

public:
// Constructor initializes the stack as empty
Stack() : top(nullptr) {}

// Push operation
void push(int value) {
Node* newNode = new Node(value); // Create a new node
newNode->next = top; // Link the new node to the current top
top = newNode; // Update top to the new node
cout<< value << " pushed onto stack" <<endl;
}

// Pop operation
void pop() {
{
Node* temp = top; // Store the top node
top = top->next; // Update top to the next node
cout<< temp->data << " popped from stack" <<endl;
delete temp; // Free memory of the popped node
}
}

// Peek operation
int peek() {
{
return top->data; // Return the data of the top node
}
 }

// Check if stack is empty

boolisEmpty() {
return top == nullptr; // Stack is empty if top is null
}
};

int main() {
Stack s;

s.push(10);
s.push(20);
s.push(30);
s.push(40);
s.push(50);
s.push(60); // This item will still be added (no size limit in linked list)
cout<< "Top element is: " <<s.peek() <<endl;

s.pop();
s.pop();
s.pop();
s.pop();

return 0;
}

Implementation of Queue using Array

#include <iostream>

using namespace std;

#define SIZE 5 // Maximum size of the queue

class Queue {

public:

intarr[SIZE]; // Array to store queue elements

int front; // Index of the front element

int rear; // Index of the rear element

int count; // Number of elements in the queue

public:

//create constructor

Queue() : front(0), rear(-1), count(0) {}

// Enqueue operation

voidenqueue(int value)

if (count == SIZE)

cout<< "Queue is Full"<<endl;

else

rear = rear + 1 ; // one item increment

arr[rear] = value;

count++;

cout<< value << " Insert into the queue."<<endl;

// Dequeue operation

voiddequeue() {

if (count == 0)

cout<< "Queue is Empty"<<endl;

else

{
cout<<arr[front] << " dequeued(Droped) from the queue"<<endl;

front = front + 1 ;

count--;

// Peek operation

int peek() {

if (count == 0)

cout<< "Queue is empty\n";

return -1;

} else

returnarr[front];

// Check if the queue is empty

boolisEmpty() {

return count == 0;

// Check if the queue is full

boolisFull() {

return count == SIZE;

};

int main() {

Queue q;

q.enqueue(10);

q.enqueue(20);

q.enqueue(30);

q.enqueue(40);
q.enqueue(50);

cout<< "Front element is: " <<q.peek() << "\n";

q.dequeue();

q.dequeue();

q.dequeue();

q.dequeue();

q.dequeue();

q.peek();

return 0;

Queue Implementation using Linked List

#include <iostream>

using namespace std;

// Node structure

struct Node {

int data; // Data stored in the node

Node* next; // Pointer to the next node

};

// Queue class

class Queue {

public:

Node* front; // Pointer to the front of the queue

Node* rear; // Pointer to the rear of the queue

public:

// Constructor to initialize queue

Queue() : front(nullptr), rear(nullptr) {}

 // Enqueue operation

voidenqueue(int value) {

Node* newNode = new Node(); // Create a new node

newNode->data = value; // Assign value to the node

newNode->next = nullptr; // New node will point to nullptr

if (rear == nullptr) { // If the queue is empty

front = rear = newNode; // Both front and rear point to the new node

} else {

rear->next = newNode; // Link the new node to the current rear

rear = newNode; // Update the rear pointer

cout<< value << " inserted into the queue." <<endl;

// Dequeue operation

voiddequeue() {

if (isEmpty()) {

cout<< "Queue is Empty" <<endl;

} else {

Node* temp = front; // Temporarily store the front node

cout<< front->data << " dequeued from the queue." <<endl;

front = front->next; // Update front to the next node

if (front == nullptr) { // If the queue becomes empty

rear = nullptr; // Rear should also be null

delete temp; // Free memory of the dequeued node

// Peek operation

int peek() {

if (isEmpty()) {

cout<< "Queue is empty" <<endl;

return -1;
 }

return front->data; // Return the data at the front

// Check if the queue is empty

boolisEmpty() {

return front == nullptr; // Queue is empty if front is null

};

int main() {

Queue q;

q.enqueue(10);

q.enqueue(20);

q.enqueue(30);

q.enqueue(40);

q.enqueue(50);

cout<< "Front element is: " <<q.peek() << "\n";

q.dequeue();

q.dequeue();

q.dequeue();

q.dequeue();

q.dequeue();

q.peek(); // Try to peek an empty queue

return 0;

Divide and Conquer Algorithm

The Divide and Conquer algorithm is a problem-solving technique that involves
breaking a problem into smaller subproblems, solving them independently, and then
combining their solutions to get the final result. It follows three main steps:
Steps of Divide and Conquer:
 1. Divide:
 Break down the original problem into smaller subproblems.
 Each subproblem should represent a part of the overall problem.
 The goal is to divide the problem until no further division is possible.
2. Conquer:
 Solve each of the smaller subproblems individually.
 If a subproblem is small enough (often referred to as the “base case”), we
solve it directly without further recursion.
 The goal is to find solutions for these subproblems independently.
3. Merge:
 Combine the sub-problems to get the final solution of the whole problem.
 Once the smaller subproblems are solved, we recursively combine their
solutions to get the solution of larger problem.
 The goal is to formulate a solution for the original problem by merging the
results from the subproblems.

Sorting Algorithm
A sorting algorithm is a method or procedure used to arrange the elements of a list (or array) in a
particular order—typically ascending or descending. Sorting is a fundamental task in computer science
and is used in many applications such as searching, data processing, and optimization.
Below is a detailed list of popular sorting algorithms, organized by their approach, along with their main
characteristics, time and space complexities, and typical use cases.
Types of Sorting Algorithms in Data Structure
These are the main types of sorting in data structures:
1. Comparison-based:
(Selection sort, Insertion sort, Merge sort, Quick sort, Bubble sort, Heap sort, shell sort, radix, bucket
sort)

Selection Sort:
Selection Sort –
1. find the smallest element
2. put it in the first position
3. find the next smallest element
4. put it in the second position …
− And so on, until you get to the end of the list
This technique is so simple that you might have found it yourself already. You search the whole array and
find the smallest number. The smallest number is put on the first position of the array while the previous
element in this position is moved somewhere else. Find the second smallest number and then put that
number in the second position in the array, again the previous number in that position is shifted
somewhere else. We keep on performing this activity again and again and eventually we get the array
sorted. This technique is called selection sort because we select elements for their sorted positions.
Let’s understand this algorithm by considering an example with the help of
figures. Consider an array that has four numbers i.e. 19, 5, 7 and 12 respect
Now we want to sort this array in ascending order. To sort the array, selecti
algorithm will be applied on it.
We find that 5 is the smallest number and bring it to the first position i.e. in
Later, number 19 is put at the position that was occupied by number 5.
Thus, in a sense, we swap these numbers. Now 5, the smallest number in th
has come at its final position i.e. index 0
Now we look at the remaining elements 19, 7, 12 and find the smallest num
among them. Here 7 is the smallest so we change its position with 19 to br
at its position. Thus 5 and 7 have come at their final positions. Now there a
elements are left behind i.e. 12 and 19. We search the smallest among thes
find that 12 is the smallest. So, we swap it with 19 to bring it at index 2 i.e.
final position. Now there is last element remaining and obviously it is at its
position as there is no element to compare with it. The array is now in the s
form with ascending numbers.
Insertion Sort
 Start by considering the first two elements of the array data. If found out of order, swap them
Consider the third element;
 Insert it into the proper position among the first three elements.
  Consider the fourth element; insert it into the proper position among the first four elements.
Let’s understand this algorithm by considering an example with the help of
figures. The array consists of the elements 19, 12, 5 and 7. We take the firs
numbers i.e. 19 and 12. As we see 12 is less than 19, so we swap their pos
Thus 12 comes at index 0 and 19 goes to index 1. Now we pick the third nu
i.e. 5. We have to find the position of this number by comparing it with the t
already sorted numbers. These numbers are 12 and 19. We see that 5 is sm
these two. So, it should come before these two numbers. Thus, the proper
of 5
is index 0. To insert it at index 0, we shift the numbers 12 and 19 before ins
5 at index 0. Thus 5 has come at its position. Now we pick the number 7 an
its position between 5 and 12. To insert 7 after 5 and before 12, we have to
the numbers 12 and 19 to the right. After this shifting, we put number 7 at i
position. Now the whole array has been sorted so the process stops here.

Bubble Sort
The third sorting algorithm is bubble sort. The basic idea of this algorithm is that we bring the smaller
elements upward in the array step by step and as a result, the larger elements go downward. If we think
about array as a vertical one, we do bubble sort. The smaller elements come upward and the larger
elements go downward in the array. Thus, it seems a bubbling phenomenon. Due to this bubbling nature,
this is called the bubble sort. Thus, the basic idea is that the lighter bubbles (smaller numbers) rise to the
top. This is for the sorting in ascending order. We can do this in the reverse order for the descending
order.
The steps in the bubble sort can be described as below
 Exchange neighboring items until the largest item reaches the end of the array
 Repeat the above step for the rest of the array
In this sort algorithm, we do pair-wise
swapping. We will take first the elements
and swap the smaller with the larger num
Then we do the swap between the next p
repeating this process, the larger number
will be going to the end of the array and
smaller elements come to the start of the
array.First of all, we compare the first pa
i.e. 19 and 5. As 5 is less than 19, we swa
theseelements. Now 5 is at its place and
take the next pair. This pair is 19, 12 and
not 12, 7. In this pair 12 is less than 19,
we swap 12 and 19. After this, the next p
is 19, 7. Here 7 is less than 19 so we swa
it. Now 7 is at its place as compared to 1
but it is not at its final position.

The element19 is at its final position. Now we repeat the pair wise swapping on the array from
index 0 to 2 as the value at index 3 is at its position. So we compare 5 and 12. As 5 is less than 12 so it
is at its place (that is before 12) and we need not to swap them. Now we take the next pair that is 12
and 7. In this pair, 7 is less than 12 so we swap these elements. Now 7 is at its position with respect to
the pair 12 and 7. Thus we have sorted the array up to index 2 as 12 is now at its final position. The
element 19 is already at its final position. Note that here in the bubble sort, we are not using additional
storage (array). Rather, we are replacing the elements in the same array. Thus, bubble sort is also an in-
place algorithm. Now as index 2 and 3 have their final values, we do the swap process up to the index 1.
Here, the first pair is 5 and 7 and, in this pair, we need no swapping as 5 is less than 7 and is at its
position (i.e. before 7). Thus 7 is also at its final position and the array is sorted.

Merge sort is a sorting algorithm that follows the divide-and-conquer approach. It works by recursively
dividing the input array into smaller subarrays and sorting those subarrays then merging them back
together to obtain the sorted array.
In simple terms, we can say that the process of merge sort is to divide the array into two halves, sort
each half, and then merge the sorted halves back together. This process is repeated until the entire
array is sorted.
Merge sort is a popular sorting algorithm known for its efficiency and stability. It follows the divide-and-
conquer approach to sort a given array of elements.
Here’s a step-by-step explanation of how merge sort works:
1. Divide: Divide the list or array recursively into two halves until it can no more be divided.
2. Conquer: Each subarray is sorted individually using the merge sort algorithm.
3. Merge: The sorted subarrays are merged back together in sorted order. The process
continues until all elements from both subarrays have been merged.

QuickSort
Quick sort is a sorting algorithm based on the Divide and Conquer that picks an element as a
pivot and partitions the given array around the picked pivot by placing the pivot in its correct
position in the sorted array.
Quick Sort works on the principle of divide and conquer, breaking down the problem into smaller
sub-problems.
There are mainly three steps in the algorithm:
1. Choose a Pivot: Select an element from the array as the pivot. The choice of pivot can
vary (e.g., first element, last element, random element, or median).
2. Partition the Array: Rearrange the array around the pivot. After partitioning, all elements
smaller than the pivot will be on its left, and all elements greater than the pivot will be on
its right. The pivot is then in its correct position, and we obtain the index of the pivot.
 3. Recursively Call: Recursively apply the same process to the two partitioned sub-arrays
(left and right of the pivot).
4. Base Case: The recursion stops when there is only one element left in the sub-array, as a
single element is already sorted.

Heap Sort
First convert the array into a max heap using heapify, Please note that this happens in-place.
The array elements are re-arranged to follow heap properties. Then one by one delete the root
node of the Max-heap and replace it with the last node and heapify. Repeat this process while
size of heap is greater than 1.
 Rearrange array elements so that they form a Max Heap.
 Repeat the following steps until the heap contains only one element:
o Swap the root element of the heap (which is the largest element in current heap)
with the last element of the heap.
o Remove the last element of the heap (which is now in the correct position). We
mainly reduce heap size and do not remove element from the actual array.
o Heapify the remaining elements of the heap.
 Finally we get sorted array.

1. This is not a Max 2. Swap 10 with 4 3. Swap 5 with 3

 Final Max Heap is Done
4. 10 swap with 9

Radix Sort
Radix Sort is a linear sorting algorithm that sorts elements by processing them digit by digit.It is an
efficient sorting algorithm for integers or strings with fixed-size keys. Rather than comparing elements
directly, Radix Sort distributes the elements into buckets based on each digit’s value. By repeatedly
sorting the elements by their significant digits, from the least significant to the most significant, Radix
Sort achieves the final sorted order

Sorting based on the unit place:

Sorting based on the tens place:

Sorting based on the hundreds place:

The array is now sorted in ascending order.The final sorted array using radix sort is [2, 24, 45, 66, 75, 90, 170,
802].

Bucket sort
Bucket sort is a sorting technique that involves dividing elements into various groups, or buckets. These
buckets are formed by uniformly distributing the elements. Once the elements are divided into buckets,
they can be sorted using any other sorting algorithm. Finally, the sorted elements are gathered together in
an ordered fashion.
Bucket sort, also known as bin sort, is a sorting algorithm that divides an array's elements into several
buckets. The buckets are then sorted one at a time, either using a different sorting algorithm or by
recursively applying the bucket sorting algorithm.
The bucket sort method is as follows:
 Create an array of "buckets" that are initially empty
 Scatter: Go through the original array, placing each object in its appropriate bucket
 Each non-empty bucket should be sorted
 Gather: Return all elements to the original array after visiting the buckets in order
For example, have the input array is:

Create Bucket for storing the sorting Element

Take each element from the input array. Multipl

the element by the size of the bucket array (10 i
this case). For example, for element 0.34, we ge
0.34 * 10 = 3.4. Then it is converted into an
integer. Finally,.34 is inserted into bucket 3.
Same procedure at 0.39 * 10= 3.9.
Converted it into integer, we got 3. So, we put th
items into 3rd index in array
Next Results: Items inserted like this

Now sorted result is here:

Hashing In Data Structure:

Hashing is a technique used in data structures that efficiently stores and retrieves data in a way that
allows for quick access.
 Hashing involves mapping data to a specific index in a hash table (an array of items)
using a hash function that enables fast retrieval of information based on its key.
 The great thing about hashing is, we can achieve all three operations (search, insert and
delete) in O(1) time on average.
 Hashing is mainly used to implement a set of distinct items and dictionaries (key value
pairs).

Components of Hashing
There are majorly three components of hashing:
1. Key: A Key can be anything string or integer which is fed as input in the hash function the
technique that determines an index or location for storage of an item in a data structure.
2. Hash Function: Receives the input key and returns the index of an element in an array
called a hash table. The index is known as hash index.(K Mod N (where N is No of Items)
or (K mod 10)
3. Hash Table: Hash table is typically an array of lists. It stores values corresponding to the
keys. Hash stores the data in an associative manner in an array where each data value
has its own unique index.
 We Follow (K Mod Table Size) or (K Mod N (N No of Items in Hashing table)
How does Hashing work?
Suppose we have a set of strings {“ab”, “cd”, “efg”} and we would like to store it in a table.
 Step 1: We know that hash functions (which are some mathematical formula) are used to
calculate the hash value which acts as the index of the data structure where the value will
be stored.
 Step 2: So, let’s assign
o “a” = 1,
o “b”=2, .. etc, to all alphabetical characters.
 Step 3: Therefore, the numerical value by summation of all characters of the string:
 “ab” = 1 + 2 = 3,
 “cd” = 3 + 4 = 7 ,
 “efg” = 5 + 6 + 7 = 18
 Step 4: Now, assume that we have a table of size 7 to store these strings. The hash
function that is used here is the sum of the characters in key mod Table size . We can
compute the location of the string in the array by taking the sum(string) mod 7 .
 Step 5: So we will then store
o “ab” in 3 mod 7 = 3,
o “cd” in 7 mod 7 = 0, and
o “efg” in 18 mod 7 = 4.

What is indexing?
Indexing improves database performance by minimizing the number of disc visits required to fulfill a query.
It is a data structure technique used to locate and quickly access data in databases. Several database
fields are used to generate indexes. The main key or candidate key of the table is duplicated in the first
column, which is the Search key. To speed up data retrieval, the values are also kept in sorted order. It
should be highlighted that sorting the data is not required. The second column is the Data Reference or
Pointer which contains a set of pointers holding the address of the disk block where that particular key
value can be found.

What is hashing with open addressing

It is the technique/ Type related to hashing (Collision in hashing technique)
Open Addressing is a method for handling collisions. In Open Addressing, all elements are stored in
the hash table itself. A collision occurs when two different inputs produce the same hash value (Index) in
a hash table. Techniques like chaining and open addressing help resolve this issue.Open addressing is a
technique used in hash tables to handle collisions by finding alternative positions for the collided key
within the table itself. Unlike chaining, which stores multiple keys in the same bucket, open addressing
keeps all entries in a single array.
How It Works:When a collision occurs (i.e., two keys map to the same index), open addressing searches
for the next available slot using a probing sequence.
Formula:1.If slot hash(k) % S is full, then we try (hash(k) + 1) % S,
2.If (hash(k) + 1) % S is also full, then we try (hash(k) + 2) % S
3.If (hash(k) + 2) % S is also full, then we try (hash(k) + 3) % S
Example: Let us consider a simple hash function as “key mod 5” and a sequence of keys that are to be
inserted are 50, 70, 76, 85, 93.

What is Hashing with Chaining in Data Structure?

In this section we will see what is the hashing with chaining. The Chaining is one collision resolution
technique. We cannot avoid collision, but we can try to reduce the collision, and try to store multiple
elements for same hash value.
This technique supposes our hash function h(x) ranging from 0 to 6. So for more than 7 elements, there
must be some elements that will be places inside the same room. For that we will create a list to store them
accordingly. In each time we will add at the beginning of the list to perform insertion in O(1) time
Let us see the following example to get better idea. If we have some elements like {15, 47, 23, 34, 85, 97, 65,
89, 70}. And our hash function is h(x) = x mod 7
 What is Graph?
A graph is a set of data items called Nodes, where nodes are connected to each other by the
help of edges called Graphs. A graph in data structures is a non-linear data structure that
consists of a set of nodes (or vertices) and a set of edges that connect these nodes. Graphs
are used to represent relationships between objects, such as social networks, road maps,
and network topologies.

A graph (G) can be represent on ordered pair (V, E) where V indicates the No of Vertices and
E indicates the No of Edges.
G= (V,E)
G= (6,6)
Components:
1. Vertices: The vertices are sometimes also referred to as nodes and the
2. Edges are lines or arcs that connect any two nodes in the graph.
“A collection of vertices and edges is called Graph”
Types of Graphs in Data Structure and Algorithms:
1. Null Graph: A graph is known as a null graph if there are no edges in the graph.
2. Trivial Graph: Graph having only a single vertex (Node), it is also the smallest graph
possible

3. Undirected Graph: A graph in which edges do not have any direction. That is the nodes are
unordered pairs in the definition of every edge.
4. Directed Graph: A graph in which edge has directions. That is the nodes are ordered
pairs in the definition of every edge.

5. Connected Graph: The graph in which from one node we can visit any other node in the
graph is known as a connected graph.
6. Disconnected Graph: The graph in which at least one node is not reachable from a node is
known as a disconnected graph

7. Complete Graph: The graph in which from each node there is an edge to each other node
8. Cycle Graph: The graph in which the graph is a cycle in itself, the minimum value of
degree of each vertex is 2.
9. Cyclic Graph: A graph containing at least one cycle is known as a Cyclic graph
10. Directed Acyclic Graph: A Directed Acyclic Graph, often abbreviated as DAG, is a
fundamental concept in graph theory. DAGs are used to show how things
are related or depend on each other in a clear and organized way.
“A Directed Acyclic Graph (DAG) is a directed graph that does not contain any cycles.”
Directed Acyclic Graph has two important features:
 Directed Edges: In Directed Acyclic Graph, each edge has a direction,
meaning it goes from one vertex (node) to another. This direction signifies
a one-way relationship or dependency between nodes.
 Acyclic: The term "acyclic" indicates that there are no cycles or closed loops
within the graph. In other words, you cannot traverse a sequence of directed
edges and return to the same node, following the edge directions. Formation
of cycles is prohibited in DAG. Hence this characteristic is essential.

Breadth-First Search (BFS)

Breadth-First Search (BFS) is a traversal algorithm used for searching tree or graph data
structures. It explores all the vertices at the present depth level before moving on to nodes at
the next depth level.
How BFS Works:
1. Start from a source node and mark it as visited.
2. Use a queue (FIFO - First In, First Out) to keep track of nodes to be explored.
3. Visit all adjacent (neighbor) nodes of the current node, mark them as visited,
 and enqueue them.
4. Repeat the process until all reachable nodes are visited.
Algorithm for BFS:
1. Initialize a queue and enqueue the starting node.
2. Mark the starting node as visited.
3. While the queue is not empty:
o Dequeue a node.
o Process the node.
o Enqueue all its unvisited neighbors and mark them as visited
A
/\
B C
/\ \
D E F
BFS Traversal (Starting from A)
Queue: A
1. Dequeue A → Visit A, Enqueue B, C → Queue: [B, C]
2. Dequeue B → Visit B, Enqueue D, E → Queue: [C, D, E]
3. Dequeue C → Visit C, Enqueue F → Queue: [D, E, F]
4. Dequeue D → Visit D → Queue: [E, F]
5. Dequeue E → Visit E → Queue: [F]
6. Dequeue F → Visit F → Queue: []
BFS Order: A → B → C → D → E → F

Depth First Search or DFS for a Graph

In Depth First Search (or DFS) for a graph, we traverse all adjacent vertices one by one. When
we traverse an adjacent vertex, we completely finish the traversal of all vertices reachable
through that adjacent vertex. This is similar to a tree, where we first completely traverse the
left subtree and then move to the right subtree. The key difference is that, unlike trees,
graphs may contain cycles (a node may be visited more than once). To avoid processing a
node multiple times, we use a Boolean visited array.
 Output: 1 0 2 3 4
Explanation: The source vertex s is 1.
We visit it first, then we visit an adjacent.
Start at 1: Mark as visited. Output: 1
Move to 0: Mark as visited.
Output: 0 (backtrack to 1)
Move to 2: Mark as visited.
Output: 2 (backtrack to 0)
Move to 3: Mark as visited.
Output: 3 (backtrack to 2)
Move to 4: Mark as visited.
Output: 4 (backtrack to 2)

Topological Order/Topological Sorting

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that
for every directed edge u-v, vertex u comes before v in the ordering.
Note: Topological Sorting for a graph is not possible if the graph is not a DAG.
Steps (to find the Topological Order):
1. Find the in degrees of each vertices in graph
2. Remove the vertices with edges of 0 in degree from graph
3. Repeat these steps till the end
Output: 5 4 2 3 1 0
Explanation: The first vertex in topological sorting is
always a vertex with an in-degree of 0 (a vertex with
no incoming edges). A topological sorting of the
following graph is “5 4 2 3 1 0”. There can be more
than one topological sorting for a graph. Another
topological sorting of the following graph is
“4 5 2 3 1 0”.

A→B→D Valid Topological Orders

A, E, B, C, D, F
| ↘


 A, B, E, C, D, F
↓ C (There can be multiple valid solutions.)
E→F
 Shortest Path
In graph theory, the shortest path problem is about finding the shortest possible
route between two nodes in a graph. The path length is usually measured by the
sum of edge weights (or the number of edges in an unweighted graph).
Common Shortest Path Algorithms
1. Dijkstra’s Algorithm (For graphs with non-negative weights)
Uses a priority queue to find the shortest path from a single
source to all nodes
2. Bellman-Ford Algorithm (For graphs with negative weights)

Finds the shortest path from a single source and can handle
graphs with negative weights

3. Floyd-Warshall Algorithm (For all-pairs shortest paths)

Uses dynamic programming to find shortest paths between all

pairs of nodes.

Dijkstra’s Algorithm

Dijkstra's algorithm is used to find the shortest path from a single

source node to all other nodes in a graph with non-negative weights.

Algorithm Steps:

1. Initialize:

 Set the distance of the source node to 0 and all other nodes
to infinity.
 Use a priority queue (min-heap) to always explore the node
with the shortest known distance.

2. Process Nodes:

 Extract the node with the smallest distance.

 Update distances of its neighbors if a shorter path is found.

3. Repeat Until All Nodes Are Processed:

 Continue until the priority queue is empty.

Example:

Input: src = 0, the graph is shown below.

 Explanation: Shortest Paths:
0 to 1 = 4.
0 to 2 = 12. 0->1->2
0 to 3 = 19. 0->1->2->3
0 to 4 = 21. 0->7->6->5->4
0 to 5 = 11. 0->7->6->5
0 to 6 = 9. 0->7->6
0 to 7 = 8. 0->7
0 to 8 = 14. 0->1->2->8

Output: 0 4 12 19 21 11 9 8 14

Floyd-Warshall Algorithm:
Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all
the pairs of vertices in a weighted graph. This algorithm works for both the
directed and undirected weighted graphs. unlike Dijkstra and Bellman-Ford which
are single source shortest path algorithms. This algorithm works for both
the directed and undirected weighted graphs.

Note: It does not work for the graphs with negative cycles (where the sum of the
edges in a cycle is negative).
Example:
Given Graph: Final Result:
 Representation of graph
The process of representing the graph with the help of vertices and edges is
called graph representation.
There are two types of technique to represent the graph
1. Adjacency Matrix
2. Adjacency List

Adjacency Matrix
An adjacency matrix is a two-dimensional array that stores the edges between
two vertices as boolean values. The rows and columns of the matrix represent
the vertices of the graph.

Explanation: At the top we have a graph with some vertices and edges. At the bottom we
have the adjacency matrix representation of the graph. The rows and columns represent the
vertices of the graph. If we look at the vertex with the value of 1, we can see that it has
edges to vertices 2 and 4. So we put a 1 in the first row for 2 and 4. This is an undirected
graph, so it goes the other way as well. So we can put a 1 in the 2 row and the 4 row for 1. If
this were a directed graph, we would only put a 1 in the 1 row for 2 and 4
Implementation of Adjacency Matrix:
#include <iostream>
using namespace std;

class Graph {
public:
int adjMatrix[10][10] ; // 10x10 adjacency matrix, initialized to 0
int numVertices = 4; // Fixed number of vertices (can be changed)
public:
// Constructor
Graph() {
// This constructor initializes all entries in the matrix to 0
for (int i = 0; i < numVertices; i++)
for (int j = 0; j < numVertices; j++)
adjMatrix[i][j] = 0;
}

// Function to add an edge between vertex i and vertex j (undirected)

void addEdge(int i, int j) {
adjMatrix[i][j] = 1; // Mark edge from i to j
adjMatrix[j][i] = 1; // Mark edge from j to i (because undirected)
}

// Function to print the adjacency matrix

void display() {
cout << "Adjacency Matrix:" << endl;
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
cout << adjMatrix[i][j] << " "; // Print each cell
}
cout << endl; // Newline after each row
}
}
};

int main() {
Graph g; // Create a Graph object
 // Add edges between the vertices
g.addEdge(0, 1); // Connect vertex 0 and 1
g.addEdge(0, 2); // Connect vertex 0 and 2
g.addEdge(1, 2); // Connect vertex 1 and 2
g.addEdge(2, 3); // Connect vertex 2 and 3

// Display the adjacency matrix

g.display();

return 0;
}

Adjacency List
An adjacency list is a collection of linked lists or arrays that lists all of the other vertices that
are connected. Let's look at an example that uses linked lists. Every vertex has a linked list
of all the vertices that it is connected to:

Adjacency List Implementation:

#include <iostream>
#include <vector>
using namespace std;
// Define a class to represent a Graph
class Graph {
public:
int numVertices = 4; // Fixed number of vertices
vector<int> adjList[10]; // Array of vectors to represent adjacency list

// Constructor (optional initialization if needed)

Graph() {
// No need to initialize anything, vector handles dynamic size
}

// Function to add an edge between vertex i and vertex j (undirected)

void addEdge(int i, int j) {
adjList[i].push_back(j); // Add j to i's list
adjList[j].push_back(i); // Add i to j's list (undirected)
}

// Function to print the adjacency list

void display() {
cout << "Adjacency List:" << endl;
for (int i = 0; i < numVertices; i++) {
cout << i << ": ";
for (int neighbor : adjList[i]) {
cout << neighbor << " ";
}
cout << endl;
}
}
};

int main() {
 Graph g; // Create a Graph object

// Add edges between the vertices

g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);

// Display the adjacency list

g.display();

return 0;
}
Which one is better?
The answer is: it depends. It depends on the type of graph and the type of operations you
want to perform on the graph. If you have a graph with a lot of edges, then the adjacency
matrix might be better. If you have a graph with a lot of vertices, then the adjacency list
might be better. If you want to be able to quickly tell if there is an edge between two vertices,
then the adjacency matrix might be better. If you want to be able to quickly iterate over all
the edges of a vertex, then the adjacency list might be better. I think overall, in my own
opinion, the adjacency list is easier and more commonly used. But it really depends on the
situation.

Memory Management and Garbage Collection

memory management and garbage collection are essential for efficient program
operation. Memory management is the process of allocating and deallocating memory
space during program execution, while garbage collection is a specific type of memory
management that automatically reclaims memory that is no longer reachable by the
program

Memory Management:
 Allocation:
When a program needs to store data, it allocates memory to hold that data, often from a
large pool of available memory known as the heap.
 Deallocation:
Once the program no longer needs the data, it should deallocate the memory, returning it to
the heap so it can be used by other parts of the program.
 Dynamic Allocation:
In languages like C++, memory allocation and deallocation are often handled manually by
the programmer using functions like malloc and free.
 Static Allocation:
Some data structures, like arrays declared with a fixed size, have their memory allocated at
compile time (static allocation)

Garbage Collection:
 Automatic Memory Reclamation:
Garbage collection is an automatic memory management technique that identifies and
reclaims memory that is no longer in use by the program, preventing memory leaks.
 Reachable vs. Unreachable:
The garbage collector determines which memory is reachable by the program (i.e., still
pointed to by variables or other objects) and which is not.
 Unreachable Memory as Garbage:
Memory that is no longer reachable is considered "garbage" and can be safely reclaimed by
the garbage collector.
 Languages with Garbage Collection:
Languages like Java and C# have built-in garbage collection, relieving programmers from
the burden of manual memory management.
 Benefits:
Garbage collection simplifies programming, reduces the risk of memory leaks, and improves
program reliability.
Garbage Collection in Data Structures:
 Linked Lists and Trees:
In linked lists and trees, each node is allocated memory dynamically. Garbage collection
ensures that memory occupied by nodes that are no longer part of the data structure is
reclaimed.
 Arrays:
Garbage collection can also play a role in managing memory for arrays, especially dynamic
arrays or those where the size can change during runtime.
 Efficiency:
Efficient garbage collection algorithms can minimize the overhead associated with
reclaiming memory, ensuring that program performance is not negatively impacted.