Hire Our Expert Programmer & Technical Writer to do your Capstone Project
+1 vote
708 views
in Programming Languages & Algorithms by

1 Answer

+1 vote
by
selected by (user.guest)
 
Best answer
Kruskal's Algorithm

Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph. The main target of the algorithm is to find the subset of edges by using which, we can traverse every vertex of the graph. Kruskal's algorithm follows greedy approach which finds an optimum solution at every stage instead of focusing on a global optimum.

The Kruskal's algorithm is given as follows.

Algorithm

Step 1: Create a forest in such a way that each graph is a separate tree.

Step 2: Create a priority queue Q that contains all the edges of the graph.

Step 3: Repeat Steps 4 and 5 while Q is NOT EMPTY

Step 4: Remove an edge from Q

Step 5: IF the edge obtained in Step 4 connects two different trees, then Add it to the forest (for combining two trees into one tree).

ELSE

Discard the edge

Step 6: END

Applications where Kruskal's algorithm is generally used:-

*Landing cables

*TV Network

*Tour Operations

*LAN Networks

*A network of pipes for drinking water or natural gas.

*An electric grid

*Single-link Cluster.......

// Kruskal's algorithm in High level language for example JAVA :-

import java.util.*;

class Graph {

  class Edge implements Comparable<Edge> {

    int src, dest, weight;

    public int compareTo(Edge compareEdge) {

      return this.weight - compareEdge.weight;

    }

  };

  // Union

  class subset {

    int parent, rank;

  };

  int vertices, edges;

  Edge edge[];

  // Graph creation

  Graph(int v, int e) {

    vertices = v;

    edges = e;

    edge = new Edge[edges];

    for (int i = 0; i < e; ++i)

      edge[i] = new Edge();

  }

  int find(subset subsets[], int i) {

    if (subsets[i].parent != i)

      subsets[i].parent = find(subsets, subsets[i].parent);

    return subsets[i].parent;

  }

  void Union(subset subsets[], int x, int y) {

    int xroot = find(subsets, x);

    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)

      subsets[xroot].parent = yroot;

    else if (subsets[xroot].rank > subsets[yroot].rank)

      subsets[yroot].parent = xroot;

    else {

      subsets[yroot].parent = xroot;

      subsets[xroot].rank++;

    }

  }

  // Applying Krushkal Algorithm

  void KruskalAlgo() {

    Edge result[] = new Edge[vertices];

    int e = 0;

    int i = 0;

    for (i = 0; i < vertices; ++i)

      result[i] = new Edge();

    // Sorting the edges

    Arrays.sort(edge);

    subset subsets[] = new subset[vertices];

    for (i = 0; i < vertices; ++i)

      subsets[i] = new subset();

    for (int v = 0; v < vertices; ++v) {

      subsets[v].parent = v;

      subsets[v].rank = 0;

    }

    i = 0;

    while (e < vertices - 1) {

      Edge next_edge = new Edge();

      next_edge = edge[i++];

      int x = find(subsets, next_edge.src);

      int y = find(subsets, next_edge.dest);

      if (x != y) {

        result[e++] = next_edge;

        Union(subsets, x, y);

      }

    }

    for (i = 0; i < e; ++i)

      System.out.println(result[i].src + " - " + result[i].dest + ": " + result[i].weight);

  }

  public static void main(String[] args) {

    int vertices = 6; // Number of vertices

    int edges = 8; // Number of edges

    Graph G = new Graph(vertices, edges);

    G.edge[0].src = 0;

    G.edge[0].dest = 1;

    G.edge[0].weight = 4;

    G.edge[1].src = 0;

    G.edge[1].dest = 2;

    G.edge[1].weight = 4;

    G.edge[2].src = 1;

    G.edge[2].dest = 2;

    G.edge[2].weight = 2;

    G.edge[3].src = 2;

    G.edge[3].dest = 3;

    G.edge[3].weight = 3;

    G.edge[4].src = 2;

    G.edge[4].dest = 5;

    G.edge[4].weight = 2;

    G.edge[5].src = 2;

    G.edge[5].dest = 4;

    G.edge[5].weight = 4;

    G.edge[6].src = 3;

    G.edge[6].dest = 4;

    G.edge[6].weight = 3;

    G.edge[7].src = 5;

    G.edge[7].dest = 4;

    G.edge[7].weight = 3;

    G.KruskalAlgo();

  }

}

Related questions

+1 vote
1 answer 847 views
Welcome to CPENTalk.com

Disclaimer: Every user is solely responsible for anything that he/she posts or uploads on CPENTalk.
...