Algoritmo generico di visita di grafi (orientati o non orientati)
a partire da un vertice sorgente

    VISITA (G, s)
    color [s] ¬ GRAY
    while ci sono vertici grigi do
            scegli un vertice grigio u
            if esiste un vertice bianco v Î Adj[u]
                     then color [v] ¬ GRAY
                     else color [u] ¬ BLACK
 

Prima di eseguire questa procedura, occorre inizializzare il grafo con la seguente procedura:
 

    INIZIALIZZA (G)
    for ogni vertice u Î V[G] do
             color [u] ¬ WHITE
 

Proprietà:

1. Al termine dell'esecuzione di VISITA (G,s) tutti i vertici sono o WHITE o BLACK.
2. Il colore di un vertice può solo passare da WHITE a GRAY a BLACK

Invarianti del while:

 INV1: Se (u,v) Î E[G] e u è nero, allora v è o grigio o nero.

 INV2: Tutti i vertici grigi o neri sono raggiungibili da s.

 INV3: Qualunque cammino da s a un vertice bianco deve contenere almeno un vertice grigio.

Dimostrazione.
Se s è grigio: vero. Se s è nero: se non ci fosse nessun vertice grigio ci sarebbe un vertice bianco adiacente ad uno nero, che è impossibile per l'invariante INV1.
 

TEOREMA. Al termine dell'algoritmo di visita, un vertice è nero se e solo se è raggiungibile da s.

Dimostrazione.
(Þ) Per INV2 all'uscita del while tutti i vertici neri sono raggiungibili da s.
(Ü) Da INV3 e dalla condizione di uscita del ciclo (non ci sono vertici grigi) si ricava che non ci può essere nessun vertice bianco raggiungibile da s.

    VISITA (G, s)
    color [s] ¬ GRAY
    while ci sono vertici grigi do
            scegli un vertice grigio u
            if esiste un vertice bianco v Î Adj[u]
                then color [v] ¬ GRAY
                        p [v] ¬ u
                else color [u] ¬ BLACK
 

La procedura di inizializzazione deve essere estesa per inizializzare p:

     INIZIALIZZA (G)
        for ogni vertice u Î V[G] do
        color [u] ¬ WHITE
        p [u] ¬ NIL
 

Invariantedel while:

 INV4: Tutti i vertici u grigi o neri, u ¹ s, hanno p[u] ¹ NIL

Proprietà: Al termine dell'esecuzione di VISITA (G,s) ad ogni vertice nero diverso da s è associato un predecessore non NIL.
 

Sottografo dei predecessori Gp = (Vp, Ep):

         Vp = {v Î V: p[v] ¹ NIL} È {s}

         Ep = {(p[v], v) Î E: v Î Vp -{s}}

Si noti che, come conseguenza immediata della Proprietà 2, al termine dell'esecuzione di VISITA (G,s) Vp è l'insieme di tutti i vertici neri, cioè di tutti i vertici raggiungibili da s.

TEOREMA. Il sottografo dei predecessori costruito dall'algoritmo di visita è  un albero.

Dimostrazione.
Basta dimostrare che è invariante del while la seguente proprietà: (Vp, Ep) è connesso e |Ep| = |Vp| - 1.

In certe applicazioni può essere necessario visitare tutti i vertici di un grafo. Questo può essere fatto con la seguente procedura:

       VISITA-TUTTI-I-VERTICI (G)
       INIZIALIZZA (G)
       for ogni vertice u Î V[G] do
            if color [u] = WHITE
                    then VISITA (G,u)
 

Per gestire l'insieme dei vertici grigi in modo efficiente, si può utilizzare una struttura dati D i cui elementi siano ordinati, e su cui sono definite le operazioni:

    make_empty crea una struttura vuota

    first (D) restituisce il primo elemento di D (senza modificare D)

    add (D, x) aggiunge l'elemento x a D

    remove-first (D) toglie da D il primo elemento

    not_empty (D) restituisce true se D non è vuota e false altrimenti
 

