The Commutable Islands problem, also known as the Minimum Spanning Tree problem, is a common challenge in graphs and algorithms. The problem involves finding the minimum cost of connecting a set of islands, represented by a weighted, undirected graph, so that each island is connected.

This article will explore the Commutable Island problem in more detail, discussing its relevance and potential solution.

Problem Statement

We are given a scenario where we have â€śXâ€ť number of islands and â€śYâ€ť number of bridges that connect some or all of these islands. Each bridge is associated with a cost that is required to be paid to use it.

Our objective is to find a set of bridges that connects all the islands at the minimum possible cost. In other words, we need to find the minimum cost set of bridges to ensure all islands are connected.

It is guaranteed that at least one possible scenario exists where all islands can be connected. It means there is a way to connect all the islands using the available bridges, and we do not need to worry about the possibility of the islands being disconnected.

Input Format

The input for the problem consists of two parts.

The first part is an integer value, X, which represents the number of islands in the scenario.

The second part of the input is a 2-dimensional integer matrix A, with a size of Yx 3. Each row in the matrix represents a bridge that connects two islands.

The first two elements of each row, A[i][0] and A[i][1], indicate the two islands that are connected by the bridge.

The third element, A[i][2], represents the cost associated with using the bridge.

Output Format

You have to give an integer that represents the lowest cost required to connect all the islands.

Constraints

The given constraints are:

X is an integer between 1 and 60000 (inclusive).

The first and second values of each element in a 2D array A are integers between 1 and X (inclusive).

The third value of each element in A is an integer between 1 and 1000 (inclusive).

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Sample Examples

Consider the following examples to understand the problem better.

Input 1

X = 3

A = [ [1, 2, 6 ]

[2, 3, 3 ]

[3, 1, 1 ] ]

Output 1

4

Reason 1

We can join all these islands using the following bridges:

(1, 2) and (2, 3)

(1, 2) and (1, 3)

(1, 3) and (2, 3)

As you can see, the optimal way to connect these islands is by using the two bridges connecting (1, 3) and (2, 3), which cost 1 and 3, respectively.

Let's look at another example.

Input 2

X = 4

A = [ [ 1, 2, 1 ]

[ 2, 4, 6 ]

[ 1, 3, 3 ]

[ 4, 3, 9 ]

[ 1, 4, 10 ] ]

Output 2

10

Reason 2

We can visit every island using these three bridges (1, 2), (1, 3), and (4, 2), which cost 1, 3, and 6, respectively. And so, the total cost incurred here is 1 + 3 + 6 = 10, which is the minimum possible in this scenario.

Solution

To solve this problem, we can utilize graphs. We need to find the minimum cost we need to pay for the bridges to connect all the islands.

We can represent the islands as nodes and the bridges as edges in a graph. Now, we just need to find the Minimum Spanning Tree of this graph because M.S.T. will help us know the minimum cost required to keep all the nodes(islands) connected with edges(bridges).

Let us now look at the solution to this problem.

Solution using Kruskalâ€™s Algorithm

In this approach, we will use Kruskalâ€™s Algorithm to find the Minimum Spanning Tree.

Algorithm

Following is the algorithm we are going to use to find the solution to this problem.

Create a vector of edges from the input matrix, where each edge contains the source vertex, destination vertex, and weight of the edge.

Sort the edges in ascending order of weight.

Initialize a variable "minCost" to 0.

Create a vector of parent and rank arrays to keep track of the disjoint sets.

Initialize each element of the parent array to its index and each element of the rank array to 0.

Traverse the sorted edges in order, adding each edge to the minimum spanning tree if it does not create a cycle.

To check if adding an edge will create a cycle, we use the find and union operations from the union-find algorithm. Find returns the representative of the set containing a given vertex, and union merges the sets containing two vertices.

If the edge is added to the minimum spanning tree, add its weight to "minCost".

Stop traversing the edges when the number of edges in the minimum spanning tree is equal to the number of vertices - 1.

Return "minCost" as the total weight of the minimum spanning tree

Let us now look at the implementation of this algorithm.

Implementation

Following is the implementation of the above-discussed approach in C++ and Java.

Implementation in C++

