我试图使用深度优先搜索来查找树中的顶点/节点我可以创建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/

10-10 13:38