Aquest article mostra el procediment per implementar el DFS per a un arbre o gràfic proporcionat.
Com implementar Depth First Search o DFS per a un gràfic a Java?
El DFS s'utilitza principalment per cercar un gràfic visitant cada branca/vértex exactament una vegada. Pot detectar o identificar cicles en un gràfic que ajuda a prevenir bloquejos. Es pot utilitzar per resoldre trencaclosques o problemes de laberint. El DFS es pot implementar/utilitzar en algorismes de gràfics, rastreig web i disseny de compiladors.
Per obtenir una explicació, visiteu el codi següent de Depth First Search o DFS:
classe Gràfic {
privat LinkedList addNode [ ] ;
privat booleà Travessat [ ] ;
Gràfic ( int vèrtexs ) {
addNode = nou LinkedList [ vèrtexs ] ;
Travessat = nou booleà [ vèrtexs ] ;
per ( int i = 0 ; i < vèrtexs ; i ++ )
addNode [ i ] = nou LinkedList ( ) ;
}
buit afegirEdge ( int src, int començar ) {
addNode [ src ] . afegir ( començar ) ;
}
Descripció del codi anterior:
- Primer, la classe anomenada ' Gràfic ” es crea. Al seu interior, declara un ' LinkedList 'anomenat' addNode[] ” i una matriu de tipus booleà anomenada “ Travessat[] ”.
- A continuació, passeu els vèrtexs per al constructor del ' Gràfic ” classe com a paràmetre.
- Després d'això, el ' per ” es crea un bucle per moure's per cada node de la branca seleccionada.
- Al final, el tipus buit ' afegirEdge() ” s'utilitza per afegir arestes entre vèrtexs. Aquesta funció pren dos paràmetres: la font del vèrtex “ src ” i el vèrtex de destinació “ començar ”.
Després de la creació d'un gràfic, ara afegim el codi de cerca en profunditat o DFS per al gràfic anterior:
buit DFS ( int vèrtex ) {
Travessat [ vèrtex ] = veritat ;
Sistema . fora . imprimir ( vèrtex + ' ' ) ;
Iterador això = addNode [ vèrtex ] . listIterator ( ) ;
mentre ( això. hasNext ( ) ) {
int adj = això. Pròxim ( ) ;
si ( ! Travessat [ adj ] )
DFS ( adj ) ;
}
}
Al bloc de codi anterior:
- En primer lloc, el ' DFS() ' es crea la funció que està obtenint ' vèrtex ” com a paràmetre. Aquest vèrtex està marcat com a visitat.
- A continuació, imprimiu el vèrtex visitat utilitzant el ' out.print() ” mètode.
- Aleshores, creeu una instància del ' Iterador ” que itera sobre els vèrtexs adjacents del vèrtex actual.
- Si no es visita el vèrtex, passa aquest vèrtex al ' DFS() ” funció.
Ara, creem un ' principal () ” part de la funció per crear el gràfic i després aplicar DFS a això:
públic estàtica buit principal ( Corda args [ ] ) {
Gràfic k = nou Gràfic ( 4 ) ;
k. afegirEdge ( 0 , 1 ) ;
k. afegirEdge ( 1 , 2 ) ;
k. afegirEdge ( 2 , 3 ) ;
k. afegirEdge ( 3 , 3 ) ;
Sistema . fora . imprimirln ( 'El següent és el primer recorregut en profunditat' ) ;
k. DFS ( 1 ) ;
}
}
Explicació del codi anterior:
- Primer, creeu un objecte ' k 'per al' Gràfic() ” mètode.
- A continuació, el ' afegirEdge() El mètode s'utilitza per afegir vores entre diversos vèrtexs. Això crea l'estructura del nostre gràfic.
- Al final, passeu qualsevol valor de vèrtex com a argument a la ja creat ' DFS() ” funció. Per trobar aquest camí del vèrtex des de l'arrel, utilitzeu un algorisme de cerca en profunditat. Per exemple, un valor de ' 1 ' es passa a ' DFS() ” funció.
Després del final de la fase de compilació:
La sortida mostra que la cerca en profunditat s'ha implementat correctament.
Conclusió
Depth First Search és un algorisme de recorregut de gràfics que constitueix la base per a molts algorismes de gràfics com trobar el camí més curt, abastar arbres i anàlisi de connectivitat. Comença des del node arrel i després es mou tan profundament com sigui possible fins a sortir del node o l'últim node d'aquesta branca abans de fer marxa enrere. Aquest article ha demostrat el procediment per implementar la cerca en profunditat o DFS per a un gràfic a Java.