我试图使用深度优先搜索来查找树中的顶点/节点我可以创建dfs算法,但我不知道如何将树转换为代码,以便可以通过下面链接中的算法进行处理
JavaScript Depth-first search
这就是我能做的
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);
这是树结构。
a
/ \
b c
/|\ \
d e f g
|
h
这是我的密码
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);
}
}
}
最佳答案
你是说这样的事?
public enum State {
Unvisited, Visited, Visiting;
}
// let the start node and the end node be both the nodes.
// Implementation using DFS.
public static boolean search(Graph g, Node start, Node end) {
LinkedList<Node> stack = new LinkedList<Node>(); // operates as Stack
for (Node u : g.getNodes()) {
u.state = State.Unvisited;
}
start.state = State.Visiting;
stack.add(start);
Node u;
while(!stack.isEmpty())
{
u = stack.removeFirst(); // i.e., pop()
if (u != null) {
for (Node v : u.getAdjacent()) {
if (v.state == State.Unvisited) {
if (v == end) {
return true;
}
else {
v.state = State.Visiting;
stack.add(v);
}
}
}
u.state = State.Visited;
}
}
return false;
}
关于java - 使用深度优先搜索在树中查找节点,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/40814474/