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);
}