DFS方法不能正常工作

Question

我期望DFS方法打印路径为1-> 2-> 4-> 5，但它显示1-> 2-> 3-> 4-> 5请问您可以提示方法可以使用最少的代码量来修正？

/** 
* Created by mona on 5/28/16. 
*/ 

import java.util.Stack; 

public class DepthFirstSearch { 
    public static void DFS(GraphNode root, int num) { 
     if (root.val == num) { 
      System.out.println("root has the value "+num); 
     } 
     System.out.println(" current value is "+root.val); 
     Stack<GraphNode> stack = new Stack<>(); 
     stack.push(root); 
     while (!stack.isEmpty()) { 
      for (GraphNode g : stack.pop().neighbors) { 
       if (!g.visited) { 
        System.out.println(" current value is "+g.val); 
        if (g.val == num) { 
         System.out.println("Found"); 
        } 
        g.visited = true; 
        stack.push(g); 
       } 
      } 
     } 
    } 

    public static void main(String[] args) { 
     GraphNode n1 = new GraphNode(1); 
     GraphNode n2 = new GraphNode(2); 
     GraphNode n3 = new GraphNode(3); 
     GraphNode n4 = new GraphNode(4); 
     GraphNode n5 = new GraphNode(5); 

     n1.neighbors = new GraphNode[] {n2}; 
     n2.neighbors = new GraphNode[] {n4,n3}; 
     n3.neighbors = new GraphNode[] {n4}; 
     n4.neighbors = new GraphNode[] {n5}; 
     n5.neighbors = new GraphNode[] {}; 

     DFS(n1, 5); 
    } 
} 

下面是GraphNode类的代码：

/** 
* Created by mona on 5/27/16. 
*/ 
public class GraphNode { 
    int val; 
    GraphNode next; 
    GraphNode[] neighbors; 
    boolean visited; 

    GraphNode(int val) { 
     this.val = val; 
     this.visited = false; 
    } 

    GraphNode(int val, GraphNode[] neighbors) { 
     this.val = val; 
     this.neighbors = neighbors; 
     this.visited = false; 
    } 

    public String toString() { 
     return "value is: "+this.val; 
    } 

} 

Answer 1

要到这个节点的路径，这是不够的，只是添加所有您遇到的节点，因为你可能会遇到一个“死胡同“在图中或添加实际不在路径上的节点。为了防止这一点，你需要保持包含一个节点作为邻居，当你插入他们到堆栈中的节点的轨迹：

Map<GraphNode, GraphNode> parents = new HashMap<>(); 
outer: while (!stack.isEmpty()) { 
    GraphNode currentElement = stack.pop(); 
    for (GraphNode g : currentElement.neighbors) { 
     if (!g.visited) { 
      parents.put(g, currentElement); 
      System.out.println(" current value is "+g.val); 
      if (g.val == num) { 
       System.out.println("Found"); 
       List<GraphNode> path = reconstructPath(parents, g); 

       // use path, e.g. 
       System.out.println(path.stream().map(n -> Integer.toString(n.val)).collect(Collectors.joining("->"))); 

       break outer; 
      } 
      g.visited = true; 
      stack.push(g); 
     } 
    } 
} 

static List<GraphNode> reconstructPath(Map<GraphNode, GraphNode> parents, GraphNode end) { 
    List<GraphNode> list = new ArrayList<>(); 
    while (end != null) { 
      list.add(end); 
      end = parents.get(end); 
    } 
    Collections.reverse(list); 
    return list; 
}