HPSC PGT COMPUTER

SCIENCE 2025

Types of Data Structures and Explanation:

1. Array:

o An array is a collection of elements, all of the same data type, stored in

contiguous memory locations. Each element can be accessed using an index or
subscript. Arrays are static data structures because their size is fixed at the time of
initialization.

o Applications: Storing data for quick lookup, implementing matrices, etc.

o Operations: Access, Update, Insert, and Delete (mainly from the ends or specific
indexes).

2. Stack:

o A stack is a linear data structure that follows the Last In First Out (LIFO) principle. It
has two main operations:

 Push: Adds an element to the top of the stack.

 Pop: Removes the top element from the stack.

o Applications: Function calls, undo mechanisms in applications, expression

evaluation, etc.

o Example: A stack of plates, where you can only take the top plate off.

3. Queue:

o A queue is a linear data structure that follows the First In First Out (FIFO) principle. It
has two main operations:

 Enqueue: Adds an element to the end of the queue.

 Dequeue: Removes an element from the front of the queue.

o Applications: Scheduling tasks, handling requests in a web server, etc.

o Example: A queue at a bus stop, where the first person to arrive is the first one to
board the bus.

4. Linked List:

o A linked list is a linear collection of nodes, where each node contains data and a
reference (link) to the next node in the sequence. Unlike arrays, linked lists do not
store elements in contiguous memory locations.

o Types:

 Singly Linked List: Each node points to the next node.

 Doubly Linked List: Each node points to both the next and the previous
nodes.
 HPSC PGT COMPUTER
SCIENCE 2025

 Circular Linked List: The last node points back to the first node.

o Applications: Dynamic memory allocation, implementation of stacks and queues,

etc.

o Operations: Insertion, Deletion, Traversing, and Searching.

5. Tree:

o A tree is a hierarchical data structure consisting of nodes connected by edges.

Each tree has a root node, and the nodes are organized into levels. Trees are
used to represent data with hierarchical relationships.

o Types:

 Binary Tree: Each node has at most two children (left and right).

 Binary Search Tree (BST): A binary tree with the property that the left
subtree of a node contains values less than the node’s value, and the
right subtree contains values greater than the node’s value.

o Applications: Representing hierarchical data (like file systems), searching, sorting,

etc.

Searching Algorithms:

1. Linear Search:

o Linear search is the simplest searching algorithm. It involves checking each

element in the array or list sequentially until the desired element is found or the list
ends.

o Time Complexity: O(n), where n is the number of elements in the list.

o Applications: Useful for small lists or unsorted data where other searching
algorithms cannot be applied.

2. Binary Search:

o Binary search is a more efficient search algorithm, but it only works on sorted
data. The array is repeatedly divided in half, and the search continues in the half
that could contain the target element.

o Steps:

 Start with the middle element of the sorted list.

 If the target element is equal to the middle element, return the index.

 If the target element is less than the middle element, repeat the search on
the left half.
 HPSC PGT COMPUTER
SCIENCE 2025

 If the target element is greater than the middle element, repeat the
search on the right half.

o Time Complexity: O(log n), where n is the number of elements.

o Applications: Used in searching operations in sorted arrays or lists, databases, etc.

Types of Data Structures (continued):

6. Heap:

o A Heap is a special tree-based data structure that satisfies the heap property.
There are two types of heaps:

 Max Heap: The value of the parent node is always greater than or equal
to the values of its children.

 Min Heap: The value of the parent node is always less than or equal to the
values of its children.

o Applications: Used in priority queues, heap sort, and for efficient implementation
of algorithms like Dijkstra's shortest path.

7. Trie (Prefix Tree):

o A Trie is a tree-like data structure used for storing strings, where nodes represent
characters. It is optimized for searching and retrieval, especially useful when
dealing with a large dictionary of strings.

o Applications: Word auto-completion, spell checkers, IP routing, and other

applications involving string searches.

8. Hash Table:

o A Hash Table stores key-value pairs. The key is hashed to find the corresponding
value. This allows for constant time complexity, O(1), for insertion, deletion, and
searching (on average).

o Applications: Database indexing, caches, associative arrays, and implementing

sets.

o Operations: Insertion, Deletion, Search.

