Solution: Connecting Cities With Minimum Cost

Grokking Graph Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Connecting Cities With Minimum Cost

Table of Contents

Contents are not accessible

Problem Statement

You have n cities labeled from 1 to n. You are given an integer n and a list of connections where each connection is represented as [xi, yi, costi]. This means that there is a bidirectional road between city xi and city yi with a cost of costi.

Return the minimum cost to connect all the cities so that there is a path between any two cities. If it's not possible to connect all cities, return -1. The total cost is the sum of the costs of the connections used.

Examples

Example 1:
- Input: n = 5, connections = [[1, 2, 2], [1, 3, 3], [4, 5, 1], [3, 4, 4], [2, 5, 6]]
- Expected Output: 10

Explanation: The minimum cost to connect all cities is obtained by using the connections [1, 2, 2], [1, 3, 3], [4, 5, 1], and [3, 4, 4]. This gives a total cost of 2 + 3 + 1 + 4 = 10.

Example 2:
- Input: n = 4, connections = [[1, 2, 3], [2, 3, 4], [3, 4, 5], [1, 4, 10]]
- Expected Output: 12

Explanation: The minimum cost to connect all cities is obtained by using the connections [1, 2, 3], [2, 3, 4], and [3, 4, 5]. This gives a total cost of 3 + 4 + 5 = 12.

Example 3:
- Input: n = 3, connections = [[1, 2, 6], [2, 3, 2], [1, 3, 10]]
- Expected Output: 8

Explanation: The minimum cost to connect all cities is obtained by using the connections [1, 2, 6] and [2, 3, 2]. This gives a total cost of 6 + 2 = 8.

Constraints:

1 <= n <= 104
1 <= connections.length <= 104
connections[i].length == 3
1 <= xi, yi <= n
xi != yi
0 <= costi <= 105

Solution

To solve this problem, we will use Kruskal's algorithm. This algorithm is ideal for finding the Minimum Spanning Tree (MST) in a graph. The MST ensures all nodes are connected with the least total cost, which suits our requirement to connect all cities with the minimum cost.

Kruskal's algorithm works by sorting all edges in ascending order of their weight and then adding edges one by one to the MST. We use the Union-Find data structure to check if adding an edge will form a cycle. If it does not form a cycle, we add it to our MST. This process continues until all cities are connected or we have examined all edges.

Step-by-Step Algorithm

Initialize Union-Find Structure:
- Create a UnionFind class to manage the connected components.
- This class should have methods to find the root of a node and to unite two components.
Convert and Sort Edges:
- Convert the list of connections to a list of edges, adjusting the city indices to be zero-based.
- Sort the edges by their cost in ascending order.
Initialize Variables:
- Create a variable totalCost to keep track of the total cost of connecting the cities.
- Create a variable edgesUsed to count the number of edges used in the minimum spanning tree.
Process Each Edge:
- Iterate through the sorted edges.
- For each edge, use the union method to attempt to connect the two cities.
  - If the cities were not already connected, add the cost of the edge to totalCost and increment edgesUsed.
  - If edgesUsed equals n - 1, return totalCost as we have connected all cities.
Check Connectivity:
- If after processing all edges, edgesUsed is less than n - 1, return -1 because it's not possible to connect all cities.

Algorithm Walkthrough

Using the input:

n = 5
connections = [[1, 2, 2], [1, 3, 3], [4, 5, 1], [3, 4, 4], [2, 5, 6]]

Convert and Sort Edges:
- Adjust connections to be zero-based: [(0, 1, 2), (0, 2, 3), (3, 4, 1), (2, 3, 4), (1, 4, 6)]
- Sort by cost: [(3, 4, 1), (0, 1, 2), (0, 2, 3), (2, 3, 4), (1, 4, 6)]
Initialize Union-Find:
- parent = [0, 1, 2, 3, 4]
- rank = [0, 0, 0, 0, 0]
- totalCost = 0
- edgesUsed = 0
Process First Edge (3, 4, 1):
- find(3) returns 3
- find(4) returns 4
- union(3, 4):
  - Union successful
  - parent = [0, 1, 2, 3, 3]
  - rank = [0, 0, 0, 1, 0]
  - totalCost += 1 → totalCost = 1
  - edgesUsed += 1 → edgesUsed = 1
Process Second Edge (0, 1, 2):
- find(0) returns 0
- find(1) returns 1
- union(0, 1):
  - Union successful
  - parent = [0, 0, 2, 3, 3]
  - rank = [1, 0, 0, 1, 0]
  - totalCost += 2 → totalCost = 3
  - edgesUsed += 1 → edgesUsed = 2
Process Third Edge (0, 2, 3):
- find(0) returns 0
- find(2) returns 2
- union(0, 2):
  - Union successful
  - parent = [0, 0, 0, 3, 3]
  - rank = [1, 0, 0, 1, 0]
  - totalCost += 3 → totalCost = 6
  - edgesUsed += 1 → edgesUsed = 3
Process Fourth Edge (2, 3, 4):
- find(2) returns 0
- find(3) returns 3
- union(0, 3):
  - Union successful
  - parent = [0, 0, 0, 0, 3]
  - rank = [2, 0, 0, 1, 0]
  - totalCost += 4 → totalCost = 10
  - edgesUsed += 1 → edgesUsed = 4
Check if All Cities are Connected:
- edgesUsed = 4 equals n - 1 = 4
- All cities are connected, return totalCost = 10

Thus, the minimum cost to connect all the cities is 10.

Code

Python3

. . . .

Complexity Analysis

Time Complexity:
- Sorting Edges: Sorting the edges based on their cost takes $O(E \log E)$ , where (E) is the number of edges.
- Union-Find Operations: The union-find operations (find and union) take almost constant time, $O(\alpha(N))$ , where $\alpha\$ is the inverse Ackermann function. Thus, for (E) edges, it will be $O(E \alpha(N))$ .
- Total Time Complexity: Combining these, the total time complexity is $O(E \log E + E \alpha(N))$ . Since $\alpha(N)$ is very small and can be considered nearly constant, the time complexity is dominated by $O(E \log E)$ .
Space Complexity:
- Union-Find Data Structures: Storing the parent and rank arrays takes $O(N)$ space, where (N) is the number of cities.
- Edge List: Storing the edges requires $O(E)$ space.
- Total Space Complexity: The total space complexity is $O(N + E)$ .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible