Ich versuche mit der Tiefensuche zuerst einen Knoten/Knoten in einem Baum zu finden. Ich konnte den DFS-Algorithmus erstellen, aber ich weiß nicht, wie der Baum in einen Code zu konvertieren, so dass ich es durch den Algorithmus wie in dem unten stehenden Link JavaScript Depth-first searchSuchen eines Knotens in einem Baum mit Tiefensuche zuerst
verarbeiten kannDas war, was ich in der Lage war zu tun
Vertex nodeA = new Vertex();
Vertex nodeB = new Vertex();
Vertex nodeC = new Vertex();
Vertex nodeD = new Vertex();
Vertex nodeE = new Vertex();
Vertex nodeF = new Vertex();
Vertex nodeG = new Vertex();
Vertex nodeH = new Vertex();
nodeA.name = "a";
nodeB.name = "b";
nodeC.name = "c";
nodeD.name = "d";
nodeE.name = "e";
nodeF.name = "f";
nodeG.name = "g";
nodeH.name = "h";
nodeA.nextNeighbor.add(nodeB);
nodeA.nextNeighbor.add(nodeC);
nodeB.nextNeighbor.add(nodeD);
nodeB.nextNeighbor.add(nodeE);
nodeB.nextNeighbor.add(nodeF);
nodeC.nextNeighbor.add(nodeG);
nodeG.nextNeighbor.add(nodeH);
Dies ist die Baumstruktur.
a
/\
b c
/|\ \
d e f g
|
h
Dies ist mein Code
class Neighbor {
public int vertexNum;
public Neighbor next;
public Neighbor(int vnum, Neighbor nbr) {
this.vertexNum = vnum;
next = nbr;
}
}
class Vertex {
String name;
Neighbor adjList;
Vertex(String name, Neighbor neighbors) {
this.name = name;
this.adjList = neighbors;
}
}
private void dfs(int v, boolean[] visited) {
visited[v] = true;
System.out.println("visiting " + adjLists[v].name);
for (Neighbor nbr=adjLists[v].adjList; nbr != null; nbr=nbr.next) {
if (!visited[nbr.vertexNum]) {
System.out.println("\n" + adjLists[v].name + "--" + adjLists[nbr.vertexNum].name);
dfs(nbr.vertexNum, visited);
}
}
}
public void dfs() {
boolean[] visited = new boolean[adjLists.length];
for (int v=0; v < visited.length; v++) {
if (!visited[v]) {
System.out.println("\nSTARTING AT " + adjLists[v].name);
dfs(v, visited);
}
}
}
Sie verwenden grundsätzlich eine FIFO-Datenstruktur (Array/Queue), die den Baum in BFS durchläuft. Sie müssen eine LIFO-Datenstruktur (Stack) verwenden, um die DFS-Traversierung zu erhalten. – user1952500
@ user1952500 Sie meinen etwas wie was ich unten gepostet? –
Wenn Sie den anderen Benutzern mit neuem Code antworten möchten, [bearbeiten] Sie den Beitrag, antworten Sie nicht mit Code, den Sie nicht kennen ( –