// 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 Topological Sort using DFS // 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 printout(int v) { cout << v << " "; } void tophelp(Graph*, int); void topsort(Graph* G) { // Topological sort: recursive int i; for (i=0; in(); i++) // Initialize Mark array G->setMark(i, UNVISITED); for (i=0; in(); i++) // Process all vertices if (G->getMark(i) == UNVISITED) tophelp(G, i); // Call recursive helper function } void tophelp(Graph* G, int v) { // Process vertex v G->setMark(v, VISITED); for (int w=G->first(v); wn(); w = G->next(v,w)) if (G->getMark(w) == UNVISITED) tophelp(G, w); printout(v); // PostVisit for Vertex v } // Test Topological sort using DFS // Version for Adjancency List representation int main(int argc, char** argv) { Graph* G; FILE *fid; if (argc != 2) { cout << "Usage: grtsdl \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); } topsort(G); cout << endl; return 0; }