使用深度優先搜索在樹中找到節點

Question

我想使用深度優先搜索來查找樹中的頂點/節點。我能夠創建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); 
      } 
     } 
    } 

Answer 1

你的意思是這樣的嗎？

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; 
    }