Gli esercizi

Testi e soluzioni di alcuni esercizi

Algoritmo BFS per la visita in ampiezza di un grafo

/*
**  bfs.c
**
**  Implementazione dell'algoritmo BFS (Breadth First Search)
**  per la visita in ampiezza di un grafo.
**
**
**  Pseudo-codifica dell'algoritmo:
**
**  per ogni vertice u di G diverso dalla sorgente s ripeti:
**    colore(u) = bianco
**    d(u) = infinito
**    pi(u) = null
**  end
**
**  colore(s) = grigio
**  d(s) = 0
**  pi(s) = null
**
**  Q = {s}
**
**  fintanto che la coda Q non e` vuota ripeti:
**    sia u il primo elemento estratto dalla coda Q
**    per ogni vertice v adiacente ad u ripeti:
**      se colore(v) = bianco allora
**        colore(v) = grigio
**        d(v) = d(u) + 1
**        pi(v) = u
**        aggiungi v alla coda Q
**      end
**    end
**    colore(u) = nero
**  end
**
**  Marco Liverani (liverani@mat.uniroma3.it)
**
*/

/*
 *  inclusione delle librerie
 */
#include <stdlib.h>
#include <stdio.h>

/*
 *  definizione della costante che indica la massima dimensione
 *  del grafo (|V|<MAX).
 */
#define MAX 100

/*
 *  definizione della struttura utilizzata per rappresentare i
 *  vertici del grafo nelle liste di adiacenza ed i nodi della
 *  coda Q.
 */
struct nodo {
  int info;
  struct nodo *next;
};

/*
 *  Legge in input una sequenza di n interi e li memorizza su
 *  una lista. Restituisce il puntatore al primo elemento della lista.
 */
struct nodo *leggiLista(void) {
  struct nodo *p, *primo;
  int x, n, i;
  printf("Numero di elementi nella lista: ");
  scanf("%d", &n);
  primo = NULL;
  for (i=0; i<n; i++) {
    scanf("%d", &x);
    p = malloc(sizeof(struct nodo));
    p->info = x;
    p->next = primo;
    primo = p;
  }
  return(primo);
}

/*
 *  Legge in input le n liste di adiacenza (una per ogni
 *  vertice del grafo G). Restituisce il numero di vertici
 *  di cui e' costituito il grafo e l'array di puntatori
 *  ai primi elementi di ogni lista di adiacenza.
 */
int leggiGrafo(struct nodo *lista[]) {
  int i, n;
  printf("Numero di vertici: ");
  scanf("%d", &n);
  for (i=0; i<n; i++) {
    printf("Lista di adiacenza del vertice %d.\n", i);
    lista[i] = leggiLista();
  }
  return(n);
}

/*
 *  accoda
 *
 *  aggiunge un nodo alla coda Q; "primo" punta la primo elemento,
 *  "ultimo" punta all'ultimo elemento della coda.
 */
void accoda(struct nodo **primo, struct nodo **ultimo, int x) {
  struct nodo *p;
  p = malloc(sizeof(struct nodo));
  p->info = x;
  p->next = NULL;
  if (*primo == NULL)
    *primo = p;
  if (*ultimo != NULL)
    (*ultimo)->next = p;
  *ultimo = p;
  return;
}

/*
 *  estrai
 *
 *  restituisce il primo elemento della coda e lo elimina dalla coda stessa.
 */
int estrai(struct nodo **primo, struct nodo **ultimo) {
  int r;
  if (*primo == NULL) {
    r = -1;
  } else {
    r = (*primo)->info;
    *primo = (*primo)->next;
  }
  return(r);
}

/*
 *  bfs
 *
 *  visita in ampiezza del grafo rappresentato tramite le liste di
 *  adiacenza l[0], ..., l[n-1]; la visita parte dal vertice s.
 */
void bfs(struct nodo *l[], int n, int d[], int pi[], int s) {
  struct nodo *primo, *ultimo, *v;
  int colore[MAX], i, u;
  primo = NULL;
  ultimo = NULL;
  for (i=0; i<n; i++) {
    colore[i] = 0;
    d[i] = -1;
    pi[i] = -1;
  }
  colore[s] = 1;
  d[s] = 0;
  accoda(&primo, &ultimo, s);
  while (primo != NULL) {
    u = estrai(&primo, &ultimo);
    v = l[u];
    while (v != NULL) {
      if (colore[v->info] == 0) {
        colore[v->info] = 1;
        d[v->info] = d[u] + 1;
        pi[v->info] = u;
        accoda(&primo, &ultimo, v->info);
      }
      v = v->next;
    }
    colore[u] = 2;
  }
  return;
}

/*
 *  Funzione principale.
 */
int main(void){
  int i, n, d[MAX], pi[MAX], sorgente;
  struct nodo *lista[MAX];
  n = leggiGrafo(lista);
  printf("Sorgente della visita: ");
  scanf("%d", &sorgente);
  bfs(lista, n, d, pi, sorgente);
  for (i=0; i<n; i++) {
    printf("Vertice %d: padre=%d, distanza=%d\n", i, pi[i], d[i]);
  }
  return(0);
}