Find Minimum cost to connect all cities in C++

In this article, we are going to learn how to find the minimum cost to connect all cities in C++ programming. The problem is that we are given a number of cities there is a specific cost of connecting one city to others. So we need to connect the cities in a manner so that we can achieve the minimum cost.

To solve the given problem, we can consider the city as nodes of a graph and the connecting roads as edges of a graph. We need to find the calculate the minimum cost of connecting the cities so this would be a weighted graph, and we need to find the minimum spanning tree of the graph. 

A minimum spanning tree is a subset of a graph that connects all the vertices without forming a cycle and with minimum cost. As shown in the diagram  

diagram 1

C++ program to find the minimum spanning tree

Below is our code for the task:

#include<bits/stdc++.h>
using namespace std;

// this function finds the minimum
// index in the graph 
int findminIndex(int*weight,bool*visited,int n){
    int minIndex = -1;
for(int i = 0 ; i < n; i++){
    if(!visited[i] && (minIndex == -1 || weight[i] < weight[minIndex])){
        minIndex = i;
    }
}
return minIndex;
}

// this function calculates and returns
// cost of minimum spanning tree
void prims(int**edges , int n){

    int*weight = new int[n];
    bool*visited = new bool[n];
    int*parent = new int[n];
    for(int i = 0 ; i < n ; i++){
        weight[i] = INT_MAX;
        visited[i] = false;
    }
parent[0] = -1;
weight[0] = 0;
    for(int i = 0 ; i<n ;i++){
        int minIndex = findminIndex(weight,visited,n);
    visited[minIndex] = true;

    for(int j = 0 ; j < n ; j++){
        if(edges[minIndex][j] != 0 && !visited[j]){
            if(edges[minIndex][j] < weight[j]){
                weight[j] = edges[minIndex][j];
                parent[j] = minIndex;
            }
         }
     }
  }
  int ans = 0;
  for(int i = 1 ; i < n ; i++){
    if(parent[i] < i){

        ans += weight[i];
    }else{

        ans += weight[i];
    }
  }

  cout<<ans;
}



int main(){
// taking number of vertices and
// number of edges as input
int n;
int e;
cin>>n>>e;
// making a 2 d array and assigning
// '0' value to all the indexes
int**edges = new int*[n];
for(int i = 0 ; i < n ; i++){
    edges[i] = new int[n];
    for(int j = 0 ; j < n ; j++){
        edges[i][j] = 0;
    }
}
// taking input for graph i.e
//which 2 nodes are connected
for(int i = 0 ; i < e ; i++){
    int f,s,weight;
    cin>>f>>s>>weight;
    edges[f][s] = weight;
    edges[s][f] = weight;
}
cout<<endl;
prims(edges,n);
for(int i = 0 ; i < n ; i++){
    delete[]edges[i];
}

delete []edges;
}
// sample input for graph

/*5 7
0 1 4
0 2 8
1 3 6
1 2 2
2 3 3
2 4 9
3 4 5
*/

 

Function implementation 

1. Prims -:
This function follows the prims algorithm and calculates the cost of the minimum spanning tree. 

2. findminIndex-:
This function returns the minimum index of the graph.   

Implementation 

Firstly we have taken a graph as input in a 2D array, indexes with zero have no edge between them, and indexes with 1 has an edge between them. As shown in the diagram.  

diagram 2

Now we call function prims(edges,n). In this function first, we have created a certain number of arrays like  

1.int weight[] which will store the weight of the edge 

2.bool visited[] this will keep a track of the nodes which have been visited as in minimum spanning tree we don’t need cyclic graph so we will visit a node one time only. 

3.int parent[] this will store the parent of a node, the parent node is from where the edge is starting. For example, if we are connecting  “0 to 1” so “0” will be the parent and “1” will be the child. 

Then we will initialize visited as false as we haven’t visited any of the nodes. And weight as maximum int. Then we run a loop which calls findminIndex(int*weight,bool*visited, int n) this gives the current minimum index of the node which hasn’t visited yet. 

Then we compare the weight of the node with and update the weight and parent if the latest weight is smaller. For example from “0 to 2” the weight stored is “8” and “0” is the parent of “2” but from “1 to 2” the weight is “2” so we will update the weight as 2 and mark the parent of “2” as “1”. 

At last, we will traverse the path of the minimum spanning tree and add all the weight to get the minimum weight. 


Now its time to run our code and see the output. In our example we can able to see the output like you can see below:

14

Leave a Reply