UNIT 4 -Graph: Definition

Graph and its representations

Graphs are non-linear data structures made up of a finite number of nodes or vertices and the edges that
connect them. Graphs in data structures are used to address real-world problems in which it represents the
problem area as a network like telephone networks, circuit networks, and social networks.
For example, it can represent a single user as nodes or vertices in a telephone network, while the link between
them via telephone represents edges.
A Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also
referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More formally a
Graph is composed of a set of vertices(V) and a set of edges(E). The graph is denoted by G(V, E).

This graph has a set of vertices V= {1,2,3,4,5} and a set of edges E= {(1,2), (1,3), (2,3),(2,4),(2,5),(3,5),(4,5)}

• Undirected graph: In an undirected graph, edges are not associated with the directions with them. An
undirected graph is shown in the above figure since its edges are not attached with any of the
directions.

• Directed Graph: In a directed graph, edges form an ordered pair. Edges represent a specific path from
some vertex A to another vertex B. Node A is called initial node while node B is called terminal node.

The two representations of graphs in data structures

• Adjacency matrix
• Adjacency list

Adjacency Matrix
A sequential representation is an adjacency matrix. It's used to show which nodes are next to one another. I.e.,
is there any connection between nodes in a graph
You create an M x M matrix G for this representation. If an edge exists between vertex a and vertex b, the
corresponding element of G, g[i,j] = 1, otherwise g[i,j] = 0.

• Undirected Graph Representation

 • Directed Graph Representation

Adjacency List
An adjacency list represents a graph as an array of linked lists. The index of the array represents a vertex and
each element in its linked list represents the other vertices that form an edge with the vertex.
Let G=(V, E) be a graph , an adjacency linked list is an array of n linked lists where n is the number of vertices
in graph G, Each location of an array represents a vertex of the graph.

Representation of Undirected Graph as Adjacency list:

The below undirected graph has 3 vertices. So, an array of list will be created of size 3, where each indices
represent the vertices. Now, vertex 0 has two neighbours (i.e, 1 and 2). So, insert vertex 1 and 2 at indices 0 of
array. Similarly, For vertex 1, it has two neighbour (i.e, 2 and 0) So, insert vertices 2 and 0 at indices 1 of
array. Similarly, for vertex 2, insert its neighbours in array of list.

Representation of Directed Graph as Adjacency list:

• The below directed graph has 3 vertices. So, an array of list will be created of size 3, where ea ch
indices represent the vertices. Now, vertex 0 has no neighbours. For vertex 1, it has two neighbour (i.e,
0 and 2) So, insert vertices 0 and 2 at indices 1 of array. Similarly, for vertex 2, insert its neighbours in
array of list.

Graph Traversal Algorithms - Depth First Search, Breadth First Search

To process, analyze, or search through a graph, we need a method to visit nodes in an organized manner. That
organized process is called graph traversal.
DFS and BFS are the core traversal strategies. They aim to visit every node but do so in very different styles
The two very important algorithms that systematically process all vertices and edges of a graph. These two
traversal algorithms are depth first search(DFS) and breadth first search(BFS)
These algorithms have proved to be useful for many applications involving graphs in artificial intelligence and
operation research

Depth- First search

Depth-First Search or DFS algorithm is a recursive algorithm that uses the backtracking principle.
It is a recursive algorithm to search all the vertices of a tree data structure or a graph. The depth-first search
(DFS) algorithm starts with the initial node of graph G and goes deeper until we find the leaf node or the node
with no children.
Because of the recursive nature, stack data structure can be used to implement the DFS algorithm
Steps to implement DFS traversal
Step 1 - Define a Stack of size total number of vertices in the graph.
Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it on to the Stack.
Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the top of stack and push it on
to the stack.
Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which is at the top of the stack.
Step 5 - When there is no new vertex to visit then use back tracking and pop one vertex from the stack.
Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
Step 7 - When stack becomes Empty, then produce final spanning tree by removing unused edges from the
graph

Algorithm for Depth First search

DFS(G)
void DFS(int node)
visit[node]=true;
print node
for (int i=0;i<n;i++)
if (a[node][i]==1 &s& visit[i]==false)
DFS(i); //recursive call
Breadth First Search:
Breadth First Search (BFS) is a graph traversal algorithm that starts from a source node and explores the graph
level by level. First, it visits all nodes directly adjacent to the source. Then, it moves on to visit the adjacent
nodes of those nodes, and this process continues until all nodes are visited
• BFS is different from DFS in a way that closest vertices are visited before others. We mainly traverse
vertices level by level.
• It is a recursive algorithm to search all the vertices of a tree or graph data structure.
• Queue data structure can be used to implement the BFS algorithm
•
The step-by-step process to implement the BFS traversal is given as follows –
1. Create a queue and mark all vertices as not visited.
2. Choose a starting vertex and enqueue it into the queue.
3. Mark the chosen vertex as visited.
4. Dequeue a vertex from the queue and visit it.
5. Enqueue all non-visited neighbors (adjacent vertices) of the dequeued vertex.
6. Repeat steps 4 and 5 until the queue is empty.
7. If there are still unvisited vertices, go back to step 2 and choose another starting vertex.
8. Repeat steps 2-7 until all vertices are visited.
Algorithm
BFS(G)
void BFS(int s)
while(front<=rear)
begin
node=q[front++];
print node;
for i=0 to n
if (a[node][i]==1 && visit[i]==false)
begin
q[++rear]=i;
visit[i]=true;
end

