// From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. // Test program for Prim's MCST algroithm. This version uses // a linear scan of the distance array to decide on which vertex is next // closest, similar to the first version of Dijkstra's algorithm // Use any of the files in this directory with a .gph extension. // This version is for the Adjancency List representation #include "book.h" #include "grlist.h" void AddEdgetoMST(int v1, int v2) { cout << "Add edge " << v1 << " to " << v2 << "\n"; } int minVertex(Graph* G, int* D) { // Find min cost vertex int i, v = -1; for (i=0; in(); i++) // Initialize v to some unvisited vertex; if (G->getMark(i) == UNVISITED) { v = i; break; } for (i=0; in(); i++) // Now find smallest value if ((G->getMark(i) == UNVISITED) && (D[i] < D[v])) v = i; return v; } void Prim(Graph* G, int* D, int s) { // Prim's MST algorithm int V[G->n()]; // Store closest vertex int i, w; for (i=0; in(); i++) { // Process the vertices int v = minVertex(G, D); G->setMark(v, VISITED); if (v != s) AddEdgetoMST(V[v], v); // Add edge to MST if (D[v] == INFINITY) return; // Unreachable vertices for (w=G->first(v); wn(); w = G->next(v,w)) if (D[w] > G->weight(v,w)) { D[w] = G->weight(v,w); // Update distance V[w] = v; // Where it came from } } } // Prim's MCST algorithm: linear scan of distance array for next vertex // Version for Adjancency List representation int main(int argc, char** argv) { Graph* G; FILE *fid; if (argc != 2) { cout << "Usage: grpriml1 \n"; exit(-1); } if ((fid = fopen(argv[1], "rt")) == NULL) { cout << "Unable to open file |" << argv[1] << "|\n"; exit(-1); } G = createGraph(fid); if (G == NULL) { cout << "Unable to create graph\n"; exit(-1); } int D[G->n()]; for (int i=0; in(); i++) // Initialize D[i] = INFINITY; D[0] = 0; Prim(G, D, 0); for(int k=0; kn(); k++) cout << D[k] << " "; cout << endl; return 0; }