ONLINE SUMMER TRAINING Online Courses Free Tutorials 
 Placement Preparation 
Artificial Intelligence(AI) & Machine Learning(ML) Training in Jaipur
0 like 0 dislike
206 views
in VTU B.Tech (CSE-IV Sem) Design and Analysis of Algorithm Lab by Goeduhub's Expert (5.8k points)

Find Minimum Cost Spanning Tree of a given connected undirected graph using Kruskal'salgorithm. Use Union-Find algorithms in your program

Goeduhub's Online Courses @Udemy

For Indian Students- INR 570/- || For International Students- $12.99/-

S.No.

Course Name

Apply Coupon

1.

Tensorflow 2 & Keras:Deep Learning & Artificial Intelligence

Apply Coupon

2.

Computer Vision with OpenCV | Deep Learning CNN Projects

Apply Coupon

3.

Complete Machine Learning & Data Science with Python Apply Coupon

4.

Natural Language Processing-NLP with Deep Learning in Python Apply Coupon

5.

Computer Vision OpenCV Python | YOLO| Deep Learning in Colab Apply Coupon

6.

Complete Python Programming from scratch with Projects Apply Coupon

1 Answer

0 like 0 dislike
by Goeduhub's Expert (5.8k points)
 
Best answer

For Theory of Kruskal's Algorithm Click here

Java Program

import java.util.*; 

import java.lang.*; 

import java.io.*; 

class Kruk 

// A class to represent a graph edge 

class Edge implements Comparable<Edge> 

int src, dest, weight; 

public int compareTo(Edge compareEdge) 

return this.weight-compareEdge.weight; 

}; 

// A class to represent a subset for union-find 

class subset 

int parent, rank; 

}; 

int V, E; // V-> no. of vertices & E->no.of edges 

Edge edge[]; // collection of all edges 

// Creates a graph with V vertices and E edges 

Kruk(int v, int e) 

V = v; 

E = e; 

edge = new Edge[E]; 

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

edge[i] = new Edge(); 

// A utility function to find set of an element i 

int find(subset subsets[], int i) 

// find root and make root as parent of i (path compression) 

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

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

return subsets[i].parent; 

// A function that does union of two sets of x and y 

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

int xroot = find(subsets, x); 

int yroot = find(subsets, y); 

// Attach smaller rank tree under root of high rank tree  

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

subsets[xroot].parent = yroot; 

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

subsets[yroot].parent = xroot; 

// If ranks are same, then make one as root and increment its rank by one 

else

subsets[yroot].parent = xroot; 

subsets[xroot].rank++; 

    void KruskalMST() 

Edge result[] = new Edge[V]; // Tnis will store the resultant MST 

int e = 0; // An index variable, used for result[] 

int i = 0; // An index variable, used for sorted edges 

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

result[i] = new Edge(); 

Arrays.sort(edge); 

// Allocate memory for creating V subsets 

subset subsets[] = new subset[V]; 

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

subsets[i]=new subset(); 

// Create V subsets with single elements 

for (int v = 0; v < V; ++v) 

subsets[v].parent = v; 

subsets[v].rank = 0; 

i = 0; // Index used to pick next edge 

// Number of edges to be taken is equal to V-1 

while (e < V - 1) 

// Step 2: Pick the smallest edge. And increment 

// the index for next iteration 

Edge next_edge = new Edge(); 

next_edge = edge[i++]; 

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

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

// If including this edge does't cause cycle, 

// include it in result and increment the index 

// of result for next edge 

if (x != y) 

result[e++] = next_edge; 

Union(subsets, x, y); 

// Else discard the next_edge 

// print the contents of result[] to display 

// the built MST 

System.out.println("Edges of the constructed MST:"); 

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 V = 4; // Number of vertices in graph 

int E = 5; // Number of edges in graph 

Kruk graph = new Kruk(V, E); 

// add edge 0-1 

graph.edge[0].src = 0; 

graph.edge[0].dest = 1; 

graph.edge[0].weight = 10; 

// add edge 0-2 

graph.edge[1].src = 0; 

graph.edge[1].dest = 2; 

graph.edge[1].weight = 6; 

// add edge 0-3 

graph.edge[2].src = 0; 

graph.edge[2].dest = 3; 

graph.edge[2].weight = 5; 

// add edge 1-3 

graph.edge[3].src = 1; 

graph.edge[3].dest = 3; 

graph.edge[3].weight = 15; 

// add edge 2-3 

graph.edge[4].src = 2; 

graph.edge[4].dest = 3; 

graph.edge[4].weight = 4; 

graph.KruskalMST(); 

Output

Output


For more VTU IV Sem DAA Lab Experiments Click here


Our Mentors(For AI-ML)


Sharda Godara Chaudhary

Mrs. Sharda Godara Chaudhary

An alumna of MNIT-Jaipur and ACCENTURE, Pune

NISHA (IIT BHU)

Ms. Nisha

An alumna of IIT-BHU

Related questions

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 
...