MORE ABOUT PATENT

KRUSKAL’S ALGORITHM

In this blog, we will discuss Kruskal’s set of rules. Right here, we can also see the complexity, running, example, and implementation of the Kruskal’s set of rules. However earlier than shifting at once toward the algorithm, we need to first recognize the primary terms which include spanning tree and minimal spanning tree.

Spanning tree — A spanning tree is a subgraph of the connected and undirected graph, that’s a tree and connects all the vertices collectively

Minimum Spanning tree — Minimum spanning tree can be defined as the spanning tree in which the sum of the weights of all the edges is minimum. The weight of the spanning tree is the sum of the weights given to the edges of the spanning tree.

Now, let’s begin with the principle topic.

Kruskal’s algorithm is used to discover the minimal spanning tree for a connected weighted graph. the main goal of the set of rules is to discover the subset of edges through using which we can traverse every vertex of the graph. It follows the greedy method that finds an most effective answer at each stage in preference to that specialize in a global surest.

How does kruskal’s algorithm works?

In Kruskal’s algorithm, we begin from edges with the lowest weight and keep adding the rims until the goal is reached. the steps to implement Kruskal’s set of rules are indexed as follows -

· First, sort all the edges from low weight to excessive.

· Now, take the edge with the lowest weight and upload it to the spanning tree. If the edge to be brought creates a cycle, then reject the edge.

· Continue to feature the edges until we attain all vertices, and a minimal spanning tree is created.

The applications of Kruskal’s algorithm are -

· Kruskal’s algorithm may be used to format electric wiring among cities.

· It can be used to put down LAN connection

Complexity of Kruskal’s algorithm

Now, let’s have a look at the time complexity of Kruskal’s algorithm.
Time Complexity

The time complexity of Kruskal’s algorithm is O(E logE) or O(V logV), in which E is the no. of edges, and V is the no. of vertices.

Now let’s see an example

Here we have a graph with 9 vertices

Step 1 — Sort all the edges in the ascending order of there weight

As you can see, edges are sorted in the ascending order of there weight.

Step 2 — Pick the edges and check whether including it making a close cycle or not, if not then include it in the MST else discard it and move on the next edge.

We will check every edge one by one

Yellow edge means the edge is the part of the MST

We will continue adding edges until we get |V-1| edges where V is number of vertices in the original graph.

So this is the final MST as we got the |V — 1| edges.

Weight of the MST is 37.

SO ITS ALL ABOUT KRUSKAL’S ALGORITHM .