#include<bits/stdc++.h>
using namespace std;
/*
Structure of the graph
used to solve the
probelm
*/
struct Bridge {
int start, end, cost;
};
/*
Function to compare Bridges
based on their costs
*/
bool compareBridges(Bridge a, Bridge b) {
return a.cost < b.cost;
}
/*
Function to find the parent
of a node
*/
int findParent(vector < int > & parent, int i) {
if (parent[i] == i)
return i;
return parent[i] = findParent(parent, parent[i]);
}
/*
Function to merge two sets
based on their ranks
*/
void mergeSets(vector < int > & parent, vector < int > & rank, int x, int y) {
int xroot = findParent(parent, x);
int yroot = findParent(parent, y);
if (rank[xroot] < rank[yroot])
parent[xroot] = yroot;
else if (rank[xroot] > rank[yroot])
parent[yroot] = xroot;
else {
parent[yroot] = xroot;
rank[xroot]++;
}
}
/*
Function to find the minimum
cost to connect all islands
using Kruskal's algorithm
*/
int minimumCostOfConnectingIslands(int numOfIslands, vector < Bridge > & bridges) {
sort(bridges.begin(), bridges.end(), compareBridges);
// Parent and rank arrays
vector < int > parent(numOfIslands);
vector < int > rank(numOfIslands);
for (int i = 0; i < numOfIslands; i++) {
parent[i] = i;
rank[i] = 0;
}
int minCost = 0, numOfBridges = 0;
for (Bridge bridge: bridges) {
int start = bridge.start;
int end = bridge.end;
int cost = bridge.cost;
int x = findParent(parent, start);
int y = findParent(parent, end);
if (x != y) {
numOfBridges++;
minCost += cost;
mergeSets(parent, rank, x, y);
}
/*
If all islands are connected,
break out of the loop
*/
if (numOfBridges == numOfIslands - 1) break;
}
return minCost;
}
// Function to solve the problem
int solve(int numOfIslands, vector < vector < int > > & bridges) {
vector < Bridge > bridgeList;
for (auto & bridge: bridges) {
int start = bridge[0] - 1;
int end = bridge[1] - 1;
int cost = bridge[2];
bridgeList.push_back({ start, end, cost });
}
return minimumCostOfConnectingIslands(numOfIslands, bridgeList);
}
// Main Function
int main() {
int numOfIslands = 3;
vector < vector < int >> bridges = {{1, 2, 6}, {2, 3, 3}, {3, 1, 1}};
int minCost = solve(numOfIslands, bridges);
cout << minCost << endl;
return 0;
}

Output

Implementation in Java

import java.util.*;
class Main {
/*
Class to define the graph
used to solve the problem
*/
static class Bridge {
int start, end, cost;
// Constructor
Bridge(int start, int end, int cost) {
this.start = start;
this.end = end;
this.cost = cost;
}
}
/*
Function to find the parent
of a node
*/
static int findParent(int[] parent, int i) {
if (parent[i] == i)
return i;
return parent[i] = findParent(parent, parent[i]);
}
/*
Function to merge two sets
based on their ranks
*/
static void mergeSets(int[] parent, int[] rank, int x, int y) {
int xroot = findParent(parent, x);
int yroot = findParent(parent, y);
if (rank[xroot] < rank[yroot])
parent[xroot] = yroot;
else if (rank[xroot] > rank[yroot])
parent[yroot] = xroot;
else {
parent[yroot] = xroot;
rank[xroot]++;
}
}
/*
Function to find the minimum
cost to connect all islands
using Kruskal's algorithm
*/
static int minimumCostOfConnectingIslands(int numOfIslands, List<Bridge> bridges) {
/*
Sorting the bridges
based on their cost
*/
Collections.sort(bridges, (a, b) -> a.cost - b.cost);
// Parent and rank arrays
int[] parent = new int[numOfIslands];
int[] rank = new int[numOfIslands];
for (int i = 0; i < numOfIslands; i++) {
parent[i] = i;
rank[i] = 0;
}
int minCost = 0, numOfBridges = 0;
for (Bridge bridge : bridges) {
int start = bridge.start;
int end = bridge.end;
int cost = bridge.cost;
int x = findParent(parent, start);
int y = findParent(parent, end);
if (x != y) {
numOfBridges++;
minCost += cost;
mergeSets(parent, rank, x, y);
}
/*
If all islands are connected,
break out of the loop
*/
if (numOfBridges == numOfIslands - 1)
break;
}
return minCost;
}
// Function to solve the problem
static int solve(int numOfIslands, int[][] bridges) {
List<Bridge> bridgeList = new ArrayList<>();
for (int[] bridge : bridges) {
int start = bridge[0] - 1;
int end = bridge[1] - 1;
int cost = bridge[2];
bridgeList.add(new Bridge(start, end, cost));
}
return minimumCostOfConnectingIslands(numOfIslands, bridgeList);
}
// Main function
public static void main(String[] args) {
int numOfIslands = 3;
int[][] bridges = {{1, 2, 6}, {2, 3, 3}, {3, 1, 1}};
int minCost = solve(numOfIslands, bridges);
System.out.println(minCost);
}
}

