Algoritmi e strutture dati - Appunti completi

Rappresentazione di grafi sparsi

Ciò è particolarmente conveniente nel caso di grafi sparsi, cioè grafi per i quali il numero di archi è molto inferiore al numero di vertici. Per contro, il tempo per verificare l'esistenza di un arco tra due vertici dati è O(|V| + |E|) nel caso pessimo (il vertice di partenza è l'ultimo della lista primaria, tutti gli archi del grafo escono da questo vertice e l'arco in questione non esiste).

Un'altra possibile rappresentazione è quella a matrice di adiacenza, una matrice che ha tante righe e tante colonne quanti sono i vertici. L'elemento di indici i e j vale 1 (risp. d) se esiste un arco dal vertice i al vertice j (di peso d), 0 altrimenti:

double grafo[NUMERO_VERTICI][NUMERO_VERTICI];

Dato un grafo G = (V, E), la sua rappresentazione mediante matrice di adiacenza consente la verifica dell'esistenza di un arco tra due vertici dati in un tempo che è O(1). Per contro, l'occupazione di memoria è O(|V|), che non è conveniente nel caso di grafi densi.

caratteristica di comprendere tutti (e soli) i vertici che sono raggiungibili dal vertice di partenza

Non è detto che si possono sempre raggiungere tutti i vertici

Per raggiungere ogni vertice, bisogna ripetere l'attraversamento tante volte quante sono le componenti connesse del grafo

I vertici sono colorati per garantire la terminazione (in caso di cicli):

• bianco - vertici mai visitati
• grigio - vertici visitati per la prima volta
• nero - se i vertici adiacenti sono stati visitati

Visita in ampiezza (BFS)

I vertici sono attraversati in ordine di distanza crescente dal vertice di partenza

Numero di archi

Gli archi sono tutti ispezionati per scoprire tutti i vertici che sono raggiungibili dal nodo preso come sorgente.

La frontiera tra i vertici "scoperti" e quelli da "scoprire" viene espansa in maniera uniforme

prima di scoprire i vertici a distanza k+1, vengono scoperti tutti quelli a distanza k

I vertici neri hanno come adiacenti solo

vertici grigi oppure neri.I vertici grigi sono la frontiera tra quelli scoperti e da scoprire.Ogni vertice v è raggiungibile da s (vertice sorgente) raggiungibile tramite un camminominimo (percorso più breve).

Pseudocodice:

Algorithm BFS(G, s)
1 for ogni vertice u V[G] – s do∈
2 color[u] = bianco
3 d[u] = ∞
4 end for
5 color[s] = grigio
6 d[s] = 0
7 Q←
8 metti_in_cosa(Q, s)
9 while Q ≠ 0 do
10 u ← togli_da_coda(Q)
11 for ogni v Adj[u] do∈
12 if color[v] = bianco then
13 color[v] = grigio
14 d[v] = d[v] + 1
15 metti_in_coda(Q, v)
16 end if
17 end for
18 color[u] = nero
19 end while

Spiegazione:

1. per ogni vertice u che non è il nodo sorgente, esegui il seguente blocco di istruzioni.
2. assegna il colore "bianco" al nodo u. Inizialmente tutti i nodi, tranne il nodo sorgente, vengono colorati di bianco.
3. assegna al nodo u una distanza infinita. Questo valore verrà successivamente aggiornato durante la visita.
4. fine del ciclo for.
5. colora il nodo sorgente di grigio.
6. assegna al nodo sorgente una distanza di 0.
7. crea una coda vuota Q.
8. aggiungi il nodo sorgente alla coda Q.
9. finché la coda Q non è vuota, esegui il seguente blocco di istruzioni.
10. rimuovi un nodo u dalla coda Q.
11. per ogni nodo v adiacente a u, esegui il seguente blocco di istruzioni.
12. se il colore di v è bianco, esegui il seguente blocco di istruzioni.
13. colora il nodo v di grigio.
14. aggiorna la distanza di v incrementandola di 1.
15. aggiungi il nodo v alla coda Q.
16. fine del blocco if.
17. fine del ciclo for.
18. colora il nodo u di nero.
19. fine del ciclo while.

1. assegna il colore "grigio" al nodo sorgente. Questo indica che il nodo è stato scoperto ma non ancora completamente esplorato.
2. assegna una distanza di 0 al nodo sorgente.
3. inizializza una coda Q vuota, che verrà utilizzata per mantenere traccia dei nodi da visitare.
4. inserisce il nodo sorgente nella coda Q.
5. finché la coda Q non è vuota, esegui il seguente blocco di istruzioni.
6. rimuove il primo elemento dalla coda Q e lo assegna al nodo u, che diventa il nodo corrente da esplorare.
7. per ogni nodo v adiacente al nodo u, esegui il seguente blocco di istruzioni.
8. se il nodo v non è stato ancora scoperto, esegui il seguente blocco di istruzioni.
9. assegna il colore "grigio" al nodo v, indicando che è stato scoperto ma non ancora completamente esplorato.
10. incrementa la distanza del nodo v di una unità rispetto alla distanza del nodo u.
11. inserisce il nodo v nella coda Q per esplorarlo successivamente.
12. fine dell'if.

