#include <iostream.h>

#define MAX 100    // maximum number of vertices
#define INF 10000  // must be bigger than any shortest-path

class vertex {
public:
  int adj[MAX];       // vertices adjacent to this one
  int nadj;           // # of vertices adjacent to this one

  // these fields are undefined until graphsearch() is called
  int pred;           // previous hop on path from source to here
  int cost;           // cost (number of hops) to get here from source

  vertex() { nadj = 0; }
  void push(int neighbor) {
    adj[nadj++] = neighbor;
  }
};

// find shortest paths from source to all other nodes
// variations on this function are possible: returning the entire cost
// array, taking a dest argument and returning cost[dest], etc.  this
// variation fills in the 'pred' field and 'cost' of each node so
// that path and cost cost can be determined trivially after
// graphsearch returns.
void graphsearch(vertex *v, int size, int source) {
  int *queue = new int[size];
  int qhead = 0, qtail = 0;
  for (int i=0; i<size; i++) v[i].pred = -1;  // no path
  v[source].cost = 0;
  queue[qtail++] = source;
  while (qhead != qtail) {
    int u = queue[qhead++];
    for (int j=0; j<v[u].nadj; j++) {
      int av = v[u].adj[j];
      if (v[av].pred == -1) {
        v[av].pred = u;
        v[av].cost = v[u].cost + 1;
        queue[qtail++] = av;
      }
    }
  }
	delete[] queue;
}

// print the path from source to dest
// important: you must have already called graphsearch(..., source)
void print_path(vertex *v, int source, int dest, char *sep) {
  if (source == dest)
    cout << dest;
  else {
    print_path(v, source, v[dest].pred, sep);
    cout << sep << dest;
  }
}

// some examples
int main() {
  vertex v[MAX];

  // ... make up a graph (from CLR p.471)
  v[0].push(1);
  v[0].push(4);
  v[1].push(0);
  v[1].push(5);
  v[2].push(3);
  v[2].push(5);
  v[2].push(6);
  v[3].push(2);
  v[3].push(7);
  v[4].push(0);
  v[5].push(1);
  v[5].push(2);
  v[5].push(6);
  v[6].push(2);
  v[6].push(5);
  v[6].push(7);
  v[7].push(3);
  v[7].push(6);
  graphsearch(v, 8, 1);       // calculate paths from 1->everywhere
  print_path(v, 1, 3, ", ");  // print path from 1->3 (1 5 2 3)
  cout << endl;
  print_path(v, 1, 4, ", ");  // print path from 1->4 (1 0 4)
  cout << endl;
  cout << v[4].cost << endl;  // print cost of path from 1->4 (2)

  //print_path(v, 2, 4, ", ");// INVALID!
                              // You must call graphsearch(..., 2) first
}