// 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 depth 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" // 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 DFS(Graph* G, int v) { // Depth first search PreVisit(G, v); // Take appropriate action G->setMark(v, VISITED); for (int w=G->first(v); wn(); w = G->next(v,w)) if (G->getMark(w) == UNVISITED) DFS(G, w); PostVisit(G, v); // Take appropriate action } // Test the generalized traversal function // Start with some implementations for the abstract functions void doTraverse(Graph* G, int v) { cout << "doTraverse vertex " << v << "\n"; DFS(G, v); } 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 Depth First Search: // Version for Adjancency List representation int main(int argc, char** argv) { Graph* G; FILE *fid; if (argc != 2) { cout << "Usage: grdfsl \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); } graphTraverse(G); return 0; }