|
|
Esistono due metodi sistematici per visitare almeno una volta ogni nodo ed ogni arco di un grafo orientato fortemente connesso (o non orientato e connesso). Entrambi effettuano la visita in O(n+m) partendo dal generico nodo u:
DFS: Depth First Search (in profondità)
DFS
Dopo aver visitato un nodo u, ci si allontana da esso il più possibile lungo un cammino, visitando i nodi nel cammino, sino a quando non raggiungiamo un nodo i cui adiacenti risultano tutti visitati (un vicolo cieco). Allora si torna indietro lungo l’ultimo arco visitato e si riprende la visita allontanandosi lungo un altro cammino di nodi non ancora visitati.
In linguaggio C avremo una cosa di questo tipo:
dove A e l’ insieme delle adiacenze.
BFS
Nella visita BFS i nodi sono visitati in ordine di distanza crescente dal nodo di partenza. Per distanza si intende il numero minimo di archi in un cammino che collega due nodi.
In linguaggio C avremo una cosa di questo tipo:
In entrambi i metodi, occorre mantenere una lista dei nodi che sono già stati visitati, ma i cui nodi adiacenti non sono ancora stati visitati. Poiché la DFS torna indietro dal più recente vicolo cieco, tale lista è di fatto una pila.
Dall’ altro lato poiché la BFS visita i nodi più vicini prima di quelli più lontani, tale lista è una coda.
Gli archi che durante una visita DFS connettono un nodo marcato ad uno non marcato formano un albero radicato T, detto albero di copertura DFS.
Analogamente, possiamo ottenere anche l’albero di copertura BFS.
Se il grafo è orientato allora la DFS partiziona gli archi in 4 sottoinsiemi:
archi in T: archi che collegano un nodo marcato ad uno non marcato
archi all’indietro: arco che è esaminato passando da un nodo di T ad un altro suo antenato in T
archi in avanti: arco che è esaminato passando da un nodo di T ad un altro suo discendente in T
archi di attraversamento: tra nodi che stanno sullo stesso livello in T
Tale partizione di archi è utile per derivare algoritmi efficienti su grafi. Per esempio un grafo orientato è aciclico (privo di cicli) se durante la sua visita, non è esaminato alcun arco all’indietro. Le procedure DFS e BFS sono metodi di visita sistematica che ci permettono di risolvere in O(n+m) una grande varietà di problemi, per esempio:
connessione di un grafo non orientato
forte connessione di un grafo orientato
Infatti un grafo non orientato è connesso se al termine di una visita tutti i nodi sono marcati “visitato”. Analogamente un grafo orientato è fortemente connesso se al termine della visita tutti i nodi sono marcati visitati e, anche invertendo il senso degli archi e ripetendo la visita, tutti i nodi risultano visitati nuovamente. Un altro problema che possiamo risolvere, grazie all’ utilizzo di queste due metodi di esplorazione, è quello di trovare i componenti connessi.
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.
