// File BFSCamminiMinimi.cpp

// Calcola i cammini minimi di tutti i nodi da un nodo rad - tali cammini
// vengono mantenuti in forma implicita usando semplicemente un vettore dei
// predecessori

#include <iostream.h>
#include "Grafo.h"
#include "Coda.h"

void BFSCamminiMinimi(Grafo& g, int rad, int* pred)
{ // pred e' un vett in sharing dove vengono restituiti i predecessori
  bool* marca = new bool[g.NumNodi()];
  for (int i = 0; i < g.NumNodi(); i++)
    marca[i] = false;
  Coda<int> c;

  //InizioVisita: inizia la visita del grafo
  for (int i=0; i < g.NumNodi(); i++) pred[i] = -1;

  marca[rad] = true;

  //PreVisita di rad: inizia la visita di rad (rad diviene "grigio" -cfr. clr)
  //pred[rad] = -1; la radice non ha predecessori

  c.InCoda(rad);

  while (!c.EstVuota()) {
    int i = c.Primo(); c.OutCoda();
    Iteratore* itr = g.Successori(i);
    while (itr->HasNext()) {
      int j = itr->Next();
      if (!marca[j]) {
        marca[j] = true;

        //PreVisita di j: inizia la visita di j (j diviene "grigio")
        pred[j] = i;

        c.InCoda(j);
      }
    }
    delete itr;
    //PostVisita di i: termina la visita di i (i diviene "nero")
    //niente
  }

  //FineVisita: la visita del grafo e' terminata
  //niente
  delete[] marca;
}