图路径查找器

Question

我想在两个节点（sourcenode和targetnode）之间找到路径。我想出了这个代码，但我似乎不能使它递归地找到一条路径。我甚至设置节点为空，如果目标节点被发现，但我不断收到堆栈溢出错误。

public void findPathBetween(Node sourceNode, Node targetNode){ 
    //find a path between the sourceNode and targetNode 
    //select the nodes and edges along the path if one exists. 

    ArrayList<Node> nodesToSearch = new ArrayList<Node>(); 
    nodesToSearch.add(sourceNode); 

    //basis 
    if(sourceNode == null || targetNode == null) return; 

    //recursion 
    ArrayList<Node> newNodesToSearch = new ArrayList<Node>(); //get nodes for next level to search 
    for(Node aNode : nodesToSearch) { 
     for (Node neighbour : aNode.getNeighbours()) { 
      if (neighbour != targetNode && newNodesToSearch.isEmpty()) { 
       newNodesToSearch.add(neighbour); 
       neighbour.setSelected(true); 
       edgeBetween(aNode, neighbour).setSelected(true); 
       sourceNode = neighbour; 
      } 
      if (neighbour == targetNode) { 
       sourceNode = null; 
       targetNode = null; 
       return; 
      } 
     } 
    } 
    if(sourceNode != null &&targetNode != null) { 
     findPathBetween(sourceNode, targetNode); 
    } 
} 

Answer 1

您正在将递归状态存储在递归函数中，并且不会将它传递给下一次迭代。因此，您只需反复运行一个函数而不更改其参数和影响其执行的状态。

我不想纠正你的代码，因为我不得不猜测你的意图，以提供一个很好的解释。

无论如何，我认为你试图实施DFS，所以我建议你看看一些工作实现。只是谷歌他们，有很多，例如this one附带一块theory，很简单，写的是Robert Sedgewick，所以可以信任。