Basic Code Snippet for "Prim's Minimum Spanning Tree Algorithm" in java.
Mihir_Mehta
717
Graph TheoryMinimum Spanning TreeInterview

Problem statement -

  1. Given an array of points where points[i] = {x[i],y[i]}.
  2. Cost of connecting two points {x[i],y[i]} and {x[j],y[j]} is |x[i] - x[j]| + |y[i] - y[j]|.
  3. Calculate the minimum cost to connect all points.
  4. All points are connected if there is exactly one simple path between any two points.

One of the possible solutions here is "Prim's Minimum Spanning Tree Algorithm".
ref:

A Minimum Spanning Tree (MST) is a tree in a weighted undirected graph that connects all the vertices with minimum total weight. In other words, it is a subset of edges that forms a tree and connects all the vertices in the graph such that the sum of the edge weights is minimized.

class Solution {

public int minCostConnectPoints(int[][] points) {
    // Prim Algorithm
    if (points == null || points.length == 0) {
        return 0;
    }
    int size = points.length;
    PriorityQueue<Edge> pq = new PriorityQueue<>((x, y) -> x.cost - y.cost);
    boolean[] visited = new boolean[size];
    int result = 0;
    int count = size - 1;
    // Add all edges from points[0] vertex
    int[] coordinate1 = points[0];
    for (int j = 1; j < size; j++) {
        // Calculate the distance between two coordinates.
        int[] coordinate2 = points[j];
        int cost = Math.abs(coordinate1[0] - coordinate2[0]) + 
                   Math.abs(coordinate1[1] - coordinate2[1]);
        Edge edge = new Edge(0, j, cost);
        pq.add(edge);
    }
    visited[0] = true;

    while (!pq.isEmpty() && count > 0) {
        Edge edge = pq.poll();
        int point1 = edge.point1;
        int point2 = edge.point2;
        int cost = edge.cost;
        if (!visited[point2]) {
            result += cost;
            visited[point2] = true;
            for (int j = 0; j < size; j++) {
                if (!visited[j]) {
                    int distance = Math.abs(points[point2][0] - points[j][0]) + 
                                   Math.abs(points[point2][1] - points[j][1]);
                    pq.add(new Edge(point2, j, distance));
                }
            }
            count--;
        }
    }
    return result;
}

class Edge {
    int point1;
    int point2;
    int cost;

    Edge(int point1, int point2, int cost) {
        this.point1 = point1;
        this.point2 = point2;
        this.cost = cost;
    }
}

}

Comments (0)