Connecting Cities With Minimum Cost - Leetcode Solution

Problem Statement

You have to connect N cities using minimum cost. Assume that you have a set of pairs with cities' distances represented as a collection of edges in a graph. Your task is to find the minimum cost of connecting all N cities. If you connect a pair of cities, their distance is added to the cost.

Input Format

The function takes two inputs as parameter:

n: an integer representing the total number of cities.

edges: a list of integer tuples, where each tuple contains three/values. The first two values represent the city numbers to be connected and the third value represents the distance between these cities.

Output Format

The function should return minimum cost to connect all N cities.

Solution

We can solve this problem using Kruskal's Algorithm. Kruskal's Algorithm is a greedy algorithm that finds a minimum spanning tree in an undirected weighted graph.

Steps to solve the problem:

1- Sort all the edges in non-decreasing order of their weight.

2- Pick the smallest edge in the sorted list and check if it forms a cycle with the minimum spanning tree formed so far. If not, add it to the minimum spanning tree; otherwise, discard it.

3- Repeat step 2 until there are (N-1) edges in the minimum spanning tree.

4- Return the sum of the weights of all the edges in the minimum spanning tree.

Pseudo Code

1. Sort all the edges in non-decreasing order of their weight.

2. Create a parent array to keep track of all the nodes.

3. Create a find_root function to find the root of a node.

   def find_root(parent, node): while parent[node] != node: node = parent[node] return node

4. Create a Kruskal function to find the minimum spanning tree.

   def Kruskal(n, edges): #Step 1 edges.sort(key=lambda x:x[2]) #Step 2 parent = [i for i in range(n)] min_cost = 0 for edge in edges: u, v, w = edge r1 = find_root(parent, u) r2 = find_root(parent, v) if r1 != r2: parent[r1] = r2 min_cost += w if len(set(parent)) == 1: #Step 3 break # Step 4 return min_cost

5. Finally, call the Kruskal function and return the minimum cost.

   return Kruskal(n, edges)

Time complexity: O(mlogm) where m is the number of edges.

Space complexity: O(n) where n is the number of nodes.

1