Graph path finder

Question

Я пытаюсь найти путь между двумя узлами (sourcenode и targetnode). я придумал этот код, но я не могу заставить его рекурсивно найти путь. Я даже устанавливаю узлы в null, если целевой узел найден, но я продолжаю получать ошибку переполнения стека.

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, поэтому я предлагаю вам взглянуть на некоторые рабочие реализации. Просто Google их, есть много, например. this one поставляется с куском theory, прост, и был написан Robert Sedgewick, поэтому ему можно доверять.