Questo articolo illustra la procedura per implementare il DFS per un albero o un grafico fornito.
Come implementare Depth First Search o DFS per un grafico in Java?
Il DFS viene utilizzato principalmente per la ricerca di un grafico visitando ogni ramo/vertice esattamente una volta. Può rilevare o identificare i cicli in un grafico che aiuta a prevenire i deadlock. Può essere utilizzato per risolvere enigmi o problemi di labirinti. Il DFS può essere implementato/utilizzato in algoritmi grafici, scansione web e progettazione di compilatori.
Per una spiegazione, visitare il seguente codice di Depth First Search o DFS:
classe Grafico {
privato Lista collegata addNode [ ] ;
privato booleano Attraversato [ ] ;
Grafico ( int vertici ) {
addNode = nuovo Lista collegata [ vertici ] ;
Attraversato = nuovo booleano [ vertici ] ;
per ( int io = 0 ; io < vertici ; io ++ )
addNode [ io ] = nuovo Lista collegata ( ) ;
}
vuoto addEdge ( int src, int inizio ) {
addNode [ src ] . aggiungere ( inizio ) ;
}
Descrizione del codice sopra:
- Innanzitutto, la classe denominata ' Grafico ' è creato. Al suo interno, dichiara un “ Lista collegata ' di nome ' aggiungiNodo[] ” e un array di tipo booleano denominato “ attraversato[] ”.
- Successivamente, passa i vertici per il costruttore di ' Grafico ” class come parametro.
- Dopodiché il “ per ” loop viene creato per spostarsi attraverso ogni nodo del ramo selezionato.
- Alla fine, il tipo void “ aggiungibordo() ” viene utilizzato per aggiungere bordi tra i vertici. Questa funzione accetta due parametri: la sorgente del vertice “ src ” e il vertice di destinazione “ inizio ”.
Dopo la creazione di un grafico, ora aggiungiamo il codice di ricerca in profondità o DFS per il grafico sopra creato:
vuoto DFS ( int vertice ) {
Attraversato [ vertice ] = VERO ;
Sistema . fuori . stampa ( vertice + ' ' ) ;
Iteratore Questo = addNode [ vertice ] . listIterator ( ) ;
Mentre ( Questo. hasNext ( ) ) {
int agg = Questo. Prossimo ( ) ;
Se ( ! Attraversato [ agg ] )
DFS ( agg ) ;
}
}
Nel blocco di codice sopra:
- Prima il ' DFS() ” viene creata la funzione che sta ottenendo “ vertice ” come parametro. Quel vertice è contrassegnato come visitato.
- Quindi, stampa il vertice visitato usando il ' fuori.stampa() ' metodo.
- Quindi, crea un'istanza di ' Iteratore ” che itera sui vertici adiacenti del vertice corrente.
- Se il vertice non viene visitato, passa quel vertice al ' DFS() ' funzione.
Ora, creiamo un ' principale() ” parte della funzione per creare il grafico e quindi applicare DFS a quello:
pubblico statico vuoto principale ( Corda arg [ ] ) {
Grafico k = nuovo Grafico ( 4 ) ;
K. addEdge ( 0 , 1 ) ;
K. addEdge ( 1 , 2 ) ;
K. addEdge ( 2 , 3 ) ;
K. addEdge ( 3 , 3 ) ;
Sistema . fuori . println ( 'Il seguito è il primo attraversamento della profondità' ) ;
K. DFS ( 1 ) ;
}
}
Spiegazione del codice precedente:
- Per prima cosa, crea un oggetto ' K ' per il ' Grafico() ' metodo.
- Successivamente, il “ aggiungibordo() Il metodo ” viene utilizzato per aggiungere bordi tra più vertici. Questo crea la struttura del nostro grafico.
- Alla fine, passa qualsiasi valore di vertice come argomento al già creato ' DFS() ' funzione. Per trovare il percorso del vertice dalla radice, utilizza un algoritmo di ricerca in profondità. Ad esempio, un valore di ' 1 ” viene passato al “ DFS() ' funzione.
Al termine della fase di compilazione:
L'output mostra che la ricerca in profondità è stata implementata correttamente.
Conclusione
Depth First Search è un algoritmo di attraversamento di grafi che costituisce la base per molti algoritmi di grafi come la ricerca del percorso più breve, lo spanning tree e l'analisi della connettività. Inizia dal nodo radice e poi si sposta il più in profondità possibile fino al nodo di uscita o all'ultimo nodo di quel ramo prima di tornare indietro. Questo articolo ha dimostrato la procedura per implementare la ricerca in profondità o DFS per un grafo in Java.