9. Graph:

o A Graph is a non-linear data structure made up of vertices (nodes) and edges

(connections between nodes). A graph can be directed or undirected, and may
contain cycles or be acyclic.

o Applications: Social networks, web page linking, routing algorithms, network flow,
etc.

o Operations: Traversing (DFS, BFS), Finding the shortest path (Dijkstra, Floyd-
Warshall), Cycle detection, etc.
 HPSC PGT COMPUTER
SCIENCE 2025

Searching Algorithms (continued):

3. Interpolation Search:

o Interpolation Search is an improved version of Binary Search for uniformly

distributed data. Instead of dividing the search space in half, it estimates the
position of the target element using a formula that considers the value of the
element.

o Formula:

mid=low+(target−arr[low]arr[high]−arr[low])×(high−low)\text{mid} = \text{low} +
\left(\frac{\text{target} - \text{arr[low]}}{\text{arr[high]} - \text{arr[low]}}\right) \times
(\text{high} - \text{low})mid=low+(arr[high]−arr[low]target−arr[low])×(high−low)

o Time Complexity: O(log log n) in the best case, but O(n) in the worst case (if the
data is not uniformly distributed).

o Applications: Useful for searching in uniformly distributed data sets.

4. Exponential Search:

o Exponential Search works well with a sorted array, and is useful when the size of
the array is unknown. It first finds the range where the target element might be
located, and then performs binary search on that range.

o Steps:

 Start with the first element and repeatedly double the index until you find
a range where the element is within bounds.

 Perform a binary search in that range.

o Time Complexity: O(log n)

o Applications: Useful in situations where the size of the array is unknown and you
need to find an efficient search range.

5. Jump Search:

o Jump Search is an algorithm for sorted data. It works by jumping ahead by a

fixed number of steps (usually the square root of the array size), and performing a
linear search within the block where the target element is found.

o Steps:

 Jump in steps of √n from the beginning of the array until you find a block
where the target element might lie.

 Once the block is found, perform a linear search within that block.

o Time Complexity: O(√n)

 HPSC PGT COMPUTER
SCIENCE 2025

o Applications: Suitable for large arrays where Binary Search is not feasible.

In-Depth Explanation of Key Data Structures:

 Arrays: Arrays are simple and efficient for direct access using indexes, but they have a
fixed size. Inserting or deleting an element in the middle requires shifting elements, which
can be inefficient.

 Stacks: Stacks are extremely useful for problems like backtracking, parsing expressions,
and recursive algorithms. However, they are limited by their LIFO structure, which makes
accessing elements in the middle or at the bottom difficult.

 Queues: Like stacks, queues are useful for tasks like task scheduling and buffering. The
challenge with queues is that they are restricted by the FIFO order, which may not always
be desirable for every application.

 Linked Lists: Linked lists solve the problem of dynamic size allocation, but they incur the
cost of extra memory to store pointers and pointers need to be handled carefully to
avoid memory leaks.

 Trees: Trees, especially binary search trees (BST), offer efficient searching, insertion, and
deletion operations. However, in the worst case (when the tree is unbalanced), these
operations can degrade to O(n) time complexity.

Key Concepts to Remember:

 Time Complexity: Always consider the time complexity of an algorithm or data structure
when deciding which one to use. For example, arrays offer O(1) time complexity for
access, while linked lists have O(n) time complexity for access but O(1) for insertion and
deletion.

 Space Complexity: Understand the space requirements of each data structure. For
example, linked lists use more memory because of the pointers, while arrays are more
space-efficient, but have fixed size limitations.

 Efficiency in Real-World Applications: Consider practical trade-offs between the

simplicity and performance of data structures. For example, a hash table might be faster
for searching than a list, but requires more memory.

Sorting Algorithms and Their Explanations

1. Bubble Sort:

o Explanation: Bubble sort is a simple sorting algorithm that works by repeatedly

stepping through the list to be sorted. It compares each pair of adjacent items
and swaps them if they are in the wrong order. The pass through the list is
repeated until no swaps are needed, meaning the list is sorted.
 HPSC PGT COMPUTER
SCIENCE 2025

o Time Complexity:

 Worst-case: O(n2)O(n^2)O(n2)

 Best-case: O(n)O(n)O(n) (if the list is already sorted)

