// 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 harness for the breadth first search traversal code // 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" #include "aqueue.h" // Queue used by breadth-first traversal Queue* Q; // Start with some implementations for the abstract functions void PreVisit(Graph* G, int v) { cout << "PreVisit vertex " << v << "\n"; } void PostVisit(Graph* G, int v) { cout << "PostVisit vertex " << v << "\n"; } void BFS(Graph* G, int start, Queue* Q) { int v, w; Q->enqueue(start); // Initialize Q G->setMark(start, VISITED); while (Q->length() != 0) { // Process all vertices on Q v = Q->dequeue(); PreVisit(G, v); // Take appropriate action for (w=G->first(v); wn(); w = G->next(v,w)) if (G->getMark(w) == UNVISITED) { G->setMark(w, VISITED); Q->enqueue(w); } } } // Test the generalized traversal function // Start with some implementations for the abstract functions void doTraverse(Graph* G, int v) { cout << "doTraverse vertex " << v << "\n"; BFS(G, v, Q); } void graphTraverse(Graph* G) { int v; for (v=0; vn(); v++) G->setMark(v, UNVISITED); // Initialize mark bits for (v=0; vn(); v++) if (G->getMark(v) == UNVISITED) doTraverse(G, v); } // Test Breadth First Search: // Version for Adjancency List representation int main(int argc, char** argv) { Graph* G; FILE *fid; if (argc != 2) { cout << "Usage: grbfsl \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); } Q = new AQueue(G->n()); graphTraverse(G); return 0; }