Dit artikel demonstreert de procedure voor het implementeren van de DFS voor een opgegeven boom of grafiek.
Hoe kan ik Depth First Search of DFS voor een grafiek in Java implementeren?
De DFS wordt voornamelijk gebruikt voor het doorzoeken van een grafiek door elke tak/vertex precies één keer te bezoeken. Het kan cycli in een grafiek detecteren of identificeren die helpen bij het voorkomen van impasses. Het kan worden gebruikt om puzzels of doolhofproblemen op te lossen. De DFS kan worden geïmplementeerd/gebruikt in grafische algoritmen, webcrawlen en compilerontwerp.
Ga voor een uitleg naar de onderstaande code van de Depth First Search of DFS:
klas Grafiek {
privaat Gelinkte lijst addNode [ ] ;
privaat booleaans doorkruist [ ] ;
Grafiek ( int hoekpunten ) {
addNode = nieuw Gelinkte lijst [ hoekpunten ] ;
doorkruist = nieuw booleaans [ hoekpunten ] ;
voor ( int i = 0 ; i < hoekpunten ; i ++ )
addNode [ i ] = nieuw Gelinkte lijst ( ) ;
}
leegte addEdge ( int src, int begin ) {
addNode [ src ] . toevoegen ( begin ) ;
}
Beschrijving van de bovenstaande code:
- Eerst de klas met de naam ' Grafiek ' is gecreëerd. Binnenin verklaart een ' Gelinkte lijst ' genaamd ' addNode[] ” en een booleaanse array met de naam “ doorkruist[] ”.
- Geef vervolgens de hoekpunten door voor de constructor van de ' Grafiek ” klasse als een parameter.
- Daarna is de “ voor ”-lus wordt gemaakt om door elk knooppunt van de geselecteerde tak te bewegen.
- Uiteindelijk is het type leegte ' addEdge() ” wordt gebruikt om randen tussen hoekpunten toe te voegen. Deze functie heeft twee parameters: de bron van het hoekpunt ' src ” en het bestemmingspunt “ begin ”.
Laten we na het maken van een grafiek nu code van depth-first search of DFS toevoegen voor de hierboven gemaakte grafiek:
leegte DFS ( int hoekpunt ) {
doorkruist [ hoekpunt ] = WAAR ;
Systeem . uit . afdrukken ( hoekpunt + ' ' ) ;
Iterator dit = addNode [ hoekpunt ] . lijstIterator ( ) ;
terwijl ( dit. heeftVolgende ( ) ) {
int bijvoeglijk naamwoord = dit. volgende ( ) ;
als ( ! doorkruist [ bijvoeglijk naamwoord ] )
DFS ( bijvoeglijk naamwoord ) ;
}
}
In het bovenstaande codeblok:
- Eerst de ' DFS() ” functie is gemaakt die krijgt “ hoekpunt ” als parameter. Dat hoekpunt is gemarkeerd als bezocht.
- Druk vervolgens het bezochte hoekpunt af met behulp van de ' uit.print() ” methode.
- Maak vervolgens een exemplaar van de ' Iterator ” dat itereert over de aangrenzende hoekpunten van het huidige hoekpunt.
- Als het hoekpunt niet wordt bezocht, geeft het dat hoekpunt door aan de ' DFS() ” functie.
Laten we nu een ' voornaamst() ” functiegedeelte om de grafiek te maken en daarop DFS toe te passen:
openbaar statisch leegte voornaamst ( Snaar argumenten [ ] ) {
Grafiek k = nieuw Grafiek ( 4 ) ;
k. addEdge ( 0 , 1 ) ;
k. addEdge ( 1 , 2 ) ;
k. addEdge ( 2 , 3 ) ;
k. addEdge ( 3 , 3 ) ;
Systeem . uit . println ( 'Volgen is diepte eerste doorgang' ) ;
k. DFS ( 1 ) ;
}
}
Uitleg van de bovenstaande code:
- Maak eerst een object ' k ' voor de ' grafiek() ” methode.
- Vervolgens de “ addEdge() ” methode wordt gebruikt om randen toe te voegen tussen meerdere hoekpunten. Dit creëert de structuur van onze grafiek.
- Geef uiteindelijk elke hoekpuntwaarde door als een argument aan de reeds gemaakte ' DFS() ” functie. Gebruik een diepte-eerst zoekalgoritme om dat hoekpuntpad vanaf de wortel te vinden. Bijvoorbeeld een waarde van ' 1 ” wordt doorgegeven aan de “ DFS() ” functie.
Na het einde van de compilatiefase:
De uitvoer toont dat de diepte-eerst-zoekopdracht met succes is geïmplementeerd.
Conclusie
Depth First Search is een algoritme voor het doorlopen van grafieken dat de basis vormt voor veel algoritmen voor grafieken, zoals het vinden van het kortste pad, spanning trees en connectiviteitsanalyse. Het begint vanaf het rootknooppunt en beweegt dan zo diep mogelijk tot het vertrekknooppunt of het laatste knooppunt van die tak voordat het teruggaat. Dit artikel heeft de procedure gedemonstreerd om de depth-first search of DFS voor een grafiek in Java te implementeren.