Denne artikel demonstrerer proceduren til at implementere DFS for et givet træ eller graf.
Hvordan implementeres Depth First Search eller DFS for en graf i Java?
DFS'en bruges primært til at søge i en graf ved at besøge hver gren/vertex nøjagtigt én gang. Det kan detektere eller identificere cyklusser i en graf, der hjælper med at forhindre dødvande. Det kan bruges til at løse gåder eller labyrintproblemer. DFS kan implementeres/anvendes i grafalgoritmer, webcrawling og compilerdesign.
Besøg nedenstående kode for Depth First Search eller DFS for at få en forklaring:
klasse Kurve {
privat LinkedList addNode [ ] ;
privat boolesk Gennemgået [ ] ;
Kurve ( int hjørner ) {
addNode = ny LinkedList [ hjørner ] ;
Gennemgået = ny boolesk [ hjørner ] ;
til ( int jeg = 0 ; jeg < hjørner ; jeg ++ )
addNode [ jeg ] = ny LinkedList ( ) ;
}
ugyldig addEdge ( int src, int Start ) {
addNode [ src ] . tilføje ( Start ) ;
}
Beskrivelse af ovenstående kode:
- Først hedder klassen ' Kurve ” er oprettet. Inde i den erklærer en ' LinkedList ' som hedder ' addNode[] ' og en boolsk type matrix med navnet ' Gennemgået[] ”.
- Send derefter knudepunkterne for konstruktøren af ' Kurve ” klasse som en parameter.
- Derefter vil ' til ”-løkke oprettes for at bevæge sig gennem hver knude i den valgte gren.
- Til sidst vil tomrummet ' addEdge() ” bruges til at tilføje kanter mellem hjørner. Denne funktion tager to parametre: kilden til toppunktet ' src ' og destinationspunktet ' Start ”.
Efter oprettelsen af en graf, lad os nu tilføje kode for dybde-først søgning eller DFS for den ovenfor oprettede graf:
ugyldig DFS ( int toppunkt ) {
Gennemgået [ toppunkt ] = rigtigt ;
System . ud . Print ( toppunkt + ' ' ) ;
Iterator det her = addNode [ toppunkt ] . listeIterator ( ) ;
mens ( det her. har Næste ( ) ) {
int adj = det her. Næste ( ) ;
hvis ( ! Gennemgået [ adj ] )
DFS ( adj ) ;
}
}
I ovenstående kodeblok:
- For det første ' DFS() ' funktion oprettes, som får ' toppunkt ” som parameter. Det toppunkt er markeret som besøgt.
- Udskriv derefter det besøgte toppunkt ved hjælp af ' out.print() ” metode.
- Opret derefter en forekomst af ' Iterator ”, der itererer over de tilstødende hjørner af det aktuelle toppunkt.
- Hvis toppunktet ikke besøges, så overfører det det toppunkt til ' DFS() ' funktion.
Lad os nu skabe en ' hoved() ” funktionsdel for at oprette grafen og derefter anvende DFS på det:
offentlig statisk ugyldig vigtigste ( Snor args [ ] ) {
Graf k = ny Kurve ( 4 ) ;
k. addEdge ( 0 , 1 ) ;
k. addEdge ( 1 , 2 ) ;
k. addEdge ( 2 , 3 ) ;
k. addEdge ( 3 , 3 ) ;
System . ud . println ( 'Følgende er Dybde Første Traversal' ) ;
k. DFS ( 1 ) ;
}
}
Forklaring af ovenstående kode:
- Først skal du oprette et objekt ' k ' for ' Kurve() ” metode.
- Dernæst ' addEdge() ”-metoden bruges til at tilføje kanter mellem flere hjørner. Dette skaber strukturen af vores graf.
- I sidste ende skal du sende enhver toppunktsværdi som et argument til den allerede oprettede ' DFS() ' funktion. For at finde den toppunktsti fra roden, skal du bruge en dybde-først søgealgoritme. For eksempel en værdi på ' 1 ' videregives til ' DFS() ' funktion.
Efter afslutningen af kompileringsfasen:
Outputtet viser, at den første dybdesøgning er blevet implementeret med succes.
Konklusion
Depth First Search er en grafgennemløbsalgoritme, der danner grundlaget for mange grafalgoritmer som at finde den korteste vej, spænde over træer og forbindelsesanalyse. Den starter fra rodknuden og bevæger sig så dybt som muligt indtil bladknuden eller sidste knude på den gren, før den går tilbage. Denne artikel har demonstreret proceduren til at implementere dybde-først-søgningen eller DFS for en graf i Java.