Se add (D,x) aggiunge x come primo elemento di D, D è una PILA (STACK); altrimenti, se add (D,x) aggiunge x come ultimo elemento di D, D è una CODA.
 

L'algoritmo diventa:

    VISITA (G, s)
    color [s] ¬ GRAY
    D ¬ make_empty
    add (D,s)
    while not_empty (D) do
            u ¬ first (D)
    (*)    if esiste un vertice bianco v Î Adj[u]
                    then color [v] ¬ GRAY
                            p [v] ¬ u
                            add (D, v)
                    else color [u] ¬ BLACK
                            remove-first (D)
 
 
 

Se la struttura dati D è una coda, il vertice scelto è quello grigio da più tempo: la visita si chiama in ampiezza; se D è una pila si sceglie il vertice diventato grigio per ultimo: la visita si chiama in profondità.

 Le operazioni first, add, remove-first diventano rispettivamente

 CODA: head (Q) enqueue (Q, x) dequeue (Q)

 STACK: top (S) push (S, x) pop (S)
 
 

COMPLESSITA'

Per analizzare la complessità occorre specificare come viene implementato il punto (*) dell'algoritmo di visita. Ad esempio si potrebbe realizzare l'if con un ciclo che percorre la lista di adiacenza di u fino a trovare il primo vertice bianco, se c'è. Con questa realizzazione le liste di adiacenza possono essere percorse più volte, perché, ogni volta che si estrae u dalla struttura D, la lista di adiacenza di u viene percorsa dall'inizio.

Sappiamo però dalla proprietà 1 che un vertice grigio o nero non può ridiventare bianco. Grazie a questa proprietà, è facile vedere che non è necessario scandire ogni volta la lista di adiacenza di u dall'inizio, ma è sufficiente ricordarsi ogni volta dove si è arrivati a scandirla e ripartire da lì la volta successiva. Questo può essere realizzato facilmente associando ad ogni vertice il valore corrente del puntatore alla lista degli adiacenti. In questo modo si ottiene una implementazione più efficiente perché le liste di adiacenza vengono percorse al massimo una volta.
 

Analisi della complessità:

Nel caso della visita in ampiezza si vede che la head della coda non cambia finché ci sono adiacenti bianchi. Quindi l'algoritmo può essere modificato come nel libro.

    BFS-VISIT (G, s)
    Q ¬ make_empty
    color [s] ¬ GRAY
    enqueue (Q,s)
    while not_empty (Q) do
            u ¬ head (Q)
            while esiste un vertice non considerato v Î Adj[u] do
                    if color [v] = WHITE
                        then color [v] ¬ GRAY
                                p [v] ¬ u
                                enqueue (Q, v)
            color [u] ¬ BLACK
            dequeue (Q)
 

Durante l’esecuzione di BFS-VISIT, in Q ci sono tutti e soli i vertici grigi.
 

Introduciamo per ogni vertice v l’attributo d[v], che associa a v il suo livello nell’albero ottenuto da una visita in ampiezza a partire dal sorgente s, radice dell’albero. Riscriviamo perciò la BFS-VISIT introducendo l’attributo d, nell’ipotesi che INIZIALIZZA (G) inizializzi d[v] ad ¥ per ogni vertice v del grafo.

    BFS-VISIT (G, s)
    Q ¬ make_empty
    color [s] ¬ GRAY
    d[s] ¬0
    enqueue (Q,s)
    while not_empty (Q) do
            u ¬ head (Q)
            while esiste un vertice non considerato v Î Adj[u] do
                    if color [v] = WHITE
                        then color [v] ¬ GRAY
                                p [v] ¬ u
                                d[v] ¬ d[u] + 1
                                enqueue (Q, v)
            color [u] ¬ BLACK
            dequeue(Q)
 

Nel seguito si dimostra che il livello di v nell’albero (d[v]) è la distanza di v da s  ( d (s,v)), cioè la lunghezza di un cammino minimo da s a v nel grafo G.
 

Invarianti dei due while:

