Den här artikeln visar proceduren för att implementera DFS för ett tillhandahållet träd eller diagram.
Hur implementerar man Depth First Search eller DFS för en graf i Java?
DFS används främst för att söka i en graf genom att besöka varje gren/vertex exakt en gång. Den kan upptäcka eller identifiera cykler i en graf som hjälper till att förhindra dödlägen. Det kan användas för att lösa pussel eller labyrintproblem. DFS kan implementeras/användas i grafalgoritmer, webbcrawlning och kompilatordesign.
För en förklaring, besök koden nedan för Depth First Search eller DFS:
klass Graf {
privat Länkad lista addNode [ ] ;
privat booleskt Genomkorsad [ ] ;
Graf ( int hörn ) {
addNode = ny Länkad lista [ hörn ] ;
Genomkorsad = ny booleskt [ hörn ] ;
för ( int i = 0 ; i < hörn ; i ++ )
addNode [ i ] = ny Länkad lista ( ) ;
}
tomhet addEdge ( int src, int Start ) {
addNode [ src ] . Lägg till ( Start ) ;
}
Beskrivning av ovanstående kod:
- Först, klassen som heter ' Graf ' är skapad. Inuti den deklarerar en ' Länkad lista ' som heter ' addNode[] ' och en array av boolesk typ med namnet ' Genomkorsad[] ”.
- Passera sedan hörnen för konstruktören av ' Graf ' klass som en parameter.
- Efter det kommer ' för ” loop skapas för att flytta genom varje nod i den valda grenen.
- Till slut, tomrummet typ ' addEdge() ” används för att lägga till kanter mellan hörn. Denna funktion tar två parametrar: källan till vertex ' src ' och destinationspunkten ' Start ”.
Efter skapandet av en graf, låt oss nu lägga till kod för djup-först-sökning eller DFS för den ovan skapade grafen:
tomhet DFS ( int vertex ) {
Genomkorsad [ vertex ] = Sann ;
Systemet . ut . skriva ut ( vertex + ' ' ) ;
Iterator detta = addNode [ vertex ] . listIterator ( ) ;
medan ( detta. harNästa ( ) ) {
int adj = detta. Nästa ( ) ;
om ( ! Genomkorsad [ adj ] )
DFS ( adj ) ;
}
}
I ovanstående kodblock:
- Först, ' DFS() 'funktion skapas som får ' vertex ” som en parameter. Det hörnet är markerat som besökt.
- Skriv sedan ut det besökta hörnet med ' out.print() 'metoden.
- Skapa sedan en instans av ' Iterator ” som itererar över de angränsande hörnen av den aktuella vertexen.
- Om vertexet inte besöks, skickar det det vertexet till ' DFS() ' funktion.
Låt oss nu skapa en ' main() ” funktionsdel för att skapa grafen och sedan tillämpa DFS på det:
offentlig statisk tomhet huvud ( Sträng args [ ] ) {
Graf k = ny Graf ( 4 ) ;
k. addEdge ( 0 , 1 ) ;
k. addEdge ( 1 , 2 ) ;
k. addEdge ( 2 , 3 ) ;
k. addEdge ( 3 , 3 ) ;
Systemet . ut . println ( 'Följande är Depth First Traversal' ) ;
k. DFS ( 1 ) ;
}
}
Förklaring av ovanstående kod:
- Skapa först ett objekt ' k ' för ' Graf() 'metoden.
- Därefter ' addEdge() ”-metoden används för att lägga till kanter mellan flera hörn. Detta skapar strukturen för vår graf.
- Till slut skickar du vilket vertexvärde som helst som ett argument till den redan skapade ' DFS() ' funktion. För att hitta den vertexvägen från roten, använd en djup-först-sökalgoritm. Till exempel ett värde på ' 1 ' skickas till ' DFS() ' funktion.
Efter slutet av kompileringsfasen:
Utdata visar att djupet-första-sökningen har genomförts framgångsrikt.
Slutsats
Depth First Search är en grafgenomgångsalgoritm som utgör grunden för många grafalgoritmer som att hitta den kortaste vägen, spänna träd och anslutningsanalys. Den börjar från rotnoden och rör sig sedan så djupt som möjligt tills lövnoden eller den sista noden av den grenen innan den backas. Den här artikeln har demonstrerat proceduren för att implementera djupet-först-sökningen eller DFS för en graf i Java.