Ta članek prikazuje postopek za implementacijo DFS za podano drevo ali graf.
Kako implementirati iskanje po globini ali DFS za graf v Javi?
DFS se primarno uporablja za iskanje po grafu z obiskom vsake veje/točke natanko enkrat. Lahko zazna ali prepozna cikle v grafu, kar pomaga pri preprečevanju zastojev. Uporablja se lahko za reševanje ugank ali težav z labirinti. DFS je mogoče implementirati/uporabiti v algoritmih grafov, spletnem pajkanju in načrtovanju prevajalnika.
Za razlago obiščite spodnjo kodo iskanja najprej v globino ali DFS:
razred Graf {
zasebno LinkedList addNode [ ] ;
zasebno logično Prehodno [ ] ;
Graf ( int vozlišča ) {
addNode = novo LinkedList [ vozlišča ] ;
Prehodno = novo logično [ vozlišča ] ;
za ( int jaz = 0 ; jaz < vozlišča ; jaz ++ )
addNode [ jaz ] = novo LinkedList ( ) ;
}
praznina addEdge ( int src, int začetek ) {
addNode [ src ] . dodati ( začetek ) ;
}
Opis zgornje kode:
- Najprej razred z imenom ' Graf « je ustvarjen. Znotraj tega razglasi ' LinkedList 'imenovan' addNode[] « in matriko logičnega tipa z imenom » Prehodno[] ”.
- Nato posredujte vozlišča za konstruktor ' Graf ” kot parameter.
- Po tem je ' za ” se ustvari zanka za premikanje skozi vsako vozlišče izbrane veje.
- Na koncu prazen tip ' addEdge() ” se uporablja za dodajanje robov med vozlišči. Ta funkcija zavzame dva parametra: izvor točke ' src ' in ciljno točko ' začetek ”.
Po izdelavi grafa zdaj dodamo kodo iskanja v globino ali DFS za zgoraj ustvarjen graf:
praznina DFS ( int vertex ) {
Prehodno [ vertex ] = prav ;
Sistem . ven . tiskanje ( vertex + ' ' ) ;
Iterator to = addNode [ vertex ] . listIterator ( ) ;
medtem ( to. hasNext ( ) ) {
int prid = to. Naslednji ( ) ;
če ( ! Prehodno [ prid ] )
DFS ( prid ) ;
}
}
V zgornjem kodnem bloku:
- Prvič, ' DFS() ' se ustvari funkcija, ki dobi ' vertex ” kot parameter. Ta točka je označena kot obiskana.
- Nato natisnite obiskano točko z uporabo “ out.print() ” metoda.
- Nato ustvarite primerek » Iterator ”, ki ponavlja čez sosednja vozlišča trenutnega vozlišča.
- Če točko ne obišče, jo prenese na ' DFS() ”.
Sedaj pa ustvarimo ' glavni () ”, da ustvarite graf in nato zanj uporabite DFS:
javnosti statična praznina glavni ( Vrvica args [ ] ) {
Graf k = novo Graf ( 4 ) ;
k. addEdge ( 0 , 1 ) ;
k. addEdge ( 1 , 2 ) ;
k. addEdge ( 2 , 3 ) ;
k. addEdge ( 3 , 3 ) ;
Sistem . ven . println ( 'Sledi prvo prečkanje globine' ) ;
k. DFS ( 1 ) ;
}
}
Razlaga zgornje kode:
- Najprej ustvarite predmet ' k ' za ' Graf() ” metoda.
- Nato je ' addEdge() ” se uporablja za dodajanje robov med več vozlišči. To ustvari strukturo našega grafa.
- Na koncu posredujte katero koli vrednost vozlišča kot argument že ustvarjenemu ' DFS() ”. Če želite najti to pot vozlišča od korena, uporabite algoritem iskanja najprej v globino. Na primer, vrednost ' 1 « se posreduje v » DFS() ”.
Po koncu faze kompilacije:
Izhod kaže, da je bilo iskanje najprej v globino uspešno izvedeno.
Zaključek
Depth First Search je algoritem za prečkanje grafov, ki tvori osnovo za številne algoritme grafov, kot so iskanje najkrajše poti, vpeta drevesa in analiza povezljivosti. Začne se od korenskega vozlišča in se nato premakne čim globlje, dokler ne zapusti vozlišča ali zadnjega vozlišča te veje pred povratnim sledenjem. Ta članek je prikazal postopek za implementacijo iskanja v globino ali DFS za graf v Javi.