INV4: Se <v₁, v₂, . . . , v_n> è il contenuto di Q, allora:     d[v_n] £ d[v₁] + 1  e
                                                                                         d[v_i] £ d[v_i+1],  1 £ i £ n-1
 

INV5: Durante l'esecuzione della procedura BFS si ha d[v] = d(s,v) per tutti i vertici v grigi o neri.
 

Dimostrazione
a) Per il while esterno:

- INV5 è vero quando il while viene raggiunto la prima volta, in quanto l’unico vertice grigio è s e d[s] = 0 = d (s,s).

INV5 viene mantenuto vero dal corpo del while:

        { INV5}
        while not_empty (Q) do
            u ¬ head (Q)
            { INV5}
            while esiste un vertice non considerato v Î Adj[u] do
                       . . .
                       . . .
            color [u] ¬ BLACK
            dequeue (Q)
        { INV5}

Supponendo che il while interno mantenga vero INV5 si tratta di dimostrare:

     (1)  {INV5}
            color [u] ¬ BLACK
            dequeue (Q)
     (2)  {INV5}
 

In (1) u è grigio e d[u] = d (s,u), poichè d[u] non viene modificato, u diventa nero mantenendo l’uguaglianza d[u] = d (s,u). Per gli altri vertici grigi e neri l’uguaglianza continua a valere, per cui INV5 è vero in (2).

 b) Per il while interno:

- Poichè INV5 è un invariante del while esterno è sempre vero quando il while interno viene raggiunto.

- INV5 viene mantenuto dal corpo del while, cioè:

        {INV5}
          while esiste un vertice non considerato v Î Adj[u] do
                if color [v] = WHITE
                        then color [v] ¬ GRAY
                                p [v] ¬ u
                                d[v] ¬ d[u] + 1
                                enqueue (Q, v)

        {INV5}

v è l’unico vertice che cambia colore; basta dimostrare che l’assegnazione d[v] ¬ d[u] + 1 rende d[v] = d (s,v).
Consideriamo in G un cammino minimo da s a v. Per l’invariante INV3 tale cammino contiene almeno un vertice t grigio. Il cammino minimo può allora essere visto come concatenazione dei due cammini minimi da s a t e da t a v.
d (s,v) = d (s,t) + d (t,v) ³d (s,t) + 1 (d (t,v) ³ 1 poichè t ¹ v).
Ma il vertice t è in Q (t è grigio) e per l’invariante INV4, essendo u = head(Q): d[u] £ d[t] = d (s,t).
Si ottiene pertanto: d (s,v) ³ d (s,t) + 1 = d[t] + 1 ³ d[u] + 1.
Poichè s - - - u ® v è un cammino in G da s a v, non può avere lunghezza minore di quella di un cammino minimo, allora d (s,v) = d[u] + 1 e l’assegnazione d[v] ¬ d[u] + 1 rende d[v] = d (s,v).

Dimostrazione.
Se v non è raggiungible da s allora il suo costo rimane ¥ . Altrimenti v è nero e il teorema vale per il Lemma precedente.

Visita in profondità
 

Nel caso della visita in profondità si nota che, se si segue il ramo then, lo stack non può essere vuoto al passo successivo e quindi si può evitare il test del while. L'algoritmo può essere modificato come segue:
 

    DFS-iter (G, s)
    color [s] ¬ GRAY
    S ¬ make_empty
    push (S,s)
    while not_empty (S) do
            while esiste un vertice bianco v Î Adj [TOP(S)] do
                    color [v] ¬ GRAY
                    p [v] ¬ TOP(S)
                    PUSH (S, v)
            color [TOP(S)] ¬ BLACK
            POP (S)
 

Si può anche fornire una versione ricorsiva dell'algoritmo:
 

    DFS-visit (G,u)
    color [u] ¬ GRAY
    for ogni v Î Adj [u] do
            if color [v] = WHITE
                then p [v] ¬ u
                        DFS-visit (G,v)
    color [u] ¬ BLACK
 
 