Output

Complexity Analysis

The time and space complexities of this code are as follows

Time Complexity

O(ElogE) is the time complexity of this code.Here, E is the number of bridges (represented by the edges of a graph). This is because Kruskal's algorithm involves sorting the edges and then iterating over them. The sorting step takes O(ElogE) time, and the iteration over the edges takes O(E) time, resulting in a total time complexity of O(ElogE + E) which can be represented as O(ElogE).

Space Complexity

O(V) is the space complexity of this code. Here, V is the number of islands (vertices) in the graph. This is because we are creating two arrays of size V to keep track of the parent and rank of each island in the union-find algorithm.

We can also use Primâ€™s algorithm to solve this question. Letâ€™s see how.

Solution Using Primâ€™s Algorithm

This approach is based on Prim's algorithm for finding the minimum spanning tree of a graph. The idea is to start with an arbitrary node and greedily add the edge with the minimum weight that connects to an unvisited node. This ensures that we are always adding the cheapest edge to the current set of visited nodes. The resulting minimum spanning tree is guaranteed to be the cheapest way to connect all the islands.

Algorithm

The algorithm for the above-discussed approach is as follows:

Create an adjacency list representation of the graph, where each node is represented by an integer from 1 to N, and each edge is represented by a pair of integers (u, v), indicating an edge between nodes u and v.

Start with an arbitrary node and add its edges to a priority queue. Set the start node as visited.

Initialize an empty list to store the minimum spanning tree, and set its weight to 0.

Loop until all nodes have been visited or added to the minimum spanning tree:

Get the edge with the minimum weight from the priority queue.

If the edge connects to a visited node, skip to the next edge.

Otherwise, mark the new node as visited, add the edge to our minimum spanning tree, and add its weight to the total weight of our minimum spanning tree.

Add the edges of the new node to the priority queue, but only if they connect to unvisited nodes.

Return the total weight of the minimum spanning tree.

Let us now look at the implementation of this code.

Implementation

Following is the implementation in C++ and Java.

Implementation in C++

#include<bits/stdc++.h>
using namespace std;
/*
Defining a pair of integers
as pii for convenience
*/
#define pii pair < int, int >
/*
Function to find the minimum
cost of connecting all the
islands
*/
int findMinCost(vector < vector < pii >> & adj, int n) {
/*
Initializing a vector to
keep track of visited islands
*/
vector < int > vis(n + 1, 0);
/*
Initializing a priority queue
to keep track of the bridges
to be visited next
*/
priority_queue < pii, vector < pii > , greater < pii >> pq;
/*
Pushing the starting island
(island 1) to the priority
queue with a weight of 0
*/
pq.push({0, 1 });
/*
Initializing a variable to keep
track of the total cost of
connecting all the islands
*/
int ans = 0;
while (!pq.empty()) {
/*
Getting the bridge with minimum
weight from the priority queue
*/
pii top = pq.top();
pq.pop();
int w = top.first, u = top.second;
/*
If the current island has already
been visited, continue to the
next iteration of the loop
*/
if (vis[u]) continue;
// Marking the current island as visited
vis[u] = 1;
ans += w;
/*
Looping through all the bridges
connected to the current island
*/
for (auto v: adj[u]) {
/*
If the island connected by the
bridge has not been visited yet,
add the bridge to the
priority queue
*/
if (!vis[v.first]) pq.push({
v.second,
v.first
});
}
}
// Returning the minimum cost
return ans;
}
// Main function
int main() {
int n = 3;
vector < vector < int >> b = {{1, 2, 6}, {2, 3, 3}, {3, 1, 1}};
/*
Initializing an adjacency
list to represent the bridges
between the islands
*/
vector < vector < pii >> adj(n + 1);
for (auto x: b) {
int u = x[0], v = x[1], w = x[2];
adj[u].push_back({v, w });
adj[v].push_back({u, w });
}
int ans = findMinCost(adj, n);
cout << ans << endl;
return 0;
}

