Write a C++ program called prim.cpp that implements the Prim\'s algorithm to cal

Question

Write a C++ program called prim.cpp that implements the Prim's algorithm to calculate the minimum spanning tree (MST) from an input graph. Your program should ask a user for an input file name that includes the input graph information. Then, your program should present the edges to be added one-by- one to construct the MST. In the problem, you can assume that the maximum number of vertices ( nodes) in the input graph is less than or equal to 20. You can also assume that the input graph is alway:s connected. Input file format: This is a sample input file called tl.txt. 1 2 2 The first line (= 4 in the example) indicates that there are four vertices ( nodes) in the graph. The second line (-5 in the example) presents the number of edges in the graph. The remaining five lines present the edge information (= starting vertex, ending vertex, cost) in the graph. For the homework, you should assume that the first vertex starts from the number 1. Thus, tl.txt describes a graph like below 4 4 For the homework, you have to assume that a blank space is used to delimiter the values in the edge information. However, there's no space at the end of each line. If your program does not read the file properly, your program will get no credit. And also, do not assume that the starting vertex is always 1 Your program has to ask the user for the starting vertex. This is a sample result of the C++ program on the cloud9 $ g++-o prim prim.cpp ? ./prim Enter a file name: ./tl.txt Enter the first vertex to start: 1 (1) New edge: 1,2 -cost 2 (2) New edge: 2,4 -cost3 (3) New edge: 3,4 -cost 1

Explanation / Answer

// A C / C++ program for Prim's Minimum Spanning Tree (MST) algorithm.

// The program is for adjacency matrix representation of the graph

#include <iostream>

#include <cstdio>

#include <climits>

#include <fstream>

#define MAX 100

using namespace std;

// A utility function to find the vertex with minimum key value, from

// the set of vertices not yet included in MST

int minKey(int key[], bool mstSet[], int V)

{

// Initialize min value

int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (mstSet[v] == false && key[v] < min)

min = key[v], min_index = v;

return min_index;

}

// A utility function to print the constructed MST stored in parent[]

int printMST(int parent[], int n, int graph[MAX][MAX], int V)

{

printf("Edge Weight ");

for (int i = 1; i < V; i++)

printf("%d - %d %d ", parent[i], i, graph[i][parent[i]]);

}

// Function to construct and print MST for a graph represented using adjacency

// matrix representation

void primMST(int graph[MAX][MAX], int V)

{

int parent[V]; // Array to store constructed MST

int key[V]; // Key values used to pick minimum weight edge in cut

bool mstSet[V]; // To represent set of vertices not yet included in MST

// Initialize all keys as INFINITE

for (int i = 0; i < V; i++)

key[i] = INT_MAX, mstSet[i] = false;

// Always include first 1st vertex in MST.

key[0] = 0; // Make key 0 so that this vertex is picked as first vertex

parent[0] = -1; // First node is always root of MST

// The MST will have V vertices

for (int count = 0; count < V-1; count++)

{

// Pick the minimum key vertex from the set of vertices

// not yet included in MST

int u = minKey(key, mstSet, V);

// Add the picked vertex to the MST Set

mstSet[u] = true;

// Update key value and parent index of the adjacent vertices of

// the picked vertex. Consider only those vertices which are not yet

// included in MST

for (int v = 0; v < V; v++)

// graph[u][v] is non zero only for adjacent vertices of m

// mstSet[v] is false for vertices not yet included in MST

// Update the key only if graph[u][v] is smaller than key[v]

if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])

parent[v] = u, key[v] = graph[u][v];

}

// print the constructed MST

printMST(parent, V, graph, V);

}

// driver program to test above function

int main()

{

string file;

cout << "Enter the file name: ";

cin >> file;

string line;

int V, E;

int row, col, cost;

ifstream inFile;

  

inFile.open(file);

if (!inFile) {

cout << "Unable to open file";

exit(1); // terminate with error

}

  

inFile >> V;

inFile >> E;

  

int graph[MAX][MAX];

for(int i=0; i<V; i++) {

for(int j=0; j<V; j++) {

graph[i][j] = 0;

}

}

  

while (inFile >> row >> col >> cost) {

graph[row][col] = cost;

}

  

inFile.close();

// Print the solution

primMST(graph, V);

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.