Algoritmi e strutture dati

Esplorazione di un grafo

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

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:

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:

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.