Output

Implementation in Java

import java.util.*;
class Main {
/*
Pair class to store nodes
and their edge weights
*/
static class Pair implements Comparable<Pair> {
int first;
int second;
public Pair(int first, int second) {
this.first = first;
this.second = second;
}
/*
Compare method to sort pairs
by their first element
*/
public int compareTo(Pair other) {
return this.first - other.first;
}
}
public static int findMinCost(ArrayList<ArrayList<Pair>> adj, int n) {
/*
Initializing a vector to
keep track of visited islands
*/
int[] vis = new int[n + 1];
Arrays.fill(vis, 0);
// Priority queue to maintain minimum edge weights
PriorityQueue<Pair> pq = new PriorityQueue<>();
// add first node to priority queue
pq.add(new Pair(0, 1));
int ans = 0;
// Loop until priority queue is empty
while (!pq.isEmpty()) {
// get the node with minimum edge weight
Pair top = pq.poll();
int w = top.first, u = top.second;
/*
If the current island has already
been visited, continue to the
next iteration of the loop
*/
if (vis[u] == 1)
continue;
// Marking the current island as visited
vis[u] = 1;
ans += w;
// Add all adjacent nodes to priority queue
for (Pair v : adj.get(u)) {
if (vis[v.first] == 0)
pq.add(new Pair(v.second, v.first));
}
}
// Return minimum cost
return ans;
}
// Main function
public static void main(String[] args) {
int n = 3;
// Create adjacency list for nodes
ArrayList<ArrayList<Pair>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) {
adj.add(new ArrayList<Pair>());
}
int[][] bridges = { { 1, 2, 6 }, { 2, 3, 3 }, { 3, 1, 1 } };
for (int[] bridge : bridges) {
int u = bridge[0], v = bridge[1], w = bridge[2];
adj.get(u).add(new Pair(v, w));
adj.get(v).add(new Pair(u, w));
}
int ans = findMinCost(adj, n);
System.out.println(ans);
}
}

Output

Complexity Analysis

The time and space complexities of this code are as follows

Time Complexity

O(E log V) is the time complexity of this code.Here, E is the number of bridges (edges), and V is the number of islands (vertices). This is because we iterate over all the edges and perform log V operations to maintain the priority queue.

Space Complexity

O(V + E) is the space complexity of this code. Here, E is the number of bridges (edges), and V is the number of islands (vertices). This is because we need to store the adjacency list representation of the graph, which takes O(V + E) space, and also the priority queue, which takes up to O(E) space in the worst case.

Frequently Asked Questions

What is the Commutable Islands problem?

The commutable islands problem is a classic problem in computer science and graph theory, where the goal is to connect a given set of islands with the minimum cost such that every island is reachable from every other island.

What is the approach to solving the Commutable Islands problem?

The most commonly used approach to solve this problem is to use Kruskal's algorithm for finding the Minimum Spanning Tree of the given graph.

How does Kruskal's algorithm work?

Kruskal's algorithm is a greedy algorithm that works by sorting the edges of the graph in a non-decreasing order of their weight and then iteratively adding the smallest edge that does not form a cycle until all the vertices are connected.

What is time complexity?

The amount of time an algorithm or code takes to execute each instruction is known as its time complexity.

What is space complexity?

The total memory space used by an algorithm or code, including the space of input values, is referred to as "space complexity."

Conclusion

In this blog, we learned about the solution to the Commutable Islands problem. We found its solution by using a graph and finding its minimum spanning tree using Kruskalâ€™s algorithm.

You can follow these links for more such problems.