2. Code skeleton for Prim algorithm is given. You have to complete the code. Read the comments carefully and write your code where it is instructed to. You cannot change any code that is already given. For the given input, the output should be the following. Test your code with different start vertex and input.

Output: 1 -- 0 -> 2 2 -- 1 -> 3 3 -- 0 -> 6 4 -- 1 -> 5 MST COST: 16

Code Skeleton:

#include #include

using namespace std;

//This function has already been implemented for you //This function takes a 2d array and prints it void printGraph(int **g, int n) { for(int i=0; i { for(int j=0; j { cout << g[i][j] << " "; } cout << endl; } }

//This function takes values and isTaken arrays as inputs //Returns the index of the vertex that has been not taken in the MST yet and has lowest value int findMinValue(int values[], bool isTaken[], int n) { //Write your code here }

//This function takes parent, values and isTaken arrays as input //initialize these arrays with appropriate values in the function void initialize(int parent[], int values[], bool isTaken[], int n) { //Write your code here }

//This function takes parent and values arrays input //This function is called at the end of the construction of the MST //Returns the total cost of the MST and prints the edges that have been taken //Hint: The edge cost for each vertex is stored in the values array int calculate_cost(int parent[], int values[], int n) { //Write your code here }

//This function takes graph as input //Here, start_vertex is the vertex from which the prim algorithm starts running int prim(int **graph, int n, int start_vertex) { //Every vertex has 3 properties - parent, value, isTaken in MST //parent array stores the parent for each vertex //values stores the edge cost(the edge that will be included in the MST) for each vertex //isTaken keeps track of the vertices that have already been taken in the MST int parent[n], values[n]; bool isTaken[n]; initialize(parent, values, isTaken, n);

//Change the appropriate properties for start vertex

/**Start your code here

End your code here**/

//Remember, a MST with n vertices should have (n-1) edges //At first, find the vertex (u) with minimum value that has not been included in the MST yet and include //Then find the adjacent vertex (v) of the vertex u that has not been included and has more value than the edge cost //Update the properties for such vertices v

/**Start your code here

End your code here**/

int total_cost = calculate_cost(parent, values, n);

return total_cost; }

int main() { //Here, n is the number of vertices int n;

//We will take the input from a file. //The file is uploaded too. Keep it in the same folder. ifstream fp("input_graph.txt"); fp >> n; cout << n << endl;

//We are initializing a 2d array with double pointer //Google and learn about it if you don't know yet! int** graph = new int*[n];

for(int i=0; i { graph[i] = new int[n]; } //Taking input from the file to the graph array for(int i=0; i { for(int j=0; j { fp >> graph[i][j]; } } printGraph(graph, n);

//Let's call the prim function and store the cost for MST int mst_cost = prim(graph, n, 0); cout << "MST COST: " << mst_cost << endl; return 0; }

#include #include

using namespace std;

//This function has already been implemented for you //This function takes a 2d array and prints it void printGraph(int **g, int n) { for(int i=0; i { for(int j=0; j { cout << g[i][j] << " "; } cout << endl; } }

//This function takes values and isTaken arrays as inputs //Returns the index of the vertex that has been not taken in the MST yet and has lowest value int findMinValue(int values[], bool isTaken[], int n) { //Write your code here }

//This function takes parent, values and isTaken arrays as input //initialize these arrays with appropriate values in the function void initialize(int parent[], int values[], bool isTaken[], int n) { //Write your code here }

//This function takes parent and values arrays input //This function is called at the end of the construction of the MST //Returns the total cost of the MST and prints the edges that have been taken //Hint: The edge cost for each vertex is stored in the values array int calculate_cost(int parent[], int values[], int n) { //Write your code here }

//This function takes graph as input //Here, start_vertex is the vertex from which the prim algorithm starts running int prim(int **graph, int n, int start_vertex) { //Every vertex has 3 properties - parent, value, isTaken in MST //parent array stores the parent for each vertex //values stores the edge cost(the edge that will be included in the MST) for each vertex //isTaken keeps track of the vertices that have already been taken in the MST int parent[n], values[n]; bool isTaken[n]; initialize(parent, values, isTaken, n);

//Change the appropriate properties for start vertex

/**Start your code here

End your code here**/

//Remember, a MST with n vertices should have (n-1) edges //At first, find the vertex (u) with minimum value that has not been included in the MST yet and include //Then find the adjacent vertex (v) of the vertex u that has not been included and has more value than the edge cost //Update the properties for such vertices v

/**Start your code here

End your code here**/

int total_cost = calculate_cost(parent, values, n);

return total_cost; }

int main() { //Here, n is the number of vertices int n;

//We will take the input from a file. //The file is uploaded too. Keep it in the same folder. ifstream fp("input_graph.txt"); fp >> n; cout << n << endl;

//We are initializing a 2d array with double pointer //Google and learn about it if you don't know yet! int** graph = new int*[n];

for(int i=0; i { graph[i] = new int[n]; } //Taking input from the file to the graph array for(int i=0; i { for(int j=0; j { fp >> graph[i][j]; } } printGraph(graph, n);

//Let's call the prim function and store the cost for MST int mst_cost = prim(graph, n, 0); cout << "MST COST: " << mst_cost << endl; return 0; }

***********Instruction: You must need to follow this code skeleton for the given problem.************