Der DFS-Algorithmus ist ein Durchlaufalgorithmus, der als Suchalgorithmus definiert ist, der als Tiefensuche abgekürzt wird. Er wird auch als Graphalgorithmus bezeichnet, da er in der Baumstruktur sucht, die wie eine Graphenstruktur aussieht, und daher von dort aus beginnt Wurzel und Traversen zusammen mit dem Diagramm unten mit verschiedenen Zweigen. Im Allgemeinen ist der DFS-Algorithmus in Java als Traversierungsalgorithmus definiert, der eine Baum- oder Diagrammstruktur durchläuft, die vom Wurzelknoten am Anfangspunkt ausgeht und mit jedem Zweig tief geht, bis er den letzten Knoten eines beliebigen letzten Zweigs erreicht, für den eine solche Suche bekannt ist als Tiefensuche und bietet drei verschiedene Arten von DFS, z. B. Vorbestellungs-, Inorder- und Postorder-Traversal-Suchen.
Starten Sie Ihren kostenlosen Softwareentwicklungskurs
Webentwicklung, Programmiersprachen, Softwaretests und andere
Algorithmus:
DFS ist ein einheitlicher Algorithmus, der zu nicht optimalen Lösungen führt. Der DFS-Algorithmus funktioniert wie folgt:
Schritt 1: Beginnen Sie mit dem Wurzelknoten eines beliebigen Diagramms oder Baums.
Schritt 2: Betrachten Sie nun den Wurzelknoten als ersten Knoten des Diagramms und platzieren Sie diesen Knoten oben im Stapel oder in der Liste.
Schritt 3: Suchen Sie nun nach benachbarten Knoten des Wurzelknotens, der der erste Knoten war, und fügen Sie diese benachbarten Knoten der anderen Liste der benachbarten Knoten hinzu.
Schritt 4: Fahren Sie dann mit dem Hinzufügen der benachbarten Knoten jedes Knotens im Stapel oder in der Liste nach dem Wurzelknoten fort.
Schritt 5:Fahren Sie mit Schritt 3 bis 4 fort, bis Sie den Endknoten des letzten Zweigs im Diagramm erreichen oder die Liste der angrenzenden Knoten leer wird.
Daher ist der DFS-Algorithmus in Java einer der Traversal-Suchalgorithmen, die vom Anfangsknoten bis zum Endknoten tief durchsuchen. Manchmal ist es jedoch verwirrend, wenn Sie den Graphen durchlaufen, sei es durch einen linken oder einen rechten Zweig. Um dieses Problem zu lösen, gibt es drei verschiedene Arten von DFS-Vorbestellung, Inorder und Postorder zum Durchlaufen des Baums gemäß der angegebenen Reihenfolge.
In Java funktioniert der DFS-Algorithmus nach dem oben beschriebenen Algorithmus. Der DFS-Algorithmus für nicht gerichtete Graphen beginnt beim Wurzelknoten, indem er zunächst diesen Wurzelknoten in dem einen Stapel platziert, der als besuchter Stapel betrachtet werden kann, der die besuchten Knoten enthält, und dann alle benachbarten Knoten des Wurzelknotens in diesem platziert besuchter Stack, in dem der Root-Knoten vorhanden ist. Durchlaufen Sie dann das Diagramm und suchen Sie dann einen benachbarten Knoten des benachbarten Knotens jeder Wurzel. Fahren Sie bis zum letzten Knoten des Diagramms fort und durchqueren Sie diese Knoten, indem Sie alle Knoten in einem anderen Stapel platzieren. Nach Abschluss der Suche wird der besuchte Stapel angezeigt, was Folgendes ergibt die Knoten, die durch den Graphen durchlaufen wurden.
Sehen wir uns nun ein einfaches Beispiel für einen DFS-Algorithmus an, der in der Programmiersprache Java in einem nicht zusammenhängenden Diagramm implementiert ist.
Code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class vertex
{
int root, dest;
public vertex(int root, int dest)
{
this.root = root;
this.dest = dest;
}
}
class graphstruc
{
List<List<Integer>> adjList = null;
graphstruc(List<vertex> v, int N)
{
adjList = new ArrayList<>();
for (int i = 0; i < N; i++) {
adjList.add(new ArrayList<>());
}
for (vertex e: v)
{
int src = e.root;
int dest = e.dest;
adjList.get(src).add(dest);
adjList.get(dest).add(src);
}
}
}
class Main
{
public static void DFS(graphstruc graph, int v, boolean[] d)
{
d[v] = true;
System.out.print(v + " ");
for (int u: graph.adjList.get(v))
{
if (!d[u]) {
DFS(graph, u, d);
}
}
}
public static void main(String[] args)
{
List<vertex> v = Arrays.asList(
new vertex(1, 2), new vertex(1, 7), new vertex(1, 8),
new vertex(2, 3), new vertex(2, 6), new vertex(3, 4),
new vertex(3, 5), new vertex(8, 9), new vertex(8, 12),
new vertex(9, 10), new vertex(9, 11), new vertex(10, 12),
new vertex(10, 13), new vertex(11, 14)
);
final int N = 15;
graphstruc g = new graphstruc(v, N);
boolean[] d = new boolean[N];
System.out.println("Demonstration of Depth First Search algorithm in Java is as follows:");
for (int i = 0; i < N; i++)
{
if (!d[i]) {
DFS(g, i, d);
}
}
}
}Ausgabe:
Im obigen Beispiel definieren wir zunächst einen Klassenscheitelpunkt, in dem wir den Stamm- und Zielscheitelpunkt im Diagramm deklarieren, wobei dieser Klassenscheitelpunkt die Scheitelpunkte des Diagramms speichert. Dann definieren wir die Klasse graphstruc, um die angrenzenden Eckpunkte des Wurzelknotens zu deklarieren und diese angrenzenden Knoten in die Liste aufzunehmen. Wir speichern die benachbarten Scheitelpunkte und fügen später die benachbarten Scheitelpunkte dieser Scheitelpunkte zur Liste hinzu. Um dann DFS durchzuführen, deklarieren wir eine DFS-Klasse, über die wir den aktuellen Knoten aus dem gegebenen Diagramm identifizieren, und wir identifizieren dann benachbarte Knoten jedes Knotens und fügen die benachbarten Listenknoten hinzu. Schließlich definieren wir in der Hauptklasse eine Liste von Diagrammscheitelpunkten als Array zusammen mit einer Gesamtzahl von Knoten. Nach dem Aufruf der DFS-Funktion wird die Liste in der DFS-Suchliste angezeigt, wie im obigen Screenshot gezeigt , das ist die Ausgabe.
Sehen wir uns nun die DFS-Implementierung mit verschiedenen Arten von Traversal-Aufträgen wie Preorder-, Inorder- und Postorder-Traversal in Java an. Unten sehen wir die Vorbestellungsimplementierung in Java.
Code:
class vertex
{
int data;
vertex l, r;
public vertex(int k)
{
data = k;
l = r = null;
}
}
class Main
{
public static void preorder(vertex root)
{
if (root == null) {
return;
}
System.out.print(root.data + " ");
preorder(root.l);
preorder(root.r);
}
public static void main(String[] args)
{
vertex root = new vertex(2);
root.l = new vertex(3);
root.r = new vertex(1);
root.l.l = new vertex(6);
root.r.l = new vertex(4);
root.r.r = new vertex(5);
root.r.l.l = new vertex(8);
root.r.l.r = new vertex(7);
preorder(root);
}
}Ausgabe:
Das obige Beispiel ähnelt auch dem vorherigen Beispiel, wobei hier der einzige Unterschied darin besteht, dass wir die Traverse-Aufträge im DFS-Algorithmus definieren. Hier definieren wir nur die Vorbestellungs-Durchlaufreihenfolge, die, wenn sie definiert ist, den Tiefengraphen in der Reihenfolge Wurzelknoten, linker Knoten und rechter Knoten durchläuft. Deshalb haben wir hier Knoten 2 als Wurzelknoten, Knoten 3 als linken Knoten und Knoten 6 als rechten Knoten usw. deklariert. Die Ausgabe ist wie im obigen Screenshot dargestellt.
Dieser Artikel kommt zu dem Schluss, dass der DFS-Algorithmus in Java ein Traversal-Algorithmus ist, um den Graphen tief zu finden oder zu durchsuchen, bis der letzte Knoten besucht wird. Die Zeitkomplexität für den DFS-Algorithmus wird normalerweise in O(E+V) dargestellt, wobei E für Kanten und V für Eckpunkte des Diagramms steht. Es gibt viele verschiedene Anwendungen des DFS-Algorithmus basierend auf seinen Durchlaufreihenfolgen, die als Inorder-, Preorder- und Postorder-DFS-Traversal durch den Graphen klassifiziert werden.
Das obige ist der detaillierte Inhalt vonDFS-Algorithmus in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