Si possono confrontare le procedure iterativa e ricorsiva osservando che c'è una corrispondenza fra lo stack della procedura iterativa e lo stack delle attivazioni della procedura ricorsiva. Più precisamente, supponendo che gli adiacenti vengano visitati nello stesso ordine dalle due procedure, se ad un certo punto dell'esecuzione lo stack della procedura iterativa è <v₁, v₂, ..., v_r>
(con v₁= s e v_r sul top), la corrispondente sequenza di attivazioni per la procedura ricorsiva sarà <DFS-visit (G,v₁), ...,
DFS-visit (G,v_r)>. La corrispondenza può essere dimostrata per induzione sul numero di elementi nello stack.
 
 

COMPONENTI FORTEMENTE CONNESSE (Cap. 23.5)

Riportiamo le principali proprietà occorrenti per dimostrare la correttezza dell'algoritmo STRONGLY-CONNECTED-COMPONENTS(G), con relative dimostrazioni, se diverse dal libro.

 Proprietà. G e G^T hanno le stesse componenti fortemente connesse.

 Lemma CFC1 - In una qualunque visita in profondità, tutti i vertici della stessa componente fortemente connessa sono posti nello stesso albero DFS.
Dimostrazione. vedi Teorema 23.13 del testo.

Lemma CFC2- Sia u la radice di un albero A costruito dalla visita DFS(G^T) (punto 3 dell'algoritmo). Ogni discendente di u in A è anche un discendente .di u in un albero della foresta costruita dalla visita DFS(G) (punto 1).

    Dimostrazione.
    Dimostriamo il teorema per assurdo. Consideriamo un cammino sull'albero A a partire dalla radice u, e sia v il primo vertice
    nel cammino per cui il teorema non vale. Dimostriamo che questo non è possibile. Sia w il predecessore di v nel cammino.
    Dato che v è il primo vertice per cui il teorema non vale, l'enunciato vale per w, e quindi:

    a) d[u] £ d[w] < f[w] £ f[u] (w può anche essere u)

    Siccome la visita DFS(G^T) considera i vertici in ordine decrescente di fine visita, per ogni discendente di u in A, e quindi in
    particolare per v, vale

    b) f[v] < f[u]

    Da (b), per il teorema delle parentesi, si ricava che, se v non è un discendente di u nella prima visita, i due intervalli di visita di v  e u devono essere disgiunti, cioè deve valere:

    c) d[v] < f[v] < d[u] < f[u]

    Da (c) e (a) si ricava   d) f[v] < d[w]

    E' facile vedere che questo non è possibile. Infatti, dato che v è adiacente a w in G^T, w è adiacente a v in G, e quindi non è
    possibile che la visita di v termini prima che sia iniziata la visita di un suo adiacente.

 Osservazione: si noti che per la dimostrazione del Lemma CFC2 è essenziale che la visita DFS(G^T) consideri i vertici in ordine decrescente di fine visita.
 

Corollario CFC3. Sia u la radice di un albero A costruito dalla visita DFS(G^T). Ogni discendente v di u in A appartiene alla stessa componente fortemente connessa di u.

    Dimostrazione.
    Siccome v è discendente di u in A, esiste un cammino da u a v in G^T, e quindi da v a u in G. D'altra parte, per il Lemma
    CFC2 esiste anche un cammino da u a v in G.
 

Teorema CFC. L'algoritmo STRONGLY-CONNECTED-COMPONENTS(G) calcola correttamente le componenti fortemente connesse di G, ossia i vertici di ogni albero nella foresta prodotta da DFS(G^T) costituiscono una componente fortemente connessa di G.

    Dimostrazione.
    Sia A un albero, di radice u, costruito dalla visita DFS(G^T). Per il Corollario CFC3, tutti i vertici appartenenti ad A stanno
    nella stessa componente fortemente connessa. D'altra parte, per il Lemma CFC1, non ci possono essere altri vertici
    appartenenti alla stessa componente fortemente connessa che non siano in A.