Di seguito vediamo l’algoritmo incaricato di svolgere l’attraversamento di un grafo non orientato in ampiezza Per permette il corretto funzionamento dell’algoritmo procediamo con la riscrittura della funzione create(), utilizzata per la creazione di un grafo, e parte della funzione print_gr(), utilizzata per la stampa di un grafo.

Il cuore della procedura risiede nella funzione walk().

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct graph {
  int id;	      // id del nodo
  int value;	      // valore del nodo
  int nA;	      // numero di archi
  int walk;           // identificativo dell'attraversamento
  struct graph **ar;
};

typedef struct graph graph;

// coda usata nell'atraversamento
struct queue {
 int value;
 struct queue *next;
};

typedef struct queue queue;

int view = 0;

graph *create(graph *gr, int nN);
void add_arch(graph *gr, int nN);
void walk(graph *gr, int r);
void print_gr(graph *gr, int nN, int cmd);

int is_empty(queue *first);
int front(queue *first);
queue *enqueue(queue *first, int val);
queue *dequeue(queue *first);

int main(void) {
  int nN, r, i;
  graph *gr = NULL;
  
  printf("Inserisci il numero di nodi: ");
  scanf("%d", &nN);
  
  gr = calloc(nN, sizeof(graph));
  if(gr == NULL) {
    printf("Allocazione 1 fallita");
    exit(1);
  }
  
  gr = create(gr, nN);
  
  printf("\nDefinisci la radice del grafo (0 -> %d): ", nN-1);
  scanf("%d", &r);
  
  printf("\nVisita dell'albero in corso...\n");
  walk(gr, r);
  
  // il ciclo for serve per visitare tutti i nodi dei grafi non connessi
  for(i=0; i<nN; i++) {
    walk(gr, i);
  }
  
  print_gr(gr, nN, 3);
  
  return 1;
}

graph *create(graph *gr, int nN) {
  int i, value;
  
  for(i=0; i<nN; i++) {
    printf("Inserisci il valore del nodo %d: ", i);
    scanf("%d", &value);
    
    gr[i].id = i;        // setto l'id dei nodi in modo sequenziale
    gr[i].value = value;
    gr[i].walk = -1;     // setto l'identificativo dell'attraversamento a -1 (non attraversato)
  }
  
  add_arch(gr, nN);
  return &gr[0];
 }

void add_arch(graph *gr, int nN) {
  int i, j; // contatori
  int nA, id;
  
  for(i=0; i<nN; i++) {
    printf("\nInserisci il numero di archi che partono dal nodo %d: ", i);
    scanf("%d", &nA);
    
    if(nA == 0) {
      continue;
    }
    
    gr[i].nA = nA;
    
    gr[i].ar = calloc(nA, sizeof(graph *));
    if(gr[i].ar == NULL) {
      printf("Allocazione 2.%d fallita", i);
      exit(1);
    }	
    
    for(j=0; j<nA; j++) {
      printf("\n - inserisci il nodo da raggiungere (da 0 a %d): ", nN-1);
      scanf("%d", &id);
      
      gr[i].ar[j] = &gr[id];
    }
  }
}

void walk(graph *gr, int r) {
  int i, k, ex=0;
  queue *cd = NULL;;
  
  if(gr[r].walk != -1) {
    return ;
  }
  
  k = r;
  do {
    gr[k].walk = view;
    view++;
    
    for(i=0; i<gr[k].nA; i++) {
      cd = enqueue(cd, gr[k].ar[i]->id);
    }
    
    if(is_empty(cd) == 0) {
      k = front(cd);
      cd = dequeue(cd);
    }
    else {
      ex = 1;
    }
  }while(ex == 0);
}

void print_gr(graph *gr, int nN, int cmd) {
  int i, j;
  
  if(cmd == 1 || cmd  == 3) {
    printf("\nLista nodi (%d):\n", nN);
    for(i=0; i<nN; i++) {
      printf("Nodo %d - Valore %d\n", gr[i].id, gr[i].value);
    }
  }
  
  printf("\n");

  if(cmd == 2 || cmd  == 3) {
    for(i=0; i<nN; i++) {
      printf("\nNodo %d - Valore %d - N. Archi %d - Visitato %d:\n", gr[i].id, gr[i].value, gr[i].nA, gr[i].walk);
			
      if(gr[i].nA == 0) {
        printf(" - Nessun arco\n");
      }

      for(j=0; j<gr[i].nA; j++) {
        printf(" - Da %d a %d\n", i, gr[i].ar[j]->id);
      }
    }
  }
}

int is_empty(queue *first) {
  if(first == NULL) {
    return 1;
  }
  else {
    return 0;
  }
}

int front(queue *first) {
  return first -> value;
}

queue *enqueue(queue *first, int val) {
  queue *current = first, *new;

  if(first == NULL) { // è il primo valore che inserisco
    first = malloc(sizeof(queue));
    if(first == NULL) {
      printf("Allocazione fallita\n");
      return NULL;
    }
    
    first -> value = val;
    first -> next = NULL;
  }
  else {
    while(current -> next != NULL) {
      current = current -> next;
    }

    new = malloc(sizeof(queue));
    if(new == NULL) {
      printf("Allocazione fallita\n");
      return NULL;
    }
    
    new -> value = val;
    new -> next = NULL;

    current -> next = new;
  }
  
  return first;
}

queue *dequeue(queue *first) {
  queue *temp = first -> next;

  free(first);
  return temp;
}

Per maggiori informazioni circa la sintassi del linguaggio si faccia riferimento alla guida al Linguaggio C.