Tento článok ukazuje postup implementácie DFS pre daný strom alebo graf.
Ako implementovať hĺbkové prvé vyhľadávanie alebo DFS pre graf v jazyku Java?
DFS sa primárne používa na vyhľadávanie grafu návštevou každej vetvy/vrcholu presne raz. Dokáže odhaliť alebo identifikovať cykly v grafe, ktorý pomáha predchádzať zablokovaniu. Môže sa použiť na riešenie hádaniek alebo problémov s bludiskom. DFS možno implementovať/využiť v grafových algoritmoch, prehľadávaní webu a návrhu kompilátora.
Pre vysvetlenie navštívte nižšie uvedený kód Hĺbkového prvého vyhľadávania alebo DFS:
trieda Graf {
súkromné LinkedList addNode [ ] ;
súkromné boolovská hodnota Prejdené [ ] ;
Graf ( int vrcholy ) {
addNode = Nový LinkedList [ vrcholy ] ;
Prejdené = Nový boolovská hodnota [ vrcholy ] ;
pre ( int i = 0 ; i < vrcholy ; i ++ )
addNode [ i ] = Nový LinkedList ( ) ;
}
neplatné addEdge ( int src, int začať ) {
addNode [ src ] . pridať ( začať ) ;
}
Popis vyššie uvedeného kódu:
- Najprv trieda s názvom „ Graf “ je vytvorený. Vo vnútri sa uvádza „ LinkedList “ s názvom “ addNode[] “ a pole boolovského typu s názvom „ Prejdené[] “.
- Ďalej odovzdajte vrcholy pre konštruktor „ Graf ” trieda ako parameter.
- Potom sa „ pre Vytvorí sa slučka ” na pohyb cez každý uzol vybranej vetvy.
- Nakoniec prázdno typu „ addEdge() ” sa používa na pridanie hrán medzi vrcholy. Táto funkcia má dva parametre: zdroj vrcholu “ src “ a cieľový vrchol “ začať “.
Po vytvorení grafu teraz pridajte kód hĺbkového vyhľadávania alebo DFS pre vyššie vytvorený graf:
neplatné DFS ( int vrchol ) {
Prejdené [ vrchol ] = pravda ;
systém . von . vytlačiť ( vrchol + '' ) ;
Iterátor toto = addNode [ vrchol ] . listIterator ( ) ;
zatiaľ čo ( toto. hasNext ( ) ) {
int adj = toto. Ďalšie ( ) ;
ak ( ! Prejdené [ adj ] )
DFS ( adj ) ;
}
}
Vo vyššie uvedenom bloku kódu:
- Po prvé, „ DFS() “ je vytvorená funkcia, ktorá získava “ vrchol “ ako parameter. Tento vrchol je označený ako navštívený.
- Potom vytlačte navštívený vrchol pomocou „ out.print() “.
- Potom vytvorte inštanciu súboru „ Iterátor ”, ktorý iteruje cez susedné vrcholy aktuálneho vrcholu.
- Ak vrchol nenavštívite, prejde tento vrchol do „ DFS() “.
Teraz vytvoríme „ Hlavná() ” funkčná časť na vytvorenie grafu a potom naň aplikujte DFS:
verejnosti statické neplatné Hlavná ( Reťazec args [ ] ) {
Graf k = Nový Graf ( 4 ) ;
k. addEdge ( 0 , 1 ) ;
k. addEdge ( 1 , 2 ) ;
k. addEdge ( 2 , 3 ) ;
k. addEdge ( 3 , 3 ) ;
systém . von . println ( „Nasledovanie je prechod do hĺbky“ ) ;
k. DFS ( 1 ) ;
}
}
Vysvetlenie vyššie uvedeného kódu:
- Najprv vytvorte objekt ' k ' pre ' graf() “.
- Ďalej, „ addEdge() ” metóda sa používa na pridávanie hrán medzi viaceré vrcholy. To vytvára štruktúru nášho grafu.
- Nakoniec odovzdajte akúkoľvek hodnotu vrcholu ako argument do už vytvoreného „ DFS() “. Ak chcete nájsť cestu k vrcholu od koreňa, použite algoritmus vyhľadávania do hĺbky. Napríklad hodnota „ 1 'prechádza do ' DFS() “.
Po skončení fázy kompilácie:
Výstup ukazuje, že vyhľadávanie do hĺbky bolo úspešne implementované.
Záver
Hĺbka prvého vyhľadávania je algoritmus prechodu grafu, ktorý tvorí základ mnohých algoritmov grafov, ako je nájdenie najkratšej cesty, preklenutie stromov a analýza konektivity. Začína od koreňového uzla a potom sa pohybuje tak hlboko, ako je to možné, až po výstupný uzol alebo posledný uzol tejto vetvy pred spätným sledovaním. Tento článok demonštroval postup implementácie hĺbkového vyhľadávania alebo DFS pre graf v jazyku Java.