Java Stream API : Implementing Kruskal's Algorithm

0

Implementing Kruskal's Algorithm Using Java Stream API for Minimum Spanning Tree


Kruskal's algorithm is a popular method used to find the minimum spanning tree (MST) of a connected, undirected graph. The algorithm works by selecting edges in ascending order of their weights while ensuring that adding the edge to the MST does not create a cycle. In this blog post, we will explore how to implement Kruskal's algorithm using Java Stream API.

Implementing Kruskal's Algorithm Using Java Stream API for Minimum Spanning Tree
Java Stream API : Implementing Kruskal's Algorithm

Understanding Kruskal's Algorithm

Before diving into the implementation, let's briefly discuss the steps involved in Kruskal's algorithm:

1. Sort Edges: Sort all the edges in the graph in non-decreasing order of their weights.
2. Initialize MST: Create an empty set to store the edges of the MST.
3. Iterate Through Edges: Iterate through all the edges in the sorted order. For each edge:
   - If adding the edge to the MST does not create a cycle, add it to the MST.
   - Otherwise, discard the edge.
4. Output MST: The set of edges added to the MST forms the minimum spanning tree.

advertisement

Implementation Using Java Stream API

To implement Kruskal's algorithm using Java Stream API, we need to follow these steps:

1. Define a class to represent an edge in the graph, including the source, destination, and weight.
2. Create a method to sort the edges based on their weights.
3. Implement a method to find the parent of a vertex in a disjoint set.
4. Implement the main algorithm using Java Stream API.

Let's start by defining the Edge class:

class Edge {
    int source, destination, weight;

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

Next, let's create a method to sort the edges based on their weights:

private static List<Edge> sortEdges(List<Edge> edges) {
    return edges.stream()
            .sorted(Comparator.comparingInt(e -> e.weight))
            .collect(Collectors.toList());
}

Now, we need to implement a method to find the parent of a vertex in a disjoint set. This method is crucial for detecting cycles in the graph:

private static int findParent(int[] parent, int vertex) {
    if (parent[vertex] == -1)
        return vertex;
    return findParent(parent, parent[vertex]);
}


Finally, we can implement the main algorithm using Java Stream API:

public static List<Edge> kruskalMST(List<Edge> edges, int vertices) {
    List<Edge> result = new ArrayList<>();
    List<Edge> sortedEdges = sortEdges(edges);
    int[] parent = new int[vertices];
    Arrays.fill(parent, -1);
    
    sortedEdges.stream().forEach(edge -> {
        int x = findParent(parent, edge.source);
        int y = findParent(parent, edge.destination);

        if (x != y) {
            result.add(edge);
            parent[x] = y;
        }
    });

    return result;
}


Usage Example

Here's an example of how you can use the kruskalMST method to find the minimum spanning tree of a graph:

public static void main(String[] args) {
    List<Edge> edges = Arrays.asList(
            new Edge(0, 1, 10),
            new Edge(0, 2, 6),
            new Edge(0, 3, 5),
            new Edge(1, 3, 15),
            new Edge(2, 3, 4)
    );
    
    List<Edge> mst = kruskalMST(edges, 4);
    
    System.out.println("Minimum Spanning Tree:");
    mst.forEach(edge -> System.out.println(edge.source + " - " + edge.destination + ": " + edge.weight));
}


advertisement

Conclusion

In this blog post, we have discussed how to implement Kruskal's algorithm using Java Stream API to find the minimum spanning tree of a graph. Java Stream API provides a concise and readable way to work with collections, making it a suitable choice for implementing algorithms like Kruskal's algorithm.
Tags:

Post a Comment

Previous Post Next Post