Tämä artikkeli esittelee prosessin DFS:n toteuttamiseksi tarjotulle puulle tai kaaviolle.
Kuinka ottaa käyttöön Depth First -haku tai DFS kaaviolle Javassa?
DFS:ää käytetään ensisijaisesti graafin etsimiseen käymällä kussakin haarassa/vertexissä tarkalleen kerran. Se voi havaita tai tunnistaa syklit kaaviossa, mikä auttaa estämään lukkiutumia. Sitä voidaan käyttää ratkaisemaan pulmia tai labyrinttiongelmia. DFS:ää voidaan toteuttaa/hyödyntää graafialgoritmeissa, verkkoindeksoinnissa ja kääntäjien suunnittelussa.
Selvitys löytyy alla olevasta Depth First -haun tai DFS:n koodista:
luokkaa Kaavio {
yksityinen LinkedList addNode [ ] ;
yksityinen boolean Kuljettu [ ] ;
Kaavio ( int kärjet ) {
addNode = Uusi LinkedList [ kärjet ] ;
Kuljettu = Uusi boolean [ kärjet ] ;
varten ( int i = 0 ; i < kärjet ; i ++ )
addNode [ i ] = Uusi LinkedList ( ) ;
}
mitätön addEdge ( int src, int alkaa ) {
addNode [ src ] . lisätä ( alkaa ) ;
}
Kuvaus yllä olevasta koodista:
- Ensin luokka nimeltä ' Kaavio ' on luotu. Sen sisällä julistaa ' LinkedList 'nimeltään' addNode[] ' ja boolen tyyppinen taulukko nimeltä ' Kuljettu[] ”.
- Ohita seuraavaksi '' konstruktorin kärjet Kaavio ” luokka parametrina.
- Sen jälkeen ' varten ' -silmukka luodaan liikkumaan valitun haaran jokaisen solmun läpi.
- Lopulta tyhjä tyyppi ' addEdge() ” käytetään reunojen lisäämiseen kärkien väliin. Tämä funktio ottaa kaksi parametria: kärjen lähde ' src ' ja kohdepiste' alkaa ”.
Kun olet luonut kaavion, lisätään nyt syvähaun koodi tai DFS yllä luotuun kaavioon:
mitätön DFS ( int kärkipiste ) {
Kuljettu [ kärkipiste ] = totta ;
Järjestelmä . ulos . Tulosta ( kärkipiste + ' ' ) ;
Iteraattori Tämä = addNode [ kärkipiste ] . listIterator ( ) ;
sillä aikaa ( Tämä. hasNext ( ) ) {
int adj = Tämä. Seuraava ( ) ;
jos ( ! Kuljettu [ adj ] )
DFS ( adj ) ;
}
}
Yllä olevassa koodilohkossa:
- Ensinnäkin ' DFS() '-toiminto luodaan, joka saa' kärkipiste ' parametrina. Tämä kärkipiste on merkitty vierailluksi.
- Tulosta seuraavaksi vierailtu kärkipiste käyttämällä ' out.print() ”menetelmä.
- Luo sitten esiintymä ' Iteraattori ', joka iteroituu nykyisen kärjen vierekkäisten kärkien yli.
- Jos kärjessä ei käydä, se välittää kyseisen kärjen ' DFS() ”-toiminto.
Luokaamme nyt ' pää() ”-funktion osa luodaksesi kaavion ja käyttää sitten DFS:ää siihen:
julkinen staattinen mitätön pää ( merkkijono args [ ] ) {
Kaavio k = Uusi Kaavio ( 4 ) ;
k. addEdge ( 0 , 1 ) ;
k. addEdge ( 1 , 2 ) ;
k. addEdge ( 2 , 3 ) ;
k. addEdge ( 3 , 3 ) ;
Järjestelmä . ulos . println ( 'Seuraava on syvyys ensimmäinen läpikulku' ) ;
k. DFS ( 1 ) ;
}
}
Selitys yllä olevalle koodille:
- Luo ensin objekti ' k ' varten ' Graph() ”menetelmä.
- Seuraavaksi ' addEdge() ” -menetelmää käytetään reunojen lisäämiseen useiden kärkien välille. Tämä luo kaaviomme rakenteen.
- Syötä lopuksi mikä tahansa kärkiarvo argumenttina jo luodulle ' DFS() ”-toiminto. Löytääksesi tämän kärkipolun juuresta käyttämällä syvyys-ensin hakualgoritmia. Esimerkiksi arvo ' 1 ' välitetään ' DFS() ”-toiminto.
Kokoonpanovaiheen päätyttyä:
Tulos näyttää, että syvyyshaku on toteutettu onnistuneesti.
Johtopäätös
Depth First Search on kaavion läpikulkualgoritmi, joka muodostaa perustan monille graafialgoritmeille, kuten lyhimmän polun etsimiselle, kattaville puille ja yhteysanalyysille. Se alkaa juurisolmusta ja siirtyy sitten mahdollisimman syvälle poistumissolmuun tai kyseisen haaran viimeiseen solmuun ennen paluuta. Tässä artikkelissa on esitelty menetelmä, jolla kaavion syvähaku tai DFS toteutetaan Javassa.