Connecting Cities With Minimum Cost
Understanding the Problem
This is a Minimum Spanning Tree (MST) problem. We have n cities (nodes) and a list of possible connections (weighted edges). We need the cheapest set of edges that joins all cities into a single connected component. If the graph is disconnected, no such set exists and we return -1.
A spanning tree of n nodes always has exactly n-1 edges, so the task reduces to picking n-1 edges from the available connections that connect every city at minimum total cost.
Two standard algorithms solve this: Kruskal's (sort all edges, greedily add the cheapest edge that does not form a cycle) and Prim's (grow a tree from a starting node, always adding the cheapest edge that reaches a new node). Kruskal's uses Union-Find to detect cycles; Prim's uses a priority queue to track frontier edges. Both run in O(E log E).
Key Constraints:
1 <= n <= 10^4and1 <= connections.length <= 10^4→ With up to 10,000 nodes and 10,000 edges, both O(E log E) MST algorithms finish in well under a million operations. A quadratic approach would approach 10^8 operations, which is borderline at best.0 <= costi <= 10^5→ An MST uses at most n-1 = 9,999 edges of cost at most 10^5, so the answer never exceeds about 10^9. That fits in a 32-bit signed integer, so a plainintworks for the running total.
Approach 1: Kruskal's Algorithm (Union-Find)
Intuition
Kruskal's algorithm sorts all edges by cost, then processes them from cheapest to most expensive. For each edge, if it connects two cities that are not already in the same component, add it to the MST. If they are already connected, skip it because adding it would create a cycle.
This greedy choice is safe because of the cut property: for any partition of the cities into two groups, the cheapest edge crossing the partition belongs to some MST. The cheapest unprocessed edge whose endpoints sit in different components is always such a crossing edge, so taking it never blocks an optimal solution.
The remaining work is checking efficiently whether two cities are already connected. Union-Find (also called Disjoint Set Union) maintains a collection of disjoint sets and supports two operations: find (which set does this element belong to?) and union (merge two sets). With path compression and union by rank, both run in nearly O(1) amortized time. Once n-1 edges have been added, the tree is complete and the remaining edges can be ignored.
Algorithm
- Sort all connections by cost in ascending order.
- Initialize a Union-Find structure with n components.
- Initialize
totalCost = 0andedgesUsed = 0. - For each connection
[city1, city2, cost]in sorted order: - If
city1andcity2are in different components (find returns different roots), union them, addcosttototalCost, and incrementedgesUsed. - If they're already in the same component, skip this edge.
- If
edgesUsed == n - 1, returntotalCost. Otherwise, return-1(not all cities can be connected).
Visualization and Code
Loading animation...
- Time Complexity: O(E log E). Sorting the edges takes O(E log E). Processing each edge with Union-Find takes nearly O(1) amortized (inverse Ackermann function), so the sort dominates.
- Space Complexity: O(N). The Union-Find structure uses O(N) space for the parent and rank arrays.
Kruskal's sorts every edge upfront even though the final tree uses only n-1 of them. The next approach grows the tree outward from a single city and orders only the frontier edges with a heap, replacing the global sort.
Approach 2: Prim's Algorithm (Priority Queue)
Intuition
Prim's algorithm grows the MST one node at a time instead of sorting all edges globally. Start from any city, add it to the tree, and push all its edges into a priority queue (min-heap). Then repeatedly extract the cheapest edge from the heap. If the edge reaches an unvisited city, add that city to the tree and push its edges. If the city was already visited, discard the edge.
The traversal resembles BFS, except the next node is chosen by edge cost rather than by hop distance.
At any point in the algorithm, the cut separating visited cities from unvisited cities determines the next edge: by the cut property, the cheapest edge crossing this cut belongs to some MST. The heap can hold stale entries whose destination was visited after they were pushed, but the visited check discards those, so the first pop that survives the check is the cheapest crossing edge. Every accepted edge is therefore part of an optimal solution, and since each one brings in exactly one new city, the tree is complete after n-1 acceptances.
Algorithm
- Build an adjacency list from the connections array.
- Initialize a min-heap (priority queue) and a visited set.
- Start from city 1. Mark it as visited. Push all its edges into the heap.
- While the heap is not empty and we haven't visited all cities:
- Extract the edge with the minimum cost.
- If the destination city is already visited, skip it.
- Otherwise, mark it as visited, add the cost to
totalCost, and push all its unvisited neighbor edges into the heap. - If all n cities are visited, return
totalCost. Otherwise return-1.
Visualization and Code
Loading animation...
- Time Complexity: O(E log E). Building the adjacency list is O(E). Each edge can be pushed and popped from the heap at most once, and each heap operation is O(log E). So the total is O(E log E).
- Space Complexity: O(N + E). The adjacency list takes O(N + E) space. The heap can hold up to O(E) edges. The visited array takes O(N).