Gli esercizi

Testi e soluzioni di alcuni esercizi

Algoritmo di Kruskal per la costruzione dell'albero ricoprente di peso minimo

/*
**  kruskal.c
**
**  Letto in input un grafo non orientato, con pesi non
**  negativi associati ad ogni spigolo, produce in output
**  l'albero ricoprente con peso minimo (minimum spanning
**  tree).
**
**  Pseudo-codifica dell'algoritmo:
**
**  Kruskal(G, W)
**  1. per ogni vertice v di G: MakeSet(v)
**  2. ordina gli archi di G in ordine non decrescente
**     di peso w(u,v).
**  3. per ogni arco (u,v) di G, scelto in ordine non decrescente
**     di peso, ripeti il passo 4:
**  4.   se FindSet(u) != FindSet(v) allora aggiungi lo spigolo
**       (u,v) all'albero T, Union(u,v).
**  5. restituisci T
**  End
**
**  MakeSet(v)
**  1. Insieme(v) = {v}
**  2. Rappresentante(v) = v
**  End
**
**  Union(u,v)
**  1. Insieme(u) = Insieme(u) U Insieme(v)
**  2. per ogni vertice z appartenente a Insieme(v):
**     Rappresentante(z) = Rappresentante(u)
**  End
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Dicembre 2007
*/

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

#define MAX 100

/*
 *  La struttura "nodo" viene utilizzata per rappresentare
 *  gli elementi delle liste di adiacenza del grafo.
 */
struct nodo {
  int info;
  struct nodo *next;
};

/*
 *  La struttura "elemento" viene utilizzata per memorizzare
 *  gli elementi della lista con cui vengono rappresentati
 *  gli insiemi.
 */
struct elemento {
  int info, rap;
  struct elemento *next;
};

/*
 *  La struttura "arco" viene utilizzata per memorizzare in
 *  una lista gli archi del grafo ed i pesi assocati a tali archi.
 */ 
struct arco {
  int v1, v2, w;
  struct arco *next;
};

/*
 *  Ordina in modo non decrescente gli elementi della lista
 *  indirizzata dal puntatore e, sulla base dei campi w (il peso
 *  associato ad un arco) dei nodi.
 */ 
void bubble_sort(struct arco *e) {
  int flag, x, y, z;
  struct arco *a;

  flag = 1;
  while (flag == 1) {
    flag = 0;
    a = e;
    while (a->next != NULL) {
      if (a->w > (a->next)->w) {
        x = a->w;
        y = a->v1;
        z = a->v2;

        a->w = (a->next)->w;
        a->v1 = (a->next)->v1;
        a->v2 = (a->next)->v2;

        (a->next)->w = x;
        (a->next)->v1 = y;
        (a->next)->v2 = z;
        flag = 1;
      }
      a = a->next;
    }
  }
  return;
}

/*
 *  Crea un insieme (una lista) con un unico
 *  elemento (u). Restituisce il puntatore al
 *  primo (ed unico) elemento della lista.
 */ 
struct elemento *MakeSet(int u) {
  struct elemento *a;

  a = malloc(sizeof(struct elemento));
  a->info = u;
  a->next = NULL;
  a->rap = u;
  return(a);
}

/*
 *  Esegue l'unione dell'insieme che contiene u
 *  (la lista indirizzata da A[u]) e quello
 *  contenente v (la lista puntata da A[v]).
 */ 
void Union(int u, int v, struct elemento *A[]) {
  struct elemento *a, *secondo;
  int ru, rv;

  ru = A[u]->rap;
  rv = A[v]->rap;
  secondo = A[ru]->next;
  A[ru]->next = A[rv];
  a = A[rv];
  while (a != NULL) {
    a->rap = ru;
    if (a->next == NULL) {
      a->next = secondo;
      a = NULL;
    } else {
      a = a->next;
    }
  }
  return;
}

/*
 *  Restituisce il rappresentante dell'insieme a cui 
 *  appartiene l'elemento x.
 */ 
int FindSet(struct elemento *A[], int x) {
  return(A[x]->rap);
}

/*
 *  Esegue la costruzione del minimo albero ricoprente.
 *  Non restituisce nulla, ma costruisce le liste di adiacenza
 *  dell'albero, indirizzate dai puntatori dell'array T[]
 *  ricevuto come parametro.
 */ 
void kruskal(struct nodo *G[], int n, struct arco *e, struct nodo *T[]) {
  struct nodo *v;
  struct elemento *A[MAX];
  int u;

  for (u=0; u<n; u++)
    T[u] = NULL;

  for (u=0; u<n; u++)
    A[u] = MakeSet(u);

  bubble_sort(e);

  while (e != NULL) {
    if (FindSet(A, e->v1) != FindSet(A, e->v2)) {
      v = malloc(sizeof(struct nodo));
      v->info = e->v1;
      v->next = T[e->v2];
      T[e->v2] = v;

      v = malloc(sizeof(struct nodo));
      v->info = e->v2;
      v->next = T[e->v1];
      T[e->v1] = v;

      Union(e->v1, e->v2, A);
    }
    e = e->next;
  }
  return;
}

/*
 *  Stampa le liste di adiacenza indirizzate dall'array
 *  di puntatori l[].
 */ 
void stampa_liste(struct nodo *l[], int n) {
  struct nodo *p;
  int i;

  for (i=0; i<n; i++) {
    printf("%2d: ", i);
    p = l[i];
    while (p != NULL) {
      printf("%d -> ", p->info);
      p = p->next;
    }
    printf("NULL\n");
  }
  return;
}

/*
 *  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 i, n, x;

  primo = NULL;
  scanf("%d", &n);
  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 *l[]) {
  int i, n;

  printf("Numero di vertici del grafo: ");
  scanf("%d", &n);
  for (i=0; i<n; i++) {
    printf("Lista di adiacenza del vertice %d: ", i);
    l[i] = leggi_lista();
  }
  return(n);
}


/*
 *  Funzione principale: legge in input il grafo, legge
 *  in input i pesi associati agli spigoli e li memorizza
 *  in una lista. Quindi richiama la funzione Kruskal per
 *  il calcolo dello spanning tree di peso minimo e ne
 *  stampa le liste di adiacenza.
 */ 
int main(void) {
  int i, n, x;
  struct nodo *p, *G[MAX], *T[MAX];
  struct arco *e, *WE;

  /* Legge in input le liste di adiacenza del grafo G */
  n = leggi_grafo(G);
  
  /* Legge in input i pesi associati ad ogni spigolo di G */
  WE = NULL;
  for (i=0; i<n; i++) {
    p = G[i];
    while (p != NULL) {
      printf("w(%d,%d): ", i, p->info);
      scanf("%d", &x);
      e = malloc(sizeof(struct arco));
      e->w = x;
      e->v1 = i;
      e->v2 = p->info;
      e->next = WE;
      WE = e;
      p = p->next;
    }
  }
  stampa_liste(G, n);
  kruskal(G, n, WE, T);
  printf("E' stato trovato il seguente spanning-tree:\n");
  stampa_liste(T, n);
  return(0);
}