Scribd
Upload
49 views

Kruskal's Algorithm

It has notes of Kruskal's algo

Uploaded by

Suhani Rana
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
49 views

Kruskal's Algorithm

It has notes of Kruskal's algo

Uploaded by

Suhani Rana
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 6

KRUSKAL'S MINIMUM SPANNING TREE

ALGORITHM
 Kruskal’s algorithm creates a minimum spanning tree from a weighted undirected
graph by adding edges in increasing order of weights.
 Kruskal’s algorithm is greedy in nature as the edges are chosen in the increasing order
of their weights.
 The algorithm makes sure that the addition of new edges to the spanning tree does not
create a cycle within it.
 A union-by-rank & path compression technique used for merging two disjoint subsets
could be used to efficiently add edges to the minimum spanning tree.

Algorithm : Kruskal’s minimum spanning tree ( Graph G )

0. Create an empty minimum spanning tree M i.e M = ∅ (zero edges)


1. Sort the edge-list of the graph G in ascending order of weights.
2. For each edge ( A, B ) in the sorted edge-list.
3. If Find_Set_Of_A != Find_Set_Of_B, then
4. Add edge A-B to the minimum spanning tree M i.e M = M + edge ( A - B )
5. Make a set / union of Find_Set_Of_A + Find_Set_Of_B.

Example of finding the minimum spanning tree using Kruskal’s algorithm


Time complexity of Kruskal’s algorithm : O ( E log ( E ) ) or O ( E log ( V )). Where E is the
number of edges and V is the number of vertices.

Why is the time complexity of Kruskal's algorithm O ( E log ( E ) ) or O ( E log ( V ) ) ?

Kruskal’s minimum spanning tree implementation

PythonC++Java
import java.util.ArrayList;
import java.util.List;

class Edge {

int node_start;
int node_end;
int weight;
Edge (int node1, int node2, int wt) {
node_start = node1;
node_end = node2;
weight = wt;
}

public int GetWeight() {


return weight;
}
};

class Graph {

private int num_nodes;


private List<Edge> edgelist = new ArrayList<Edge>(); // Edgelist
stores the edges of MST
private List<Integer> parent;
private List<Integer> rank;

Graph (int num_nodes) {


this.num_nodes = num_nodes;
parent = new ArrayList<Integer>(num_nodes);
rank = new ArrayList<Integer>(num_nodes);
}

public void AddEdge (Edge e) {


edgelist.add(e);
}

public int FindParent (int node) {

// With path compression


if ( node != parent.get(node) )
parent.set(node, FindParent(parent.get(node)));

return parent.get(node);

/* Without path compression


if ( node == parent.get(node) )
return node;

return FindParent(parent.get(node)); */
}

//Funtion implements Kruskal's algorithm and finds the minimum


spanning tree.
public void KruskalMST (List<Edge> result) {

for (int i=0; i<num_nodes; i++) {


parent.add(i, i); // Initially set every node as the parent
of itself.
rank.add(i, 0); // Initial rank of each node is 0.
}

// Lambda expression to sort the edges based on their weights


edgelist.sort((Edge e1, Edge e2)->e1.GetWeight()-e2.GetWeight());

for (Edge e : edgelist) {

int root1 = FindParent(e.node_start);


int root2 = FindParent(e.node_end);
// Union by rank technique to find minimum spanning tree.
if (root1 != root2) {
result.add(e);
if (rank.get(root1) < rank.get(root2)) {
parent.set(root1, root2);
rank.set(root2, rank.get(root2) + 1);
} else {
parent.set(root2, root1);
rank.set(root1, rank.get(root1) + 1);
}
}
}
}

public void DisplayEdges(List<Edge> result) {


int cost = 0;
System.out.print( "\nEdges of minimum spanning tree : ");

for (Edge edge : result) {


System.out.print( "[" + edge.node_start + "-" + edge.node_end
+ "]- (" + edge.weight + ") ");
cost += edge.weight;
}
System.out.println("\nCost of minimum spanning tree : " + cost);
}

public static void main (String args[]) {

int num_nodes = 6; // Nodes (0, 1, 2, 3, 4, 5)

// Edge (source, dest, weight);


Edge e1 = new Edge(0, 1, 4);
Edge e2 = new Edge(0, 2, 1);
Edge e3 = new Edge(0, 3, 5);
Edge e4 = new Edge(1, 3, 2);
Edge e5 = new Edge(1, 4, 3);
Edge e6 = new Edge(1, 5, 3);
Edge e7 = new Edge(2, 3, 2);
Edge e8 = new Edge(2, 4, 8);
Edge e9 = new Edge(3, 4, 1);
Edge e10 = new Edge(4, 5, 3);

Graph g1 = new Graph(num_nodes);

g1.AddEdge(e1);
g1.AddEdge(e2);
g1.AddEdge(e3);
g1.AddEdge(e4);
g1.AddEdge(e5);
g1.AddEdge(e6);
g1.AddEdge(e7);
g1.AddEdge(e8);
g1.AddEdge(e9);
g1.AddEdge(e10);

List<Edge> mst = new ArrayList<Edge>();


g1.KruskalMST(mst);
g1.DisplayEdges(mst);

num_nodes = 7;

Edge a = new Edge(0, 1, 1);


Edge b = new Edge(0, 2, 2);
Edge c = new Edge(0, 3, 1);
Edge d = new Edge(0, 4, 1);
Edge e = new Edge(0, 5, 2);
Edge f = new Edge(0, 6, 1);
Edge g = new Edge(1, 2, 2);
Edge h = new Edge(1, 6, 2);
Edge i = new Edge(2, 3, 1);
Edge j = new Edge(3, 4, 2);
Edge k = new Edge(4, 5, 2);
Edge l = new Edge(5, 6, 1);

Graph g2 = new Graph(num_nodes);


g2.AddEdge(a);
g2.AddEdge(b);
g2.AddEdge(c);
g2.AddEdge(d);
g2.AddEdge(e);
g2.AddEdge(f);
g2.AddEdge(g);
g2.AddEdge(h);
g2.AddEdge(i);
g2.AddEdge(j);
g2.AddEdge(k);
g2.AddEdge(l);

mst.clear();
g2.KruskalMST(mst);
g2.DisplayEdges(mst);
}
}

Output

Edges of minimum spanning tree : [0-2]-(1) [3-4]-(1) [1-3]-(2) [2-3]-(2)


[1-5]-(3)
Cost of minimum spanning tree : 9

Edges of minimum spanning tree : [0-1]-(1) [0-3]-(1) [0-4]-(1) [0-6]-(1)


[2-3]-(1) [5-6]-(1)
Cost of minimum spanning tree : 6

You might also like