LabASD - Visita in ampiezza (BFS)

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-05-20

Realizziamo l'algoritmo di visita in ampiezza (Breadth-First Search, BFS) di un grafo orientato \(G=(V,E)\) con \(n\) nodi e \(m\) archi. La visita in ampiezza inizia da un nodo sorgente \(s\) e procede "per livelli": prima si visitano tutti i nodi adiacenti a \(s\), poi tutti i nodi adiacenti a quelli adiacenti, e così via.

In questa pagina è presente una interessante visualizzazione dell'algoritmo BFS mentre esplora un labirinto (che può essere descritto tramite un grafo).

Al termine della visita, l'algoritmo riempie due array p[] e d[], entrambi di \(n\) elementi, con le seguenti informazioni:

L'algoritmo BFS richiede l'uso di una coda FIFO in cui inserire i nodi da visitare. In una coda FIFO il primo elemento inserito è anche il primo ad essere estratto. Viene fornita una implementazione nei file queue.h e queue.c; è anche possibile utilizzare la struttura List già vista in una precedente esercitazione.

La struttura Queue è basata su un array circolare che viene automaticamente espanso e contratto in base al numero di elementi effettivamente presenti. Tale struttura supporta l'inserimento e la rimozione dalle estremità in tempo \(O(1)\) ammortizzato; la struttura List fa uso di puntatori, e supporta l'inserimento e la rimozione dalle estremità in tempo \(O(1)\) nel caso pessimo.

Se si vuole usare la struttura Queue, le funzioni utili per questo esercizio sono:

queue_init(Queue *q)

Inizializza la coda

queue_destroy(Queue *q)

Libera tutta la memoria occupata dalla coda

queue_enqueue(Queue *q, int val)

Inserisce val in fondo alla coda

int queue_dequeue(Queue *q)

Rimuove e restituisce l'elemento in testa alla coda.

int queue_is_empty(const Queue *q)

Restituisce 1 se la coda è vuota

Questo programma deve accettare uno o due parametri sulla riga di comando. Il primo parametro (obbligatorio) indica il nodo sorgente da cui far partire la visita. Il secondo parametro (facoltativo) indica il nome del file contenente il grafo da visitare; se manca, il grafo viene letto da standard input.

Per compilare:

    gcc -std=c90 -Wall -Wpedantic queue.c graph.c bfs.c -o bfs

Per eseguire:

    ./bfs 0 < graph100.in

oppure

    ./bfs 0 graph100.in

dove al posto di 0 si può indicare l'indice di qualunque altro nodo da usare come sorgente.

Curiosità

La visita in ampiezza può essere applicata all'analisi del grafo delle mosse di un gioco da tavolo, per determinare il numero minimo di mosse necessarie a vincere, o se esiste una strategia vincente. Un risultato interessante è stato ottenuto nel 2007 quando un gruppo di ricercatori ha completato l'analisi del gioco della dama, che ha circa \(5 \times 10^{20}\) configurazioni valide (che corrispondono a nodi del grafo). È stato così dimostrato che, se entrambi i giocatori giocano in modo "perfetto", il risultato è un pareggio. "The Atlantic" ha un articolo non tecnico che discute questo risultato.

Usando la visita in ampiezza dell'albero delle mosse valide, è possibile rispondere alle questioni rimaste in sospeso sul gioco shooting stars: qual è il minimo numero di mosse necessarie per vincere? esistono configurazioni della griglia di gioco che non possono essere ottenute da quella iniziale?

File