Esplorazione di un grafo

0
79




<br /> Esplorazione di un grafo<br />

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:

  • 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:

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.

Let’s block ads! (Why?)

from My Reading List: Read and Unread https://ift.tt/2PE45Yz
via IFTTT

LEAVE A REPLY

Please enter your comment!
Please enter your name here