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