Corso di Informatica 1 (IN110)

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

Author: Marco Liverani - Last modified: Monday October 24, 2016 - URI: http://www.mat.uniroma3.it/users/liverani/IN110/kruskal.shtml