See artikkel demonstreerib DFS-i juurutamise protseduuri pakutud puu või graafiku jaoks.
Kuidas rakendada Javas graafiku jaoks esmast sügavust otsingut või DFS-i?
DFS-i kasutatakse peamiselt graafiku otsimiseks, külastades iga haru/tippu täpselt üks kord. See suudab tuvastada või tuvastada graafikul tsükleid, mis aitab vältida ummikseisu. Seda saab kasutada mõistatuste või labürindi probleemide lahendamiseks. DFS-i saab rakendada/kasutada graafikualgoritmides, veebi roomamises ja kompilaatori kujundamises.
Selgituse saamiseks külastage allpool olevat sügavuse esimese otsingu või DFS-i koodi:
klass Graafik {
privaatne LinkedList addNode [ ] ;
privaatne tõeväärtus Läbitud [ ] ;
Graafik ( int tipud ) {
addNode = uus LinkedList [ tipud ] ;
Läbitud = uus tõeväärtus [ tipud ] ;
jaoks ( int i = 0 ; i < tipud ; i ++ )
addNode [ i ] = uus LinkedList ( ) ;
}
tühine addEdge ( int src, int alustada ) {
addNode [ src ] . lisama ( alustada ) ;
}
Ülaltoodud koodi kirjeldus:
- Esiteks klass nimega ' Graafik ” on loodud. Selle sees kuulutab ' LinkedList 'nimega' addNode[] ' ja tõeväärtuslikku tüüpi massiiv nimega ' Läbitud[] ”.
- Järgmisena edastage konstruktori tipud Graafik ” klass parameetrina.
- Pärast seda ' jaoks ” tsükkel luuakse valitud haru iga sõlme kaudu liikumiseks.
- Lõpuks tühjuse tüüp ' addEdge() ” kasutatakse tippude vahele servade lisamiseks. See funktsioon võtab kaks parameetrit: tipu allikas ' src ' ja sihtkoha tipp' alustada ”.
Pärast graafiku loomist lisame nüüd ülaltoodud graafiku jaoks sügavus-esimese otsingu või DFS-i koodi:
tühine DFS ( int tipp ) {
Läbitud [ tipp ] = tõsi ;
Süsteem . välja . printida ( tipp + ' ' ) ;
Iteraator see = addNode [ tipp ] . listIterator ( ) ;
samal ajal ( see. hasNext ( ) ) {
int adj = see. järgmiseks ( ) ;
kui ( ! Läbitud [ adj ] )
DFS ( adj ) ;
}
}
Ülaltoodud koodiplokis:
- Esiteks, ' DFS() Luuakse funktsioon ', mis saab ' tipp ” parameetrina. See tipp on märgitud külastatuks.
- Järgmisena printige külastatud tipp, kasutades ' out.print() ” meetod.
- Seejärel looge ' Iteraator ”, mis itereerub üle praeguse tipu külgnevate tippude.
- Kui tippu ei külastata, edastab see selle tipu ' DFS() ” funktsioon.
Nüüd loome ' peamine () ” funktsiooni osa graafiku loomiseks ja seejärel DFS-i rakendamiseks sellele:
avalik staatiline tühine peamine ( String args [ ] ) {
Graafik k = uus Graafik ( 4 ) ;
k. addEdge ( 0 , 1 ) ;
k. addEdge ( 1 , 2 ) ;
k. addEdge ( 2 , 3 ) ;
k. addEdge ( 3 , 3 ) ;
Süsteem . välja . println ( 'Järgnedes on sügavus esimene läbimine' ) ;
k. DFS ( 1 ) ;
}
}
Ülaltoodud koodi selgitus:
- Esiteks looge objekt ' k ' Selle eest ' Graafik() ” meetod.
- Järgmiseks ' addEdge() ” meetodit kasutatakse servade lisamiseks mitme tipu vahele. See loob meie graafiku struktuuri.
- Lõpuks edasta mis tahes tipu väärtus argumendina juba loodud ' DFS() ” funktsioon. Selle tipu tee leidmiseks juurest kasutage sügavus-esimese otsingu algoritmi. Näiteks väärtus ' 1 ' edastatakse jaotisele ' DFS() ” funktsioon.
Pärast kompileerimisfaasi lõppu:
Väljund näitab, et sügavus-esimene otsing on edukalt rakendatud.
Järeldus
Sügavuse esimene otsing on graafiku läbimise algoritm, mis on aluseks paljudele graafikualgoritmidele, nagu lühima tee leidmine, ulatuvad puud ja ühenduvusanalüüs. See algab juursõlmest ja liigub seejärel võimalikult sügavale kuni lahkumissõlmeni või selle haru viimase sõlmeni enne tagasiminekut. Selles artiklis on näidatud protseduur, kuidas Java-s graafiku jaoks sügavus-esimese otsingu või DFS-i juurutada.