Di seguito vediamo l’algoritmo incaricato di svolgere l’attraversamento di un grafo (rappresentato mediate la sua lista di adiacenza) non orientato in profondità. Al fine di permettere 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 graphi
  int walk;           // identificativo dell'attraversamento
  struct graph **ar;
};

typedef struct graph graph;

int view = 0;

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

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_graph(gr, nN);
  return &gr[0];
 }

void add_graph(graph *gr, int nN) {
  int i, j; // contatori
  int nA, id;

  for(i=0; i<nN; i++) {
    printf("\nInserisci il numero di graphi 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 i;

  if(gr -> walk == -1) {
    gr -> walk = view;
    view++;
  }

  for(i=0; i<gr -> nA; i++) {
    if(gr -> ar[i] -> walk == -1) {
      walk(gr -> ar[i]);
    }
  }
}

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. graphi %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);
      }
    }
  }
}

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