Commutable Island

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.

1. Create a vector of edges from the input matrix, where each edge contains the source vertex, destination vertex, and weight of the edge.
    
2. Sort the edges in ascending order of weight.
    
3. Initialize a variable "minCost" to 0.
    
4. Create a vector of parent and rank arrays to keep track of the disjoint sets.
    
5. Initialize each element of the parent array to its index and each element of the rank array to 0.
    
6. Traverse the sorted edges in order, adding each edge to the minimum spanning tree if it does not create a cycle.
   
   
   1. 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.
       
   2. If the edge is added to the minimum spanning tree, add its weight to "minCost".
       
7. Stop traversing the edges when the number of edges in the minimum spanning tree is equal to the number of vertices - 1.
    
8. 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:

1. 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.
    
2. Start with an arbitrary node and add its edges to a priority queue. Set the start node as visited.
    
3. Initialize an empty list to store the minimum spanning tree, and set its weight to 0.
    
4. Loop until all nodes have been visited or added to the minimum spanning tree:
   
   
   1. Get the edge with the minimum weight from the priority queue.
       
   2. If the edge connects to a visited node, skip to the next edge.
       
   3. 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.
       
   4. Add the edges of the new node to the priority queue, but only if they connect to unvisited nodes.
       
5. 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.

• Aggressive Cows
• Pythagorean Triplet in an array
• Best time to buy and sell stocks
• Kth largest element in an array.
• Sum Of Two Arrays.
• Median of two sorted arrays.
   

You may refer to our Guided Path on Code Studios for enhancing your skill set on DSA, Competitive Programming, System Design, etc. Check out essential interview questions, practice our available mock tests, look at the interview bundle for interview preparations, and so much more!

Happy Learning, Ninjas!