o Example:

 For the array [5, 1, 4, 2, 8], after the first pass, it becomes [1, 4, 2, 5, 8]. This
process continues until no more swaps are required.

2. Selection Sort:

o Explanation: In selection sort, the algorithm divides the list into two parts: the
sorted part and the unsorted part. It repeatedly selects the smallest (or largest,
depending on order) element from the unsorted part and swaps it with the
leftmost unsorted element.

o Time Complexity:

 Worst-case: O(n2)O(n^2)O(n2)

 Best-case: O(n2)O(n^2)O(n2)

o Example:

 For the array [64, 25, 12, 22, 11], after the first pass, it becomes [11, 25, 12,
22, 64].

3. Insertion Sort:

o Explanation: Insertion sort works by taking one element at a time and inserting it
into its correct position in the already sorted part of the array. It compares the
current element to the previous elements and shifts the elements as needed to
make space for the current element.

o Time Complexity:

 Worst-case: O(n2)O(n^2)O(n2)

 Best-case: O(n)O(n)O(n)

o Example:

 For the array [12, 11, 13, 5, 6], it starts with 12 and compares with 11,
shifting 12 and placing 11 at the first position.

4. Quick Sort:

o Explanation: Quick sort is a divide-and-conquer algorithm. It picks an element as

a pivot and partitions the array around the pivot, placing elements smaller than
the pivot to the left and elements greater than the pivot to the right. This process
is recursively applied to the subarrays formed by the partitioning.

o Time Complexity:
 HPSC PGT COMPUTER
SCIENCE 2025

 Worst-case: O(n2)O(n^2)O(n2)

 Best-case: O(nlog⁡n)O(n \log n)O(nlogn)

 Average-case: O(nlog⁡n)O(n \log n)O(nlogn)

o Example:

 For the array [10, 7, 8, 9, 1, 5], choosing 5 as a pivot, the array is partitioned
as [1, 5, 8, 9, 7, 10] and further recursively sorted.

5. Merge Sort:

o Explanation: Merge sort is another divide-and-conquer algorithm that divides the

array into two halves, recursively sorts each half, and then merges the two sorted
halves. The merge operation ensures that the two sorted subarrays are combined
in sorted order.

o Time Complexity:

 Worst-case: O(nlog⁡n)O(n \log n)O(nlogn)

 Best-case: O(nlog⁡n)O(n \log n)O(nlogn)

o Example:

 For the array [38, 27, 43, 3, 9, 82, 10], the array is split into subarrays,
recursively sorted, and then merged back together in sorted order.

6. Heap Sort:

o Explanation: Heap sort is based on a binary heap data structure. It first builds a
max heap (for ascending order), where the largest element is at the root. It then
repeatedly swaps the root with the last element and restores the heap property.

o Time Complexity:

 Worst-case: O(nlog⁡n)O(n \log n)O(nlogn)

 Best-case: O(nlog⁡n)O(n \log n)O(nlogn)

o Example:

 For the array [4, 10, 3, 5, 1], it is first transformed into a max heap and then
sorted by swapping the root with the last element and re-heapifying.

Analysis of Algorithms: Asymptotic Notation

Asymptotic notation is used to describe the behavior of algorithms as the input size grows. It
gives an approximation of the algorithm's efficiency, especially in the worst or best case.

1. Big-O Notation (O):

 HPSC PGT COMPUTER
SCIENCE 2025

o Definition: Big-O notation provides an upper bound on the time complexity of an

algorithm. It describes the worst-case scenario, indicating the maximum time an
algorithm will take.

o Example: An algorithm with a time complexity of O(n2)O(n^2)O(n2) will take at

most n2n^2n2 operations in the worst case.

2. Omega Notation (Ω):

o Definition: Omega notation provides a lower bound on the time complexity,

representing the best-case scenario. It indicates the minimum number of
operations an algorithm will take.

o Example: An algorithm with Ω(n)\Omega(n)Ω(n) time complexity will take at

least nnn operations, even in the best case.

3. Theta Notation (Θ):

o Definition: Theta notation provides both an upper and lower bound on the time
complexity. It is used when the algorithm's time complexity is bounded both
above and below by the same function.

