In diesem Artikel wird das Verfahren zum Implementieren des DFS für einen bereitgestellten Baum oder ein bereitgestelltes Diagramm veranschaulicht.
Wie implementiert man die Tiefensuche oder DFS für ein Diagramm in Java?
Das DFS wird hauptsächlich zum Durchsuchen eines Diagramms verwendet, indem jeder Zweig/Scheitelpunkt genau einmal besucht wird. Es kann Zyklen in einem Diagramm erkennen oder identifizieren, was dabei hilft, Deadlocks zu verhindern. Es kann zum Lösen von Rätseln oder Labyrinthproblemen verwendet werden. Das DFS kann in Diagrammalgorithmen, Web-Crawling und Compiler-Design implementiert/verwendet werden.
Eine Erklärung finden Sie im folgenden Code der Depth First Search oder DFS:
Klasse Graph {
Privatgelände LinkedList addNode [ ] ;
Privatgelände Boolescher Wert Durchquert [ ] ;
Graph ( int Eckpunkte ) {
addNode = neu LinkedList [ Eckpunkte ] ;
Durchquert = neu Boolescher Wert [ Eckpunkte ] ;
für ( int ich = 0 ; ich < Eckpunkte ; ich ++ )
addNode [ ich ] = neu LinkedList ( ) ;
}
Leere addEdge ( int src, int Start ) {
addNode [ src ] . hinzufügen ( Start ) ;
}
Beschreibung des obigen Codes:
- Zuerst die Klasse mit dem Namen „ Graph ' geschaffen. Darin heißt es: „ LinkedList ' genannt ' addNode[] ” und ein boolesches Array mit dem Namen „ Durchquert[] “.
- Als nächstes übergeben Sie die Eckpunkte für den Konstruktor von „ Graph ”-Klasse als Parameter.
- Danach wird das „ für Es wird eine Schleife erstellt, um jeden Knoten des ausgewählten Zweigs zu durchlaufen.
- Am Ende ist der Void-Typ „ addEdge() „wird verwendet, um Kanten zwischen Scheitelpunkten hinzuzufügen. Diese Funktion benötigt zwei Parameter: die Quelle des Scheitelpunkts „ src ” und der Zielscheitelpunkt „ Start “.
Nach der Erstellung eines Diagramms fügen wir nun Code für die Tiefensuche oder DFS für das oben erstellte Diagramm hinzu:
Leere DFS ( int Scheitel ) {
Durchquert [ Scheitel ] = WAHR ;
System . aus . drucken ( Scheitel + ' ' ) ;
Iterator Das = addNode [ Scheitel ] . listIterator ( ) ;
während ( Das. hasNext ( ) ) {
int adj = Das. nächste ( ) ;
Wenn ( ! Durchquert [ adj ] )
DFS ( adj ) ;
}
}
Im obigen Codeblock:
- Zuerst die ' DFS() „Funktion wird erstellt, die erhält“ Scheitel ” als Parameter. Dieser Scheitelpunkt ist als besucht markiert.
- Drucken Sie als Nächstes den besuchten Scheitelpunkt mit dem Befehl „ out.print() ' Methode.
- Erstellen Sie dann eine Instanz von „ Iterator ”, das über die benachbarten Scheitelpunkte des aktuellen Scheitelpunkts iteriert.
- Wenn der Scheitelpunkt nicht besucht wird, wird dieser Scheitelpunkt an „ übergeben. DFS() ” Funktion.
Lassen Sie uns nun ein „ hauptsächlich() ”-Funktionsteil, um das Diagramm zu erstellen und dann DFS darauf anzuwenden:
öffentlich statisch Leere hauptsächlich ( Zeichenfolge args [ ] ) {
Diagramm k = neu Graph ( 4 ) ;
k. addEdge ( 0 , 1 ) ;
k. addEdge ( 1 , 2 ) ;
k. addEdge ( 2 , 3 ) ;
k. addEdge ( 3 , 3 ) ;
System . aus . println ( „Folgen ist Tiefendurchquerung“ ) ;
k. DFS ( 1 ) ;
}
}
Erklärung des obigen Codes:
- Erstellen Sie zunächst ein Objekt „ k ” für die „ Graph() ' Methode.
- Als nächstes wird das „ addEdge() Die Methode wird verwendet, um Kanten zwischen mehreren Scheitelpunkten hinzuzufügen. Dadurch entsteht die Struktur unseres Diagramms.
- Übergeben Sie am Ende einen beliebigen Scheitelpunktwert als Argument an die bereits erstellte „ DFS() ” Funktion. Um diesen Scheitelpunktpfad von der Wurzel aus zu finden, verwenden Sie einen Tiefensuchalgorithmus. Zum Beispiel ein Wert von „ 1 „wird an „übergeben“ DFS() ” Funktion.
Nach dem Ende der Kompilierungsphase:
Die Ausgabe zeigt, dass die Tiefensuche erfolgreich implementiert wurde.
Abschluss
Depth First Search ist ein Graph-Traversal-Algorithmus, der die Grundlage für viele Graph-Algorithmen wie die Suche nach dem kürzesten Pfad, Spanning Trees und Konnektivitätsanalysen bildet. Es beginnt am Wurzelknoten und bewegt sich dann so tief wie möglich bis zum Ausgangsknoten oder letzten Knoten dieses Zweigs, bevor es zurückgeht. In diesem Artikel wurde das Verfahren zur Implementierung der Tiefensuche oder DFS für ein Diagramm in Java demonstriert.