Kruskel's algorithm

 This tutorial will help, you to find out about how Kruskel's algorithm works. Additionally, you'll find working samples of Kruskel's algorithm in C, C ++, Java, and Python.

Kruskel's algorithm is that the minimum spanning tree algorithm that takes a graph as input and finds a subset of the sides of that graph

 Form a tree that contains all the titles
 it's rock bottom weight among all the trees which will be formed from the graph
 

Understand working of Kruskel's algorithm

Greed belongs to the category of algorithms referred to as algorithms, which find the local optimal within the hope of finding a global optimal solution.

We start with rock bottom weight from the sides and continue adding edges until we reach our goal.

The steps for implementing Kruskell's algorithm are as follows:

•  Sort all edges from low to high
•  Take the sting with the smallest amount weight and fasten it to the wide tree. If adding a foothold creates a cycle, discard this edge.
•  Continue adding edges until all vertices are reached.
  

Kruskel's Algorithm Pseudocode

The Minimum Spanning Tree Algorithm is employed to see whether adding a foothold creates a loop or not.

The most common thanks to find this is often with the algorithm UnionFind. 

The union-find algorithm divides the vertices into clusters and allows us to see whether the 2 vertices belong to an equivalent cluster, so determine whether adding a foothold creates a cycle.

Kruskel's Algorithm Pseudocode

Example of Kruskel's algorithm with solution

Step-01:

 Sort all the sides from low weight to high weight.

 
Step-02:

•  Take the sting with rock bottom weight and use it to attach the vertices of graph.
•  If adding a foothold creates a cycle, then reject that edge and choose subsequent least weight edge.

Step-03:

 Keep adding edges until all the vertices are connected and a Minimum Spanning Tree (MST) is obtained.

Minimum Spanning Tree Analysis-

•  the sides are maintained as min heap.
•  subsequent edge are often obtained in O(logE) time if graph has E edges.
•  Reconstruction of heap takes O(E) time.
•  So, Kruskal’s Algorithm takes O(ElogE) time.
•  the worth of E are often at the most O(V2).
•  So, O(logV) and O(logE) are same.

 
Special Case-

•  If the sides are already sorted, then there's no got to construct min heap.
•  So, deletion from min heap time is saved.
•  during this case, time complexity of Kruskal’s Algorithm = O(E + V) 

SOLVE PROBLEMS ON KRUSKAL’S ALGORITHM

SOLVE PROBLEMS

 Follow these steps to solve the problem

Steps to solve KRUSKAL’S ALGORITHM

 Now follow other two steps

Now follow other two steps

Step 5 and 6

Last Step 7

= 10 + 25 + 22 + 12 + 16 + 14

= 99 units

 Time Complexity for Kruskal’s Algorithm

Time Complexity for Kruskal’s Algorithm

C program for Kruskal’s Algorithm

#include <stdio.h>

#define MAX 30

typedef struct edge {
  int u, v, w;
} edge;

typedef struct edge_list {
  edge data[MAX];
  int n;
} edge_list;

edge_list elist;

int Graph[MAX][MAX], n;
edge_list spanlist;

void kruskalAlgo();
int find(int belongs[], int vertexno);
void applyUnion(int belongs[], int c1, int c2);
void sort();
void print();

// Applying Krushkal Algo
void kruskalAlgo() {
  int belongs[MAX], i, j, cno1, cno2;
  elist.n = 0;

  for (i = 1; i < n; i++)
    for (j = 0; j < i; j++) {
      if (Graph[i][j] != 0) {
        elist.data[elist.n].u = i;
        elist.data[elist.n].v = j;
        elist.data[elist.n].w = Graph[i][j];
        elist.n++;
      }
    }

  sort();

  for (i = 0; i < n; i++)
    belongs[i] = i;

  spanlist.n = 0;

  for (i = 0; i < elist.n; i++) {
    cno1 = find(belongs, elist.data[i].u);
    cno2 = find(belongs, elist.data[i].v);

    if (cno1 != cno2) {
      spanlist.data[spanlist.n] = elist.data[i];
      spanlist.n = spanlist.n + 1;
      applyUnion(belongs, cno1, cno2);
    }
  }
}

