BFS intr-un graf

Parcurgerea in latime (Breadth-first Search - BFS) este un algoritm de cautare in graf, in care, atunci cand se ajunge intr-un nod oarecare, v, nevizitat, se viziteaza toate nodurile nevizitate adiacente lui v, apoi toate varfurile nevizitate adiacente varfurilor adiacente lui v, etc.
BFS depinde de nodul de start. Plecand dintr-un nod se va parcurge doar componenta conexa din care acesta face parte. Pentru grafuri cu mai multe componente conexe se vor obtine mai multi arbori de acoperire.
In urma aplicarii algoritmului BFS asupra fiecarei componente conexe a grafului, se obtine un arbore de acoperire (prin eliminarea muchiilor pe care nu le folosim la parcurgere). Pentru a putea reconstitui acest arbore, se pastreaza pentru fiecare nod dat identitatea parintelui sau. In cazul in care nu exista o functie de cost asociata muchiilor, BFS va determina si drumurile minime de la radacina la oricare
nod.
Pentru implementarea BFS se foloseste o coada. In momentul adaugarii in coada, un nod trebuie colorat gri (a fost descoperit si urmeaza sa fie prelucrat).
Algoritmul de explorare BFS este complet si optimal.

#include "stdio.h"
#include "stdlib.h"
#include "assert.h"
#include "queue.h"

#define START 0
#define FINISH 2
#define INF 10000

struct Nod
{
int nrVecini;
int * vecini;
int culoare;
int parinte;
};

int n;
struct Nod * graf;

/* citeste lista de adiacenta din fisier */
void readData()
{
FILE * f;
int i, j;

f = fopen( "in1.txt","r" );
assert( f );

fscanf( f, "%d", &n );
graf = ( struct Nod * ) malloc ( n * sizeof( struct Nod ) );

for ( i = 0; i < n; ++i ) {
fscanf( f, "%d", &graf[i].nrVecini );
graf[i].vecini = ( int * ) malloc ( graf[i].nrVecini * sizeof ( int ) );
for ( j = 0; j < graf[i].nrVecini; ++j )
fscanf( f, "%d", &graf[i].vecini[j] );
graf[i].parinte = -1;
graf[i].culoare = 0;
}
fclose( f );
}

void printRoad()
{
int aux = FINISH;
printf( "Drumul de la finish la start: " );
while ( aux != START ) {
printf ( "%d ", aux );
if ( graf[aux].parinte>=0 ) {
aux = graf[aux].parinte;
} else {
printf("\nEroare. nu se cunoaste parintele nodului %d\n", aux );
return;
}
}
printf ( "%d\n", aux );
}

/* parcurgere BFS a grafului, plecand din nodul start */
void BFS ( int start )
{
int *dist =(int *)malloc(n*sizeof(int));
int i;
for (i=0; i < n; i++)
dist[i] = INF;
dist[start] = 0;
graf[start].culoare = 1;// gri
Queue Q = NULL;
int j;
enqueue (&Q, &start);
while (size(Q) > 0) {
i = *(int *)Front(Q);
for(j=0; j < graf[i].nrVecini; j++) {
int *x = (int *)malloc(sizeof(int));
*x = graf[i].vecini[j];
if(graf[*x].culoare == 0) { //alb
dist[*x]=dist[i]+1;
graf[*x].parinte = i;
graf[*x].culoare = 1; // gri
enqueue(&Q, x);
free (x);
}
}
graf[i].culoare = 2; //negru
dequeue (&Q);

}
printf("start %d finish %d \n", START, FINISH);
printf("distanta este %d\n", dist[FINISH]);
}

int main(void){
int i;

//incarca graful din fisier
readData();

//parcurgere BFS
BFS( START );

//afisarea nodurilor dintre finish si start
printRoad();

for( i = 0; i < graf[i].nrVecini; ++i )
free(graf[i].vecini);
free(graf);
return 0;
}