o Example: An algorithm with Θ(nlog⁡n)\Theta(n \log n)Θ(nlogn) time complexity

will take between nlog⁡nn \log nnlogn and nlog⁡nn \log nnlogn operations in both
the best and worst cases.

Summary of Sorting Algorithms Complexity

Algorithm Best Case Worst Case Average Case

Bubble Sort O(n)O(n)O(n) O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2)

Selection
O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2)
Sort

Insertion Sort O(n)O(n)O(n) O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2)

O(nlog⁡n)O(n \log O(nlog⁡n)O(n \log

Quick Sort O(n2)O(n^2)O(n2)
n)O(nlogn) n)O(nlogn)

O(nlog⁡n)O(n \log O(nlog⁡n)O(n \log O(nlog⁡n)O(n \log

Merge Sort
n)O(nlogn) n)O(nlogn) n)O(nlogn)

O(nlog⁡n)O(n \log O(nlog⁡n)O(n \log O(nlog⁡n)O(n \log

Heap Sort
n)O(nlogn) n)O(nlogn) n)O(nlogn)

More Detailed Explanation of Sorting Algorithms

1. Bubble Sort:
 HPSC PGT COMPUTER
SCIENCE 2025

 Process:

o Bubble sort is a comparison-based sorting algorithm where the largest unsorted

element is "bubbled" to its correct position in each pass. The process continues
with each pass going one element less, as the list gets more sorted.

o The algorithm iterates over the entire list multiple times and compares adjacent
elements. If an element is greater than its next element, they are swapped.

 Best Case: O(n)O(n)O(n)

o If the array is already sorted, no swaps are needed, and a single pass is enough.

 Drawback: Although it's easy to understand and implement, it's inefficient for large
datasets because of its quadratic time complexity in the average and worst cases.

2. Selection Sort:

 Process:

o Selection sort works by dividing the array into two sections: a sorted part (starting
with the first element) and an unsorted part (the rest of the array). The algorithm
selects the smallest (or largest) element from the unsorted part and swaps it with
the first unsorted element. This process continues until all elements are sorted.

 Best and Worst Case: O(n2)O(n^2)O(n2)

o No matter the initial order of the array, selection sort always performs the same
number of comparisons, making it inefficient for larger arrays.

 Advantage: The main advantage of selection sort is its simplicity and the fact that it
makes at most n−1n-1n−1 swaps, which can be beneficial in certain situations where
swapping is expensive.

3. Insertion Sort:

 Process:

o Insertion sort builds the sorted array one item at a time. It takes an element from
the unsorted part and compares it with the elements in the sorted part, shifting
them if necessary to make room for the new element.

 Best Case: O(n)O(n)O(n)

o In the best case, when the array is already sorted, the algorithm performs a linear
pass, making only one comparison per element.

 Worst Case: O(n2)O(n^2)O(n2)

o In the worst case, the algorithm must shift each element for every insertion,
leading to quadratic time complexity.

4. Quick Sort:
 HPSC PGT COMPUTER
SCIENCE 2025

 Process:

o Quick sort is a divide-and-conquer algorithm that works by selecting a "pivot"

element from the array and partitioning the other elements into two sub-arrays:
one with elements smaller than the pivot and the other with elements larger than
the pivot. This is done recursively for each sub-array.

 Average Case: O(nlog⁡n)O(n \log n)O(nlogn)

o When the pivot divides the array into roughly equal halves, the recursive calls
result in a logarithmic depth of recursion, with each level taking linear time to
partition the array.

 Worst Case: O(n2)O(n^2)O(n2)

o If the pivot chosen is always the smallest or largest element, the array will not be
well partitioned, and the algorithm will degrade to the performance of bubble
sort.

5. Merge Sort:

 Process:

o Merge sort divides the array into two halves, recursively sorts each half, and then
merges the sorted halves back together. The merge step ensures that the
resulting array is sorted.

 Best, Worst, and Average Case: O(nlog⁡n)O(n \log n)O(nlogn)

o The complexity of merge sort remains the same in all cases because it consistently
divides the array into two halves and merges them, which takes O(nlog⁡n)O(n
\log n)O(nlogn) time.

