Computer scienceProgramming languagesJavaInterview preparationAlgorithms and problem solving techniques

Minimum spanning tree problem - Prim and Kruskal algorithms

Theory

Prepare edges

Report a typo

Kruskal's algorithm uses separate edges to build MST.
Kruskal's approach has significant differences from Prim's approach.

Implement the method getPreparedEdges() that represents the initial step of Kruskal's algorithm.

As input, you get a list of edges.

Sample Input 1: 

0 - 1 (2)
0 - 3 (3)
0 - 2 (4)
1 - 3 (1)
2 - 3 (3)

Sample Output 1: 

1 - 3 (1)
0 - 1 (2)
2 - 3 (3)
Write a program in Java 17
import java.util.*;

class Helper {
// Implement method that prepares edges according to Kruskal's algorithm
static List<Edge> getPreparedEdges(List<Edge> edges) {
// Write your code here

return edges;
}
}

// !!! Do not modify the code below !!!
class Edge {
int source;
int destination;
int weight;

public Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}
___

Create a free account to access the full topic