Acest articol demonstrează procedura de implementare a DFS pentru un arbore sau un grafic furnizat.
Cum se implementează Depth First Search sau DFS pentru un grafic în Java?
DFS este folosit în primul rând pentru căutarea unui grafic vizitând fiecare ramură/vertex exact o dată. Poate detecta sau identifica cicluri într-un grafic care ajută la prevenirea blocajelor. Poate fi folosit pentru a rezolva puzzle-uri sau probleme de labirint. DFS poate fi implementat/utilizat în algoritmi grafici, crawling pe web și proiectarea compilatorului.
Pentru o explicație, accesați codul de mai jos al Depth First Search sau DFS:
clasă Grafic {
privat LinkedList addNode [ ] ;
privat boolean Traversat [ ] ;
Grafic ( int vârfuri ) {
addNode = nou LinkedList [ vârfuri ] ;
Traversat = nou boolean [ vârfuri ] ;
pentru ( int i = 0 ; i < vârfuri ; i ++ )
addNode [ i ] = nou LinkedList ( ) ;
}
gol addEdge ( int src, int start ) {
addNode [ src ] . adăuga ( start ) ;
}
Descrierea codului de mai sus:
- În primul rând, clasa numită „ Grafic ' este creat. În interiorul acestuia, declară un „ LinkedList ' numit ' addNode[] ” și o matrice de tip boolean numită „ Traversat[] ”.
- Apoi, treceți nodurile pentru constructorul „ Grafic ” clasa ca parametru.
- După aceea, „ pentru ” bucla este creată pentru a se deplasa prin fiecare nod al ramurii selectate.
- În cele din urmă, tipul de gol „ addEdge() ” este folosit pentru a adăuga muchii între vârfuri. Această funcție ia doi parametri: sursa vârfului „ src ” și vârful destinației ” start ”.
După crearea unui grafic, acum să adăugăm codul de căutare în profunzime sau DFS pentru graficul creat mai sus:
gol DFS ( int vârf ) {
Traversat [ vârf ] = Adevărat ;
Sistem . afară . imprimare ( vârf + ' ' ) ;
Iterator acest = addNode [ vârf ] . listIterator ( ) ;
in timp ce ( acest. areNext ( ) ) {
int adj = acest. Următorul ( ) ;
dacă ( ! Traversat [ adj ] )
DFS ( adj ) ;
}
}
În blocul de cod de mai sus:
- În primul rând, „ DFS() „ este creată funcția care primește „ vârf ” ca parametru. Acest vârf este marcat ca vizitat.
- Apoi, tipăriți vârful vizitat folosind „ out.print() ” metoda.
- Apoi, creați o instanță a „ Iterator ” care iterează peste vârfurile adiacente vârfului curent.
- Dacă vârful nu este vizitat, atunci acesta trece acel vârf la „ DFS() ”funcție.
Acum, haideți să creăm un „ principal() ” parte a funcției pentru a crea graficul și apoi aplicați DFS la acesta:
public static gol principal ( Şir argumente [ ] ) {
Graficul k = nou Grafic ( 4 ) ;
k. addEdge ( 0 , 1 ) ;
k. addEdge ( 1 , 2 ) ;
k. addEdge ( 2 , 3 ) ;
k. addEdge ( 3 , 3 ) ;
Sistem . afară . println ( „Urmarea este prima traversare a adâncimii” ) ;
k. DFS ( 1 ) ;
}
}
Explicația codului de mai sus:
- Mai întâi, creați un obiect „ k ' pentru ' Grafic() ” metoda.
- În continuare, „ addEdge() ” este utilizată pentru a adăuga muchii între mai multe vârfuri. Aceasta creează structura graficului nostru.
- În cele din urmă, transmiteți orice valoare de vârf ca argument la „ DFS() ”funcție. Pentru a găsi acea cale de vârf de la rădăcină, utilizați un algoritm de căutare în profunzime. De exemplu, o valoare de „ 1 ' este trecut la ' DFS() ”funcție.
După încheierea fazei de compilare:
Rezultatul arată că căutarea în profunzime a fost implementată cu succes.
Concluzie
Depth First Search este un algoritm de traversare a graficului care formează baza pentru mulți algoritmi de grafic, cum ar fi găsirea celei mai scurte căi, copaci care se întind și analiza conectivității. Pornește de la nodul rădăcină și apoi se mișcă cât mai adânc posibil până la părăsirea nodului sau ultimul nod al acelei ramuri înainte de a reveni. Acest articol a demonstrat procedura de implementare a căutării depth-first sau DFS pentru un grafic în Java.