Gli esercizi

Testi e soluzioni di alcuni esercizi

Algoritmo DFS per la visita in profondità di un grafo

/*
**  dfs.c
**
**  Letto in input un grafo orientato, rappresentarlo
**  mediante liste di adiacenza. Esegue la visita in
**  profondita' del grafo mediante l'algoritmo DFS
**  (Depth First Search).
**
**  Pseudo-codifica dell'algoritmo:
**
**  DFS(G)
**    per ogni vertice u di V(G) ripeti:
**      colore(u) = bianco
**      padre(u) = NULL
**    per ogni vertice u di V(G) ripeti:
**      se colore(u)=bianco allora VISITA(G, u)
**  End
**
**  VISITA(G, u)
**    colore(u) = grigio
**    per ogni vertice v adiacente ad u ripeti:
**      se colore(v)=bianco allora:
**        padre(v) = u
**        VISITA(G, v)
**    colore(u) = nero
**  End
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Maggio 2001
**
*/

/*
 *  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.
 */
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 *leggi_lista(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 leggi_grafo(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] = leggi_lista();
  }
  return(n);
}

/*
 *  Visita il grafo G a partire dal vertice u, con un algoritmo
 *  ricorsivo.
 */
void visita(int u, struct nodo *l[], int colore[], int pi[]) {
  struct nodo *p;
  colore[u] = 1;
  p = l[u];
  while (p != NULL) {
    if (colore[p->info] == 0) {
      pi[p->info] = u;
      visita(p->info, l, colore, pi);
    }
    p = p->next;
  }
  return;
}

/*
 *  Funzione principale: innesca la ricorsione chiamando
 *  la funzione visita.
 */
int main(void){
  int i, n, colore[MAX], pi[MAX];
  struct nodo *lista[MAX];
  n = leggi_grafo(lista);
  for (i=0; i<n; i++) {
    colore[i] = 0;
    pi[i] = -1;
  }
  for (i=0; i<n; i++)
    if (colore[i] == 0)
      visita(i, lista, colore, pi);
  printf("La visita ha generato il seguente albero DFS:\n");
  for (i=0; i<n; i++) {
    printf("Vertice %d: padre=%d\n", i, pi[i]);
  }
  return(0);
}