6. Heap Sort:

 Process:

o Heap sort uses a binary heap data structure to sort an array. First, the array is
transformed into a heap (a binary tree that satisfies the heap property, where
each parent node is greater than its children). Then, the root element is swapped
with the last element in the heap, and the heap is restored. This process continues
until the heap is empty, and the array is sorted.

 Time Complexity:

o Worst, Best, and Average Case: O(nlog⁡n)O(n \log n)O(nlogn)

o Heap sort is quite efficient because it guarantees O(nlog⁡n)O(n \log n)O(nlogn)

performance regardless of the input.

More on Asymptotic Notation

 HPSC PGT COMPUTER
SCIENCE 2025

Understanding asymptotic notation is crucial for analyzing the efficiency of algorithms. Here's a
bit more detail:

1. Big-O Notation (O):

 Definition: Big-O describes the upper bound of an algorithm's runtime, meaning the
maximum time the algorithm will take to run. It gives us an idea of how the algorithm
performs in the worst-case scenario as the input size increases.

 Example:

o If an algorithm has a time complexity of O(n2)O(n^2)O(n2), it means that in the

worst case, the time taken will increase quadratically with the size of the input.

 Common Uses: Big-O is often used to describe the worst-case or upper bound behavior
of sorting algorithms (e.g., O(nlog⁡n)O(n \log n)O(nlogn) for quick sort and merge sort).

2. Omega Notation (Ω):

 Definition: Omega notation describes the lower bound of an algorithm's runtime,

meaning the best-case scenario. It tells us the minimum time an algorithm will take to run.

 Example:

o An algorithm with Ω(n)\Omega(n)Ω(n) means that in the best case, it will require
at least nnn operations, even if the input is optimal.

 Common Uses: Omega is used when you want to describe the best-case performance.
For example, if an algorithm performs better than O(n2)O(n^2)O(n2) in the best case,
you can express it with Ω(n)\Omega(n)Ω(n).

3. Theta Notation (Θ):

 Definition: Theta notation provides a tight bound on the algorithm's runtime. It describes
both the upper and lower bounds, meaning the algorithm’s running time will always be
within a certain range as the input size increases.

 Example:

o If an algorithm has Θ(nlog⁡n)\Theta(n \log n)Θ(nlogn), it means that the algorithm

will take nlog⁡nn \log nnlogn time for both the best and worst cases, and that’s
the expected behavior as the input size grows.

 Common Uses: Theta notation is used when the best and worst cases have the same
time complexity, such as with merge sort, which has Θ(nlog⁡n)\Theta(n \log n)Θ(nlogn)
time complexity.

Visualizing the Time Complexity of Algorithms

 Graphical Representation: A graphical representation of time complexities helps

understand how different algorithms scale with increasing input size. For example:
 HPSC PGT COMPUTER
SCIENCE 2025

o O(n)O(n)O(n) is a linear increase.

o O(n2)O(n^2)O(n2) is a quadratic increase, which grows much faster than linear.

o O(nlog⁡n)O(n \log n)O(nlogn) is faster than O(n2)O(n^2)O(n2), but slower than

linear time.

o O(log⁡n)O(\log n)O(logn) represents logarithmic growth, which is much slower

than linear growth and is characteristic of efficient algorithms like binary search.

Summary of Sorting Algorithm Use Cases

 Bubble Sort: Best for small datasets or nearly sorted arrays due to its simple
implementation and O(n)O(n)O(n) best case.

 Selection Sort: Efficient in terms of swap operations, but its O(n2)O(n^2)O(n2) complexity
makes it unsuitable for large datasets.

 Insertion Sort: Very efficient for small or partially sorted datasets but suffers from
O(n2)O(n^2)O(n2) performance on large, unsorted datasets.

 Quick Sort: A very fast and widely used algorithm with average-case O(nlog⁡n)O(n \log
n)O(nlogn), though it can degrade to O(n2)O(n^2)O(n2) in the worst case.

 Merge Sort: Preferred for large datasets or when stability is needed, as it guarantees
O(nlog⁡n)O(n \log n)O(nlogn) performance and is stable.

 Heap Sort: Suitable when O(nlog⁡n)O(n \log n)O(nlogn) performance is needed with