int find(int belongs[], int vertexno) {
  return (belongs[vertexno]);
}

void applyUnion(int belongs[], int c1, int c2) {
  int i;

  for (i = 0; i < n; i++)
    if (belongs[i] == c2)
      belongs[i] = c1;
}

// Sorting algo
void sort() {
  int i, j;
  edge temp;

  for (i = 1; i < elist.n; i++)
    for (j = 0; j < elist.n - 1; j++)
      if (elist.data[j].w > elist.data[j + 1].w) {
        temp = elist.data[j];
        elist.data[j] = elist.data[j + 1];
        elist.data[j + 1] = temp;
      }
}

// Printing the result
void print() {
  int i, cost = 0;

  for (i = 0; i < spanlist.n; i++) {
    printf("\n%d - %d : %d", spanlist.data[i].u, spanlist.data[i].v, spanlist.data[i].w);
    cost = cost + spanlist.data[i].w;
  }

  printf("\nSpanning tree cost: %d", cost);
}

int main() {
  int i, j, total_cost;

  n = 6;

  Graph[0][0] = 0;
  Graph[0][1] = 4;
  Graph[0][2] = 4;
  Graph[0][3] = 0;
  Graph[0][4] = 0;
  Graph[0][5] = 0;
  Graph[0][6] = 0;

  Graph[1][0] = 4;
  Graph[1][1] = 0;
  Graph[1][2] = 2;
  Graph[1][3] = 0;
  Graph[1][4] = 0;
  Graph[1][5] = 0;
  Graph[1][6] = 0;

  Graph[2][0] = 4;
  Graph[2][1] = 2;
  Graph[2][2] = 0;
  Graph[2][3] = 3;
  Graph[2][4] = 4;
  Graph[2][5] = 0;
  Graph[2][6] = 0;

  Graph[3][0] = 0;
  Graph[3][1] = 0;
  Graph[3][2] = 3;
  Graph[3][3] = 0;
  Graph[3][4] = 3;
  Graph[3][5] = 0;
  Graph[3][6] = 0;

  Graph[4][0] = 0;
  Graph[4][1] = 0;
  Graph[4][2] = 4;
  Graph[4][3] = 3;
  Graph[4][4] = 0;
  Graph[4][5] = 0;
  Graph[4][6] = 0;

  Graph[5][0] = 0;
  Graph[5][1] = 0;
  Graph[5][2] = 2;
  Graph[5][3] = 0;
  Graph[5][4] = 3;
  Graph[5][5] = 0;
  Graph[5][6] = 0;

  kruskalAlgo();
  print();
}

 introduction Of greedy algorithm with example

In an algorithm design, there's no band aid to all or any computational problems. Different problems require the utilization of various sorts of techniques. an honest programmer uses all of those techniques counting on the sort of problem. Some commonly used techniques are:

