Di seguito vediamo l’algoritmo incaricato di svolgere l’attraversamento di un grafo (rappresentato mediate la sua matrice 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 nV;      // numero vertici
  int nL;      // numero lati
  int *value;  // valori dei nodi
  int **mat;   // matrice di adiacenza
  int *walk;   // identificati dell'attraversamento
};

typedef struct graph graph;

int view = 0;

void create(graph *gr);
void edge(graph *gr, int a, int b);
void walk(graph *gr, int r);
void print_gr(graph *gr, int cmd);

int main(void) {
  int r, i;
  graph gr;

  printf("Inserisci il numero di nodi: ");
  scanf("%d", &gr.nV);

  printf("Inserisci il numero dei lati: ");
  scanf("%d", &gr.nL);	

  create(&gr);

  printf("\nDefinisci la radice del grafo (0 -> %d): ", gr.nV-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<gr.nV; i++) {
    walk(&gr, i);
  }

  print_gr(&gr, 1);

  return 1;
}

void create(graph *gr) {
  int i, a, b;

  // alloco lo spazio per il vettore dei valori
  gr->value = calloc(gr->nV, sizeof(int));
  if(gr->value == NULL) {
    printf("Allocazione 1 fallita");
    exit(1);
  }

  // alloco lo spazio per il vettore di attraversamento
  gr->walk = calloc(gr->nV, sizeof(int));
  if(gr->walk == NULL) {
    printf("Allocazione 2 fallita");
    exit(1);
  }

  // carico i valori dei nodi
  for(i=0; i<gr->nV; i++) {
    printf("Valore del nodo %d: ", i);
    scanf("%d", &gr->value[i]);

    gr->walk[i] = -1;     // setto l'identificativo dell'attraversamento a -1 (non attraversato)
  }

  // aloco lo spazio per la matrice di adiacenza
  gr->mat = calloc(gr->nV, sizeof(int *));
  if(gr->mat == NULL) {
    printf("Allocazione 3 fallita");
    exit(1);
  }

  for(i=0; i<gr->nV; i++) {
    gr->mat[i] = calloc(gr->nV, sizeof(int));
    if(gr->mat[i] == NULL) {
      printf("Allocazione 4.%d fallita", i);
      exit(1);
    }
    memset(gr->mat[i], 0, sizeof(int)*gr->nV);
  }

  // carico la matrice
  for(i=0; i<gr->nL; i++) {
    printf("Lato (a b): ");
    scanf("%d %d", &a, &b);
    edge(gr, a, b);
  }
}

void edge(graph *gr, int a, int b) {
  if(a>gr->nV || a<0 || b>gr->nV || b<0) {
    exit(1);
  }

  gr->mat[a][b] = 1;
  // gr->mat[b][a] = 1;  // il grafo non è orientato
}

void walk(graph *gr, int i) {
  int j;
  
  if(gr->walk[i] == -1) {
    gr->walk[i] = view;
    view++;
  }

  for(j=i; j<gr->nV; j++) {
    if(gr->mat[i][j] == 1) {
      walk(gr, j);
    }
  }
}

void print_gr(graph *gr, int cmd) {
  int i, j;

  if(cmd == 1) {
    printf("\nLista nodi (%d):\n", gr->nL);
    for(i=0; i<gr->nV; i++) {
      printf("Nodo %d - Valore %d - Visitato %d\n", i, gr->value[i], gr->walk[i]);
    }
  }
  else if(cmd == 2) {
    printf("\nMatrice di adiacenza:\n");
  
    for(i=0; i<gr->nV; i++) {
      for(j=0; j<gr->nV; j++) {
        printf("%3d", gr->mat[i][j]);
      }
      printf("\n\n");
    }
  }
}

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