Computer scienceProgramming languagesJavaInterview preparationAlgorithms and problem solving techniques

Minimum spanning tree problem - Prim and Kruskal algorithms

Theory

Kruskal's approach

Report a typo

A junior developer decided to implement Kruksal's approach to solve MST problem. The developer wrote almost all code except the one line. Help the developer finish the implementation.

You should write down only one code line in the method getKruskalMST() in Graph class.

Here is an image of the graph:

an image of graph

Go through the code accurately, read comments to understand the implementation, and think what is one significant action that wasn't written.

What should we do if the current edge does not create a cycle, according to Kruskal's algorithm?

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 Graph {
public static List<Edge> getKruskalMST(List<Edge> edges, int numNodes) {
// Create a disjoint "parentNodes" set to keep track of connected components
int[] parentNodes = new int[numNodes];
for (int i = 0; i < numNodes; i++) {
// Initialize each node is a parent of its own
parentNodes[i] = i;
}

edges.sort(Comparator.comparingInt(e -> e.weight));

// Initialize a list with edges, that create MST
List<Edge> mstEdges = new ArrayList<>();

for (Edge edge : edges) {
// Search the parent of the source and destination node of the edge
int sourceParentNode = findParentNode(edge.source, parentNodes);
int destinationParentNode = findParentNode(edge.destination, parentNodes);

if (sourceParentNode != destinationParentNode) {
// !!! Do not modify the code above !!!

// Write one line of code here

// !!! Do not modify the code below !!!

// Merge two nodes to one tree
// Set the parent of the first node to the parent of the second node
// On each step we move our tree main parent node
parentNodes[sourceParentNode] = destinationParentNode;
}
}

return mstEdges;
___

Create a free account to access the full topic