Kruskal's Algorithm

Vaishnavi Sharma — Mon, 14 Jun 2021 07:42:03 +0000

Kruskal's Algorithm finds a minimum spanning tree of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree(MST).
It is a greedy algorithm in graph theory as in each step it adds the next lowest-weight edge that will not form a cycle to the minimum spanning tree.

Lets Code :D

But first lets read the step wise guide :)

What we need?

Class Edge :- Properties : i) Source ii) Destination iii) Weights
Array of type Edge of size e (number of edges) - Input from user
Array output of type Edge of size e - 1 (the required MST)

STEPS:

Take input.
Sort the input array in increasing order according to their weights.
Create a parent array of size n (number of vertices) as - parent[n] = { 0, 1, 2, 3, ...}
Initialize count as 0.
while ( count < n - 1){ e edge is between two vertices - v1 and v2 parent of v1 is let, v1P and parent of v2 is let, v2p. If parent is same, next iteration. Else count + 1, update parent[] }
At last you'll get minimum spanning tree and then print the output.

Easy?

Below is the code for Kruskal's Algorithm in C++

Hope you enjoyed :)

Merge Sort, Its not hard!

Vaishnavi Sharma — Sun, 23 May 2021 09:57:46 +0000

Merge sort works on the principle of divide and conquer algorithm. It is one of the most efficient sorting algorithm. The top down merge sort approach uses recursion. We break/divide the array into subparts (till single element).

This sorting algorithm recursively sorts the subparts and then merges them into a single sorted array.

There are 4 important points where all the process of merge sort takes place:

Find the middle element of the array.
Call mergeSort function for the first half.
Call mergeSort function for the second half.
Merge the two halves into a single sorted array, and yes, this is the answer! Ain't that easy? it is!

Below is the function mergeSort() in C++ language:

Time Complexity:

Total T(n) work is done which is divided as:

k amount of constant work,
T(n/2) work for 2 halves,
Merge two halves = k1n,
Copy elements to input array = k2n, So, T(n) = k + T(n/2) + T(n/2) + k1n + k2n T(n) = 2T(n/2) + Kn {K here is the sum of all constants - k, k1, k2}

The recurrence relation that we'll get-
T(n) = 2T(n/2) + Kn
After solving this recurrence relation, we'll come to the conclusion that the time complexity for merge sort is-
O(nlogn)

Space Complexity:

Space complexity is the maximum space required at any point of time during execution of a program.
In merge sort, we use recursion on half part of the array, So the calling will be done as (n is size of the array):
n -> n/2 -> n/4 -> n/8 ... and so on
that is, logn function waiting in the call stack.
-> klogn space for storing functions
-> kn for array
So the maximum space required is kn,
Space Complexity will be O(n).

I hope now you can do problems on merge sort :)

DEV Community: Vaishnavi Sharma

Kruskal's Algorithm

Merge Sort, Its not hard!