fine del ciclo for sui nodi adiacenti a u.
18. assegna il colore "nero" al nodo u, indicando che è stato completamente esplorato.
19. fine del ciclo while.

Codice:

typedef enum {bianco, grigio, nero} colore_t;
typedef struct vertice_grafo {
    int valore;
    struct vertice_grafo *vertice_succ_p;
    struct arco_grafo *lista_archi_p;
    colore_t colore;
    int distanza;
    struct vertice_grafo *padre_p;
} vertice_grafo_t;

void avvia_visita_grafo_amp (vertice_grafo_t *grafo_p) {
    vertice_grafo_t *verifica_p;
    for(vertice_p = grafo_p; vertice_p != NULL; vertice_p = vertice_p -> vertice_succ_p){
        vertice_p -> colore = bianco;
        vertice_p -> distanza = -1;
        vertice_p -> padre_p = NULL;
    }
    for(vertice_p = grafo_p; vertice_p != NULL; vertice_p = vertice_p -> vertice_succ_p){
        if (vertice_p -> colore == bianco)
            visita_grafo_amp(vertice_p);
    }
}

void visita_grafo_amp(vertice_grafo_t *vertice_partenza_p){
    vertice_grafo_t *vertice_p;
    arco_grafo_t *arco_p;
    elem_lista_vertici_t *uscita_p,

ingresso_p;vertice_partenza_p -> colore = grigio;vertice_partenza_p -> distanza = 0;uscita_p = ingresso_p = NULL;metti_in_coda(&uscita_p, &ingresso_p, vertice_partenza_p);while (uscita_p != NULL){ vertice_p = togli_da_coda(&uscita_p, &ingresso_p) -> valore;elabora(vertice_p -> valore);for (arco_p = vertice_p->lista_archi_p;arco_p != NULL;arco_p = arco_p -> arco_succ_p) {if (arco_p -> vertice_adiac_p -> colore == bianco){ arco_p -> vertice_adiac_p -> colore = grigio;arco_p -> vertice_adiac_p -> distanza = vertice_p -> distanza+ 1; arco_p->vertice_adiac_p -> padre_p = vertice_p;metti_in_coda(&uscita_p,&ingresso_parco_p -> vertice_adiac_p);}vertice_p->colore = nero;}}}

Il codice implementa l'algoritmo di visita in ampiezza (BFS) su un grafo rappresentato con una lista di adiacenza. L'algoritmo visita tutti i nodi del grafo a partire da un nodo di partenza, visitando tutti i nodi a distanza 1 dal nodo di partenza.

Poi tutti i nodi a distanza 2, e così via, fino a visitare tutti i nodi del grafo. L'algoritmo utilizza una coda (Q) per tenere traccia dei nodi da visitare, inizializzata con il nodo di partenza. L'algoritmo BFS utilizza una variabile distanza per tenere traccia della distanza tra il nodo di partenza e gli altri nodi del grafo. Durante la visita, la distanza viene incrementata ogni volta che viene visitato un nuovo nodo. Inoltre, ogni nodo viene contrassegnato con uno dei tre colori: bianco, grigio e nero. Un nodo bianco è un nodo che non è ancora stato visitato, un nodo grigio è un nodo che è stato visitato ma i suoi vicini non sono ancora stati visitati, e un nodo nero è un nodo che è stato completamente visitato (cioè tutti i suoi vicini sono stati visitati). La visita inizia impostando tutti i nodi del grafo al colore bianco, eccetto il nodo di partenza che viene impostato al colore grigio. Il ciclo while estrae un nodo dalla coda Q e lo contrassegna come nero. Successivamente, vengono visitati tutti i vicini del nodo estratto che sono ancora bianchi, contrassegnandoli come grigi e inserendoli nella coda Q. Questo processo viene ripetuto finché la coda Q non è vuota, cioè finché tutti i nodi sono stati visitati.

coda (Q) e visita tutti i suoi vicini. Se il vicino non è stato ancora visitato (colore bianco), viene aggiunto alla coda(Q) e contrassegnato come nodo grigio. La distanza del vicino viene impostata a quella del nodo corrente più 1. Il ciclo continua finché la coda (Q) non è vuota, ovvero finché non sono stati visitati tutti i nodi del grafo.

Il codice è suddiviso in due funzioni. La prima funzione, avvia_visita_grafo_amp, inizializza il grafo e richiama la seconda funzione, visita_grafo_amp, per visitare ogni nodo bianco del grafo. La seconda funzione, visita_grafo_amp, visita il grafo a partire dal nodo passato come parametro. Durante la visita, la funzione utilizza una coda (implementata come una lista collegata) per tenere traccia dei nodi da visitare. La funzione elabora() viene chiamata su ogni nodo visitato. In questo pseudocodice, la funzione elabora() non è definita, ma rappresenta l'azione che deve essere eseguita su ogni nodo visitato.