1135. Connecting Cities With Minimum Cost

/**

 * 1135. Connecting Cities With Minimum Cost

 *

 * There are N cities numbered from 1 to N.

 *

 * You are given connections, where each connections[i] = [city1, city2, cost] represents the cost to connect city1 and city2 together.  (A connection is bidirectional: connecting city1 and city2 is the same as connecting city2 and city1.)

 *

 * Return the minimum cost so that for every pair of cities, there exists a path of connections (possibly of length 1)

 * that connects those two cities together.  The cost is the sum of the connection costs used.

 * If the task is impossible, return -1.

 *

 * Example 1:

 * Input: N = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]

 * Output: 6

 * Explanation:

 * Choosing any 2 edges will connect all cities so we choose the minimum 2.

 * the problem uses min spanning trees (union find) to connect the cities (vertices) together while traversing the path

 * using edges with minimum cost.

*/

See the code on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/graph/ConnectCitiesWithMinCost.java

Here is the code on union-find:

https://github.com/zcoderz/leetcode/blob/main/src/main/java/utils/graph/UnionFind.java

Observations: Connecting data points with minimum edge cost is a minimum spanning tree problem and can be solved via disjoint sets – union-find. See more about minimum spanning tree here: https://en.wikipedia.org/wiki/Minimum_spanning_tree.

Logic:

  1. Sort edges by the cost
  2. Work on the edges from lowest to highest cost until all edges or vertices are processed
    1. For source and destination per edge
    1. Find parent nodes
    1. Union the two parents found in b while incrementing the costs
  3. If all vertices have been processed return cost
  4. Else return -1

Here is the code to construct min spanning tree:

public static int constructMinSpanningTree(Vertex[] vertices, Edge[] edges) {
    int cost = 0;
    //sort the edges by the cost
    Arrays.sort(edges, Comparator.comparingInt(Edge::getCost));
    int numVertices = vertices.length;
    int seenVertices = 0;
    //break when either all edges are exhausted or when all vertices have been joined
    for (int i = 0; i < edges.length && seenVertices < (numVertices - 1); i++) {
        int x = find(vertices, edges[i].getSrc());
        int y = find(vertices, edges[i].getDest());
        //if the two vertices belong to diff parents then union them together
        if (x != y) {
            union(vertices, x, y);
            cost += edges[i].getCost();
            seenVertices++;
        }
    }
    if (seenVertices == numVertices - 1) {
        return cost;
    } else {
        return -1;
    }
}

Here is the code for finding the parent of any vertex

public static int find(Vertex[] vertices, int i) {
    if (vertices[i].getParent() != i) {
        //compact the parent path so that next call to parent doesnt have to recuse as deep
        vertices[i].setParent(find(vertices, vertices[i].getParent()));
    }
    return vertices[i].getParent();
}

Here is the code for merging (union) of two vertices

public static void union(Vertex[] vertices, int x, int y) {
    int xRank = vertices[find(vertices, x)].getRank();
    int yRank = vertices[find(vertices, y)].getRank();

    if (xRank > yRank) {
        vertices[y].setParent(x);
    } else if (yRank > xRank) {
        vertices[x].setParent(y);
    } else {
        vertices[x].setParent(y);
        //rank increases only when two vertices of same rank are merged together.
        vertices[y].setRank(vertices[y].getRank() + 1);
    }
}