constant time for extracting the maximum element (in a priority queue).

Graphs: Definitions and Concepts

Graphs are fundamental data structures used to represent relationships or connections between
entities. A graph consists of vertices (also called nodes) and edges (also called arcs or links) that
connect pairs of vertices.

1. Graph Definition

A graph GGG is a set of vertices VVV and a set of edges EEE, where each edge connects two
vertices. Formally, it is represented as G=(V,E)G = (V, E)G=(V,E), where:

 VVV is the set of vertices.

 EEE is the set of edges, each of which connects a pair of vertices.

2. Types of Graphs

 Connected Graph:
A connected graph is a graph in which there is a path between every pair of vertices. In
other words, there are no isolated vertices in a connected graph.
 HPSC PGT COMPUTER
SCIENCE 2025

 Regular Graph:
A regular graph is a graph in which every vertex has the same degree, meaning each
vertex is connected to the same number of edges. For example, a 3-regular graph
means every vertex has exactly 3 edges.

 Bipartite Graph:
A bipartite graph is a graph where the set of vertices VVV can be divided into two
disjoint sets UUU and WWW such that every edge in the graph connects a vertex in UUU
to a vertex in WWW. No edge exists between two vertices in the same set. This type of
graph is often used to model relationships between two different sets of objects, such as
jobs and workers.

3. Cycles and Circuits

 Cycle:
A cycle in a graph is a path that starts and ends at the same vertex and does not repeat
any edge or vertex except for the starting and ending vertex. In a directed graph, it is
called a directed cycle.

 Circuit:
A circuit is a path that starts and ends at the same vertex and may repeat vertices or
edges, but no other vertices are visited more than once except for the starting/ending
vertex. A circuit can be either directed or undirected.

4. Spanning Tree

A spanning tree of a graph is a subgraph that includes all the vertices of the graph, is
connected, and contains no cycles. A graph can have multiple spanning trees, and the total
number of edges in a spanning tree is always V−1V - 1V−1, where VVV is the number of vertices
in the graph.

 Minimum Spanning Tree (MST) is a spanning tree where the sum of the weights of the
edges is minimized. Algorithms like Prim’s and Kruskal’s are used to find MSTs.

5. Graph Traversal

 Breadth-First Search (BFS):

BFS is an algorithm used to traverse or search a graph in a breadthward motion. It starts
at a source vertex and explores all of its neighboring vertices at the present depth before
moving on to vertices at the next level. It uses a queue data structure.

Algorithm:

1. Start with a source vertex.

2. Mark the source vertex as visited and enqueue it.

3. While the queue is not empty:

 Dequeue a vertex, visit its neighbors, and enqueue them if they are not
visited.
 HPSC PGT COMPUTER
SCIENCE 2025

4. Repeat until all reachable vertices are visited.

 Depth-First Search (DFS):

DFS is an algorithm used to traverse or search a graph in a depthward motion. It starts at
the source vertex and explores as far as possible along each branch before
backtracking. DFS uses a stack (or recursion).

Algorithm:

1. Start with a source vertex.

2. Mark the vertex as visited and push it onto the stack.

3. While the stack is not empty:

 Pop a vertex, visit its unvisited neighbors, and push them onto the stack.

4. Repeat until all reachable vertices are visited.

6. Applications of Graphs

 Graphs are used to model networks, social media connections, transportation systems,
recommendation systems, etc.

 Spanning trees are used in network design to ensure connectivity with the least cost.

 BFS is used in finding the shortest path in unweighted graphs.

 DFS is useful for tasks like topological sorting and detecting cycles in directed graphs.

Additional Graph Concepts

7. Directed and Undirected Graphs

 Undirected Graph:
In an undirected graph, the edges have no direction. The edge (u,v)(u, v)(u,v) is the
same as the edge (v,u)(v, u)(v,u). That is, if there is an edge between vertex uuu and
vertex vvv, it can be traversed in both directions.

 Directed Graph (Digraph):

In a directed graph, the edges have a direction, meaning the edge (u,v)(u, v)(u,v) can
only be traversed from vertex uuu to vertex vvv. The direction is represented as an arrow
pointing from one vertex to another. Directed graphs are used to model situations like
traffic flow, web pages, and social media followers.

