|
|
Si pensi di dover trovare tutte le componenti connesse di un grafo non orientato G, cioè tutti i sottografi connessi di cui G è composto, tali che nessun sottografo è contenuto in uno più grosso. Un’ idea per risolvere tale problema è un uso iterativo di DFS per marcare l’ appartenenza a componente connesso. Vediamo un algoritmo per individuare le componenti connesse.
Si utilizzano una variabile numcomp inizializzata a zero, che conta le componenti connesse ed un vettore COMP (con COMP[i] inizializato a zero) nel quale sarà registrato il numero della componente connessa alla quale appartiene il nodo i. Se COMP[i]=0 allora i non è stato ancora raggiunto dalla visita e quindi appartiene ad una nuova componente connessa. Viene pertanto incrementata di uno numcomp e richiamata la DSF sul nodo i, in modo da assegnare numcomp sia ad i, che a tutti i nodi raggiungibili dal nodi i.
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.