Application of Graphs in Data Structures

Following are some applications of graphs in data structures:
• Graphs are used in computer science to depict the flow of computation.
• Users on Facebook are referred to as vertices, and if they are friends, there is an edge connecting them.
The Friend Suggestion system on Facebook is based on graph theory.
• Graph used for the Resource Allocation in the Operating System, where each process and resource are
regarded vertically. Edges are drawn from resources to assigned functions or from the requesting
process to the desired resource.
• Web pages are referred to as vertices on the World Wide Web. Suppose there is a link from page A to
page B that can represent an edge. This application is an illustration of a directed graph.
• Google maps use graphs for building transportation systems, where intersection of two (or more) roads
is considered to be a vertex and the road connecting two vertices is considered to be an edge, thus their
navigation system is based on the algorithm to calculate the shortest path between two vertices.

Sorting Techniques
Selection sort
The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion of the list and
swaps it with the first element of the unsorted part.
How Selection Sort works
1. In the selection sort, first of all, we set the initial element as a minimum.
2. Now we will compare the minimum with the second element. If the second element turns out to be smaller
than the minimum, we will swap them, followed by assigning to a minimum to the third element.
3. Else if the second element is greater than the minimum, which is our first element, then we will do nothing
and move on to the third element and then compare it with the minimum. We will repeat this process until we
reach the last element.
4. After the completion of each iteration, we will notice that our minimum has reached the start of the
unsorted list.
ALGORITHM SelectionSort (A[0….. n -1])
//Sorts a given array by selection sort
SelectionSort (A[0….. n -1])
for i  0 to n - 2 do
min  i
for j  i+1 to n-1 do
if A[j] < A[min]
min  j
tempa[i]
a[i]a[min]
a[min]temp

To measure performance of algorithms, we typically use time and space complexity analysis. The idea is to
measure order of growths in terms of input size.
Space complexity
Problem-solving using computer requires memory to hold temporary data or final result while the program is
in execution. The amount of memory required by the algorithm to solve given problem is called space
complexity of the algorithm
Time Complexity: The time complexity of an algorithm quantifies the amount of time taken by an algorithm
to run as a function of the length of the input.

Time Complexities:
• Best Case Complexity: The selection sort algorithm has a best-case time complexity of O(n2) for the
already sorted array.
• Average Case Complexity: The average-case time complexity for the selection sort algorithm is
O(n2), in which the existing elements are in jumbled ordered, i.e., neither in the ascending order nor in
the descending order.
• Worst Case Complexity: The worst-case time complexity is also O(n2), which occurs when we sort
the descending order of an array into the ascending order
Space Complexity is the measure of memory consumed by a program to operate on the input of a given size,
It only uses a constant amount of extra space for a few temporary variables (e.g., to store the index of the
minimum element and for swapping values). This results in a space complexity of O(1)

Bubble Sort
Bubble sort works on the repeatedly swapping of adjacent elements until they are not in the specific order. It is
called bubble sort because the movement of array elements is just like the movement of air bubbles in the
water.
The bubble sort starts with the very first index and makes it a bubble element. Then it compares the bubble
element, which is currently our first index element, with the next element. If the bubble element is greater and
the second element is smaller, then both of them will swap. After swapping, the second element will become
the bubble element. Now we will compare the second element with the third as we did in the earlier step and
swap them if required. The same process is followed until the last element
For each iteration, the bubble sort will compare up to the last unsorted element. Once all the elements get
sorted in the ascending order, the algorithm will get terminated
 ALGORITHM BubbleSort(A[0..n − 1])
//Sorts a given array by bubble sort
BubbleSort(A[0..n − 1])
for i ← 0 to n − 1 do
for j ← 0 to n − 1 − i do
if A[j ] > A[j+1]
temp a[j]
a[j] a[j+1]
a[j+1] temp
end if
end for
end for

Complexity Analysis of Bubble Sort

Best Case Complexity: The bubble sort algorithm has a best-case time complexity of O(n) for the already
sorted array.
Average Case Complexity: The average-case time complexity for the bubble sort algorithm is O(n2), which
happens when 2 or more elements are in jumbled, i.e., neither in the ascending order nor in the descending
order.
Worst Case Complexity: The worst-case time complexity is also O(n2), which occurs when we sort the
descending order of an array into the ascending order.

Space Complexity Analysis of Bubble Sort:

• The space complexity of Bubble Sort is O(1). This means that the amount of extra space (memory)
required by the algorithm remains constant regardless of the size of the input array being sorted. Bubble
Sort only needs a constant amount of additional space to store temporary variables or indices during the
sorting process.
Searching Techniques
LINEAR SEARCH: Linear search is also called as sequential search algorithm. It is the simplest searching
algorithm. In Linear search, we simply traverse the list completely and match each element of the list with the
item whose location is to be found. If the match is found, then the location of the item is returned; otherwise,
the algorithm returns NULL.
Here's a basic algorithm for sequential search:
1. Start at the beginning of the list.
2. Compare the target element with the current element in the list.
3. If a match is found, return the index (or position) of the element.
4. If the end of the list is reached without finding a match, indicate that the target element is
not in the list
Wworking of linear search with an [Link] the element to be searched is K = 41
Algorithm
void linear(int a[], int n, int key)
for i=0 to n
if (a[i]==key)
flag=1;
if (flag==1)
print Element is present in the array
else
print Element is not present in the array
Time Complexity
Best Case Complexity - In Linear search, best case occurs when the element we are finding is at the first
position of the array. The best-case time complexity of linear search is O(1).
Average Case Complexity - The average case time complexity of linear search is O(n).
Worst Case Complexity - In Linear search, the worst case occurs when the element we are looking is present
at the end of the array. The worst-case in linear search could be when the target element is not present in the
given array, and we have to traverse the entire array. The worst-case time complexity of linear search is O(n).

Space Complexity of Linear Search: O(1)

• Linear search is an in-place algorithm that does not require additional memory (apart from a few
variables like i for indexing and target for comparison).
• Therefore, the space complexity of linear search is O(1)

BINARY SEARCH
Binary search is the search technique that works efficiently on sorted lists. Hence, to search an element into
some list using the binary search technique, we must ensure that the list is sorted.
• Binary search follows the divide and conquer approach in which the list is divided into two halves, and
the item is compared with the middle element of the list. If the match is found then, the location of the
middle element is returned. Otherwise, we search into either of the halves depending upon the result
produced through the match.
The following is our sorted array and let us assume that we need to search the location of value 31 using
binary search.

Algorithm
Repeat steps until low meets high. do until the pointers low and high meet each other.
mid = (low + high)/2
if (key == arr[mid])
return mid
if (key > arr[mid]) // Key is on the right side
low = mid + 1
 if (key < arr[mid])
high = mid – 1 /// Key is on the left side

Time Complexity:
Best Case: O(1) (target is the middle element on the first try).
Average Case: O(log N)
Worst Case: O(log N)
Space Complexity: As we are not using any significant extra memory in Binary Search, the space
complexity is constant, i.e. O(1).

Heap
A heap is a tree where each parent node is greater than or equal to its child nodes in a max-heap or less than or
equal to its child nodes in a min-heap. This means the largest or smallest value is always at the top (root) of
the tree.
• There are two main types of heaps: Max-Heap and Min-Heap in data structure. Let's look at each type
with examples.

Max-Heap
In a max-heap, each parent node is greater than or equal to its child nodes. This ensures that the largest value
is always at the root of the tree.
In other words, the max heap can be defined as for every node i. Mathematically, it can be defined as:
A[Parent(i)] >= A[i]

Example of a Max-Heap:
• The root node (50) is greater than its children (30 and 20).
• Each parent node (30, 20) is greater than its children (15, 10 for 30 and 8, 5 for 20).

Min-Heap
In a min-heap, each parent node is less than or equal to its child nodes. This ensures that the smallest value is
always at the root of the tree.
In other words, the min-heap can be defined as, for every node i, Mathematically, it can be defined as:
A[Parent(i)] <= A[i]
Example of a Min-Heap:

The root node (5) is smaller than its children (10 and 15).
Each parent node (10, 15) is smaller than its children (30, 20 for 10 and 50, 40 for 15).
The two main operations that can be performed on a heap are insertion & deletion
1. Insertion: To insert a new element into a heap,
The step-by-step process for insertion is :
1)Add the new element to the bottom rightmost spot in the tree (the end of the array).
2)Compare the new element with its parent.
3)If the parent is smaller than the new element (in a max heap) or larger than the new element (in a min-heap),
swap them.
4) Repeat steps 2 & 3 until the heap property is satisfied.

2. Deletion
Deletion in a heap always happens at the root.
To delete the root element,
Let’s see the step-by-step process for deletion:
• Replace the root element with the last element in the array.
• Compare the new root with its children.
• If a child is larger than the root (in a max heap) or smaller than the root (in a min-heap), swap the root
with the larger (or smaller) child.
Repeat steps 2 & 3 until the heap property is satisfied

Applications of Heap
 Priority Queue: Heaps are the fundamental data structures behind priority queues. A priority queue is
used when objects are to be processed based on the priority assigned to them and not on the order in
which they arrive.
 Sorting: The heap data structure can create a sorting algorithm called Heapsort.
 Lossless Compression: Heaps are used in data compression algorithms (the process of reducing file
size by eliminating redundancy and re-encoding data using fewer bits) such as Huffman coding.
 Resource allocation: Heaps can be used to efficiently allocate resources in a system, such as memory
blocks or CPU time
 Medical Applications: In medical applications, heaps are used to store and manage patient
information based on priority, such as vital signs, treatments, and test results