•  Divide and conquer
•  Random algorithms
•  Greedy algorithms (It's not an algorithm, it is a technique.)
•  Dynamic programming

Understand About “greedy algorithm”?

A greedy algorithm, because the name suggests, always makes the selection that seems to be the simplest at that point . this suggests that he makes a locally optimal choice within the hope that this choice will cause a globally optimal solution.

How does one decide which choice is optimal?

Suppose you've got an objective function that must be optimized (maximized or minimized) at some point. A Greedy algorithm makes greedy choices at every step to make sure that the target function is optimized. The Greedy algorithm only has one move to calculate the optimal solution in order that it never goes back and reverses the choice .

advantages and disadvantages for Greedy algorithms With Example:

•  It's pretty easy to seek out a Greedy algorithm (or even multiple greedy algorithms) for a drag .

•  time period analysis for greedy algorithms will generally be much easier than for other techniques (like Divide and conquer). For the Divide and Conquer technique, it's not clear whether the technique is fast or slow. Indeed, at each level of recursion, the dimensions of becomes smaller and therefore the number of sub-problems increases.

•  The hard part is that for greedy algorithms you've got to work tons harder to figure out the accuracy issues. Even with the proper algorithm, it's hard to prove why it's correct. Proving that a greedy algorithm is correct is more of an art than a science. It involves tons of creativity.

Note: Most of the greedy algorithms in DAA(data structure and algorithm) aren't correct. An example is described later during this article.

Greedy Algorithm Example

Greedy Algorithm Example

• First Make a empty set solution-set = { }.
  

• Coins 5,2,1
  

• sum = 0
  

• While sum ≠ 28, do the rest.
  

• Select a coin C from coins so that sum + C < 28.
  

• If C + sum > 28, return a empty solution.

• Else, sum = sum + C.

• Add C to solution-set.
  

Up to the primary 5 iterations, the answer set contains 5 $5 coins. then , we get 1 $2 coin and eventually , 1 $1 coin.

Where to use Greedy algorithms?

A problem must comprise these two components for a greedy algorithm to work:

 it's optimal substructures. The optimal solution for the matter contains optimal solutions to the sub-problems.

 it's a greedy property (hard to prove its correctness!). If you create a choice that seems the simplest at the instant and solve the remaining sub-problems later, you continue to reach an optimal solution. you'll never need to reconsider your earlier choices.
 

Heap Sorting Algorithm

The heap sort algorithm is a arrangement and therefore the heaps are arrays of binary trees. Each node of the binary tree corresponds to a component of the array. Since a node has zero, one or two child nodes, for the i-th element of the array, the 2-th and (2i + 1) -th elements are its left and right children respectively.

The following figure shows an example of a heap during which the numbers in nodes are adequate to the orders in an array of 12 elements. the basis is that the first element of the array, and its left and right children are the second and third elements, respectively. The sixth element has just one child left and therefore the seventh doesn't .

min heap

Heapsort Algorithm

The strategy is as follows; 

i) transform an array into a max heap; 

ii) choose the basis , which is that the maximum number; 

iii) keep the remaining array as a maximum heap; 

iv) recurse ii) and iii).

Here is that the code from step iii) which is additionally utilized in step i). This "Max-Heapify" function takes two inputs: an array and an integer. The function compares the node during a given order (input integer) with its two children. If the node is smaller than either of the youngsters , it's swapped with the larger of the 2 child nodes.
 

Heap sort Algorithm

Although Max-Heapify doesn't exhaust the whole heap, by running the function on all nodes except leaves (the end nodes of the heap), we will turn any array into a max heap.
 

Heap sort

We are now able to implement Heapsort.

Heap sort algorithm

The following figure explains how Heapsort treats an array of 12 elements; 

i) first, we turn the array into a max heap; 

ii) take the basis , 12, and replace it with the last element, 

3; iii) process Max-Heapify on the array of 11 elements remaining at the basis , and therefore the affected nodes are shown in dark blue; iii) recurse ii) and iii). within the end, we'll get an array sorted in ascending order. Heapsort works in situ , only storing a continuing amount of knowledge outside of the input array.

solution for Heap sort algorithm

heap sort time complexity

We can analyze the value of Heapsort by watching the sub-functions of Max-Heapify and Build-Max-Heap.

The cost of Max-Heapify is O (lgn). Comparing a node and its two child nodes costs Θ (1), and within the worst case, we rewind ⌊log₂n⌋ times down. Alternatively, the value of Max-Heapify are often expressed because the height h of the heap O (h).

heap sort time complexity

Check Performance For heap sort algorithm

The following table describes different sorting algorithms. needless to say , Heap sort algorithm follows other O (nlgn) cost algorithms, while it's not as cheap as Quicksort with a better constant hidden within the O notation.