8. Weighted Graph

A weighted graph is a graph in which each edge has a weight or cost associated with it. These
weights represent the cost, distance, or time to traverse between the vertices connected by the
edge. Weighted graphs are essential in shortest path problems (like finding the fastest route) and
minimum spanning tree problems.

9. Adjacency Matrix and Adjacency List Representations

 HPSC PGT COMPUTER
SCIENCE 2025

Graphs can be represented in various ways, depending on the nature of the problem and the
efficiency required for certain operations.

 Adjacency Matrix:
An adjacency matrix is a 2D array where each element matrix[i][j]matrix[i][j]matrix[i][j]
represents the presence of an edge between vertex iii and vertex jjj. In the case of a
weighted graph, the matrix entry holds the weight of the edge.

o Advantages: Fast to check if an edge exists between two vertices.

o Disadvantages: Space inefficient for sparse graphs (where most of the edges are
missing).

 Adjacency List:
An adjacency list is an array of lists or a dictionary where each list holds the vertices that
are connected to the vertex at the corresponding index. For a directed graph, each list
stores only the outgoing vertices.

o Advantages: Space-efficient for sparse graphs.

o Disadvantages: Checking for the existence of an edge between two vertices can
be slower.

10. Path and Distance in a Graph

 Path:
A path is a sequence of vertices where each consecutive pair is connected by an edge.
A simple path does not repeat any vertices (except potentially the starting and ending
vertices in a cycle).

 Distance:
The distance between two vertices is the number of edges in the shortest path
connecting them. In unweighted graphs, this can be directly determined by BFS.

11. Graph Coloring

Graph coloring is an assignment of labels (colors) to the vertices of a graph such that no two
adjacent vertices share the same color. It is used in scheduling problems, map coloring, and
resource allocation. The minimum number of colors required to color a graph is called its
chromatic number.

Applications:

 Map coloring: Assigning different colors to adjacent regions.

 Scheduling problems: Assigning time slots or resources in such a way that conflicts
(adjacent tasks) do not occur at the same time.

Detailed Explanation of Traversal Algorithms

Breadth-First Search (BFS)

 HPSC PGT COMPUTER
SCIENCE 2025

BFS is ideal for finding the shortest path in unweighted graphs because it explores all vertices at
the present depth level before moving to the next level.

Steps:

1. Start at the root (or source vertex).

2. Mark the starting vertex as visited.

3. Enqueue the starting vertex into the queue.

4. While the queue is not empty:

o Dequeue a vertex.

o For each neighbor of the vertex, if it is not visited, mark it as visited and enqueue
it.

5. Continue until all vertices are explored.

Complexity:

 Time Complexity: O(V+E)O(V + E)O(V+E), where VVV is the number of vertices and EEE is
the number of edges.

 Space Complexity: O(V)O(V)O(V) due to the storage of the queue.

Applications:

 Shortest path in unweighted graphs (like finding the minimum number of hops in a
network).

 Web crawlers.

 Broadcasting in networks.

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It is useful for tasks like
topological sorting, cycle detection, and pathfinding in maze problems.

Steps:

1. Start at the root (or source vertex).

2. Mark the vertex as visited.

3. For each neighbor of the vertex, if it is not visited, recursively call DFS on it.

4. Backtrack when no unvisited neighbors remain.

Complexity:

 Time Complexity: O(V+E)O(V + E)O(V+E).

 Space Complexity: O(V)O(V)O(V) for the recursive stack.

 HPSC PGT COMPUTER
SCIENCE 2025

Applications:

 Topological sorting of a Directed Acyclic Graph (DAG).

 Solving puzzles or mazes.

 Detecting cycles in directed graphs.

 Pathfinding in certain graph structures.

12. Special Graph Types

 Complete Graph:
A complete graph is a graph in which there is an edge between every pair of vertices. A
complete graph with nnn vertices is denoted by KnK_nKn.

 Tree:
A tree is an acyclic connected graph. It is a special case of a graph that has no cycles.
A tree with nnn vertices has n−1n - 1n−1 edges.

 Forest:
A forest is a disjoint set of trees. It is an acyclic graph where there may be multiple
connected components, each being a tree.