Ads Unit-2

ADS-Unit -2
Graph
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.
Representations of Graph
1. Adjacency Matrix
2. Adjacency List
Adjacency Matrix
Let’s assume there are n vertices in the graph So, create a 2D matrix adjMat[n]
[n] having dimension n x n.
 If there is an edge from vertex i to j, mark adjMat[i][j] as 1.
 If there is no edge from vertex i to j, mark adjMat[i][j] as 0.
Representation of Undirected Graph in Adjacency
Matrix:
Representation of directed Graph in Adjacency Matrix:
Adjacency List
Let’s assume there are n vertices in the graph So, create an array of list of
size n as adjList[n].
 adjList[0] will have all the nodes which are connected (neighbour) to
vertex 0.
 adjList[1] will have all the nodes which are connected (neighbour) to
vertex 1 and so on.
Undirected graph
directed graph
Graph traversals
Graph traversal refers to the process of visiting all the nodes (vertices) in a
graph in a systematic way. The two most common types of graph traversal
algorithms are:
1. Breadth-First Search (BFS):
2. Depth-First Search (DFS):
Breadth-First Search (BFS):

BFS is the application of queue.
Algorithm
1. Start with inserting anyone of the vertices from the graph into the
queue.
2. First, delete the front queue item and add it to the list of the visited
nodes.
3. Add adjacent nodes of the deleted vertex which have not been visited
yet into the queue.
4. Keep repeating steps 2 and 3 until the queue is found to be empty.
Find BFS for the graph
Depth-First Search (DFS):
DFS is the application of stack.
Algorithm
1. Start with pushing anyone of the vertices of the graph on top of stack.
2. Put the top item of the stack and add it to the visited vertex list.
3. Add adjacent nodes of the top of stack which have not been visited yet.
4. Keep repeating steps 2 and 3, and the stack becomes empty.
Find DFS for the graph
Connected Component
Connected Component: A maximal subgraph in which any two vertices are
connected, and there is no path to any vertex outside the subgraph.
In a connected component, every node is reachable from every other node
within the component.
Here, the graph has two connected components:
1. Component 1: (0,1,2)
2. Component 2: (3,4)
The nodes in component 1 are all connected to each other, while nodes in
component 2 form another separate connected group.
Bi-connected components
A biconnected component is a maximal subgraph that remains connected even
after the removal of any single vertex. In other words, it is a subgraph where
there is no "articulation point" or "cut vertex" whose removal would
disconnect the subgraph.
Articulation Point (Cut Vertex): A vertex whose removal increases the number
of connected components in the graph.
Divide and Conquer
The basic idea is to recursively divide the problem into smaller subproblems
until they become simple enough to be solved directly. Once the solutions to
the subproblems are obtained, they are then combined to produce the overall
solution.
Pseudo code of Divide and conquer
Step 1: Divide the problem into subproblems
subproblem1, subproblem2 = Divide(problem)
Step 2: Conquer the subproblems by recursively solving them
result1 = DivideAndConquer(subproblem1)
result2 = DivideAndConquer(subproblem2)
Step 3: Combine the results from the subproblems to form the final solution
result = Combine(result1, result2)
return result
Problems solved by Divide and conquer
1.Quick sort
2.Merge sort
3.Strassen's Matrix Multiplication
Quick sort
Quicksort picks an element as pivot, and then it partitions the given array
around the picked pivot element. In quick sort, a large array is divided into two
arrays in which one holds values that are smaller than the specified value
(Pivot), and another array holds the values that are greater than the pivot.
After that, left and right sub-arrays are also partitioned using the same
approach. It will continue until the single element remains in the sub-array.
Choosing the pivot
Pivot is the last element of the given array.
Algorithm:
QUICKSORT (array A, start, end)
{
if (start < end)
{
p = partition(A, start, end)
QUICKSORT (A, start, p - 1)
QUICKSORT (A, p + 1, end)
}
}
Partition Algorithm:
The partition algorithm rearranges the sub-arrays in a place.
PARTITION (array A, start, end)
{
pivot =A[end]
i = start-1
for j = start to end -1 {
if (A[j] < pivot) {
i=i+1
swap A[i] with A[j]
}
}
swap A[i+1] with A[end]
return i+1
}
Example
Sort word EXAMPLE in alphabetical order
Quick Sort Time Complexities
Merge Sort
It divides the given list into two equal halves, calls itself for the two halves and
then merges the two sorted halves. We have to define the merge() function to
perform the merging.
The sub-lists are divided again and again into halves until the list cannot be
divided further. Then we combine the pair of one element lists into two-
element lists, sorting them in the process and so on until we get the sorted list.
Algorithm
In the following algorithm, arr is the given array, beg is the starting element,
and end is the last element of the array.
MERGE_SORT(arr, beg, end)
{
if beg < end
{
mid = (beg + end)/2
MERGE_SORT(arr, beg, mid)
MERGE_SORT(arr, mid + 1, end)
MERGE (arr, beg, mid, end)
}
}
/* Function to merge the subarrays of a[] */
void merge(int a[], int beg, int mid, int end)
{
int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;
int LeftArray[n1], RightArray[n2]; //temporary arrays
/* copy data to temp arrays */
for (int i = 0; i < n1; i++)
LeftArray[i] = a[beg + i];
for (int j = 0; j < n2; j++)
RightArray[j] = a[mid + 1 + j];
i = 0, /* initial index of first sub-array */

j = 0; /* initial index of second sub-array */
k = beg; /* initial index of merged sub-array */
while (i < n1 && j < n2)
{
if(LeftArray[i] <= RightArray[j])
{
a[k] = LeftArray[i];
i++;
}
else
{
a[k] = RightArray[j];
j++;
}
k++;
}
while (i<n1)
{
a[k] = LeftArray[i];
i++;
k++;
}
while (j<n2)
{
a[k] = RightArray[j];
j++;
k++;
}
}
Recursive calls of Mergesort() function and the way the elements are merged
Time complexities of merge sort

Ads Unit-2

Uploaded by

Copyright:

Available Formats

Ads Unit-2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ads Unit-2

Uploaded by

Copyright:

Available Formats

ADS-Unit -2

Breadth-First Search (BFS):

i = 0, /* initial index of first sub-array */

You might also like