1: #include <iostream.h>
    2: 
    3: #define MAX 100    // maximum number of vertices
    4: #define INF 10000  // must be bigger than any shortest-path
    5: 
    6: class vertex {
    7: public:
    8:   int adj[MAX];       // vertices adjacent to this one
    9:   int nadj;           // # of vertices adjacent to this one
   10: 
   11:   // these fields are undefined until graphsearch() is called
   12:   int pred;           // previous hop on path from source to here
   13:   int cost;           // cost (number of hops) to get here from source
   14: 
   15:   vertex() { nadj = 0; }
   16:   void push(int neighbor) {
   17:     adj[nadj++] = neighbor;
   18:   }
   19: };
   20: 
   21: // find shortest paths from source to all other nodes
   22: // variations on this function are possible: returning the entire cost
   23: // array, taking a dest argument and returning cost[dest], etc.  this
   24: // variation fills in the 'pred' field and 'cost' of each node so
   25: // that path and cost cost can be determined trivially after
   26: // graphsearch returns.
   27: void graphsearch(vertex *v, int size, int source) {
   28:   int *queue = new int[size];
   29:   int qhead = 0, qtail = 0;
   30:   for (int i=0; i<size; i++) v[i].pred = -1;  // no path
   31:   v[source].cost = 0;
   32:   queue[qtail++] = source;
   33:   while (qhead != qtail) {
   34:     int u = queue[qhead++];
   35:     for (int j=0; j<v[u].nadj; j++) {
   36:       int av = v[u].adj[j];
   37:       if (v[av].pred == -1) {
   38:         v[av].pred = u;
   39:         v[av].cost = v[u].cost + 1;
   40:         queue[qtail++] = av;
   41:       }
   42:     }
   43:   }
   44:   delete[] queue;
   45: }
   46: 
   47: // print the path from source to dest
   48: // important: you must have already called graphsearch(..., source)
   49: void print_path(vertex *v, int source, int dest, char *sep) {
   50:   if (source == dest)
   51:     cout << dest;
   52:   else {
   53:     print_path(v, source, v[dest].pred, sep);
   54:     cout << sep << dest;
   55:   }
   56: }
   57: 
   58: // some examples
   59: int main() {
   60:   vertex v[MAX];
   61: 
   62:   // ... make up a graph (from CLR p.471)
   63:   v[0].push(1);
   64:   v[0].push(4);
   65:   v[1].push(0);
   66:   v[1].push(5);
   67:   v[2].push(3);
   68:   v[2].push(5);
   69:   v[2].push(6);
   70:   v[3].push(2);
   71:   v[3].push(7);
   72:   v[4].push(0);
   73:   v[5].push(1);
   74:   v[5].push(2);
   75:   v[5].push(6);
   76:   v[6].push(2);
   77:   v[6].push(5);
   78:   v[6].push(7);
   79:   v[7].push(3);
   80:   v[7].push(6);
   81:   graphsearch(v, 8, 1);       // calculate paths from 1->everywhere
   82:   print_path(v, 1, 3, ", ");  // print path from 1->3 (1 5 2 3)
   83:   cout << endl;
   84:   print_path(v, 1, 4, ", ");  // print path from 1->4 (1 0 4)
   85:   cout << endl;
   86:   cout << v[4].cost << endl;  // print cost of path from 1->4 (2)
   87: 
   88:   //print_path(v, 2, 4, ", ");// INVALID!
   89:                               // You must call graphsearch(..., 2) first
   90: }