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