Java Stream API : Implementing Prim's Algorithm

Implementing Prim's Algorithm to Find Minimum Spanning Tree Using Java Stream API

Introduction

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. It starts with an arbitrary node and grows the spanning tree by adding the cheapest edge that connects the tree to a new node. This process is repeated until all nodes are included in the tree. In this blog post, we will implement Prim's algorithm using Java's Stream API, which provides a functional approach to processing collections.

Java Stream API : Implementing Prim's Algorithm

Understanding Prim's Algorithm

Before we dive into the implementation, let's briefly review the steps involved in Prim's algorithm:

1. Choose an arbitrary node as the starting point.

2. Initialize a priority queue to store the edges, with the key being the weight of the edge.

3. While there are still nodes left to be included in the tree:

   a. Find the edge with the minimum weight that connects a node in the tree to a node outside the tree.

   b. Add this edge to the tree.

   c. Mark the newly added node as included in the tree.

---

advertisement

---

Implementing Prim's Algorithm

To implement Prim's algorithm, we will represent the graph as a list of edges, where each edge is a tuple containing the source node, the destination node, and the weight of the edge. We will use a Set to keep track of the nodes included in the tree and a PriorityQueue to store the edges sorted by weight.

import java.util.*;

import java.util.stream.*;

class Edge {

    int src, dest, weight;

    Edge(int src, int dest, int weight) {

        this.src = src;

        this.dest = dest;

        this.weight = weight;

    }

}

public class PrimAlgorithm {

    public static List<Edge> primMST(List<Edge> edges, int numVertices) {

        Set<Integer> visited = new HashSet<>();

        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));

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

        // Start from the first node

        int startNode = 0;

        visited.add(startNode);

        // Add all edges from the starting node to the priority queue

        pq.addAll(edges.stream()

                       .filter(e -> e.src == startNode || e.dest == startNode)

                       .collect(Collectors.toList()));

        while (!pq.isEmpty() && visited.size() < numVertices) {

            Edge minEdge = pq.poll();

            int nextNode = visited.contains(minEdge.src) ? minEdge.dest : minEdge.src;

            if (!visited.contains(nextNode)) {

                visited.add(nextNode);

                mst.add(minEdge);

                pq.addAll(edges.stream()

                               .filter(e -> e.src == nextNode || e.dest == nextNode)

                               .collect(Collectors.toList()));

            }

        }

        return mst;

    }

    public static void main(String[] args) {

        List<Edge> edges = Arrays.asList(

                new Edge(0, 1, 2),

                new Edge(0, 2, 3),

                new Edge(1, 2, 1),

                new Edge(1, 3, 4),

                new Edge(2, 4, 5),

                new Edge(3, 4, 6)

        );

        List<Edge> mst = primMST(edges, 5);

        System.out.println("Minimum Spanning Tree:");

        for (Edge edge : mst) {

            System.out.println(edge.src + " - " + edge.dest + ": " + edge.weight);

        }

    }

}

In this implementation, we start from the first node and repeatedly add the minimum weight edge connecting a node in the tree to a node outside the tree until all nodes are included in the tree. The PriorityQueue ensures that we always select the minimum weight edge efficiently.

---

advertisement

---

Conclusion

In this blog post, we have implemented Prim's algorithm to find the minimum spanning tree of a graph using Java's Stream API. Prim's algorithm is a fundamental algorithm in graph theory and finding its implementation using a functional approach can be beneficial for understanding both the algorithm and the Stream API.