Глубина первого поиска в java - как вернуться к родительскому узлу?

Question

Я пытаюсь сделать первый поиск глубины в Java рекурсивно. На данный момент код проходит через мой график отлично, но он никогда не возвращается, чтобы найти маршрут, когда у них больше нет узлов для посещения. Честно говоря, у меня есть блок менталитета. Каким будет лучший способ вернуться к родительскому узлу?

Вот мой код до сих пор:

private final Map<Character, Node> mNodes; 
private final List<Edge> mEdges; 

public DepthFirstSearch(Graph graph){ 
    mNodes = graph.getNodes(); 
    mEdges = new ArrayList<>(graph.getEdges()); 
    for(Node node : mNodes.values()){ 
     node.setVisited(false); 
    } 
} 

public void depthFirstSearch(Node source){ 
    source.setVisited(true); 
    List<Node> neighbours = source.getNeighbours(mEdges); 
    for(Node node : neighbours){ 
      if(!node.isVisited()){ 
       System.out.println(node.getName()); 
       depthFirstSearch(node); 
      } 
     } 
    } 

И код getNeighbour:

public List<Node> getNeighbours(List<Edge> edges) { 
     List<Node> neighbours = new ArrayList<>(); 
     for(Edge edge : edges){ 
      if(edge.getFrom().equals(this)){ 
       neighbours.add(edge.getTo()); 
      } 
     } 
     return neighbours; 
    } 

код Добавленная пытается идею Jager в:

public void depthFirstSearch(Node source){ 
     source.setVisited(true); 
     List<Edge> neighbours = source.getNeighbouringEdges(mEdges); 
     for(Edge edge : neighbours){ 
       if(!edge.getTo().isVisited()){ 
        System.out.println(edge.getTo().getName()); 
        depthFirstSearch(edge.getTo()); 
       }else{ 
        depthFirstSearch(edge.getFrom()); 
       } 
      } 
     } 

Answer 1

Гадать: вы «получение «соседи для mEdges, который, кажется, является полем окружающего пространства класс.

Скорее всего, вы должны спросить у каждого узла свои собственные края при его посещении.

Answer 2

Ну, обычно у вас есть корневой узел с детьми. У каждого ребенка могут быть свои дети. Таким образом, вы предпочли бы сделать:

public void depthFirstSearch(Node source) 
{ 
    for(Node node : source.getChildren()) 
    { 
     System.out.println(node.getName()); 
     depthFirstSearch(node); 
     // and right here you get your back tracking implicitly: 
     System.out.println("back at " + node.getName()); 
    } 
} 

Обратите внимание, что у меня нет необходимости для члена visited ...

Edit:

Теперь, когда вы предоставили вашу структуру данных, позвольте мне предложить другой подход:

class Node 
{ 
    // all that you have so far... 

    private char mId; 
    private List<Node> mChildren = new ArrayList<Node>(); 

    public char getId() 
    { 
     return mId; 
    } 
    public List<Node> getChildren() 
    { 
     return Collections.unmodifiableList(children); 
    } 

    // appropriate methods to add new children 
} 

Идентификатор заменяет ключ вашей карты. Тогда у вас просто есть корень Node mRoot, чтобы начать с чего-то. Это типичный способ реализации деревьев.

Возможно, вы захотите перейти от дочернего узла напрямую. Затем вам дополнительно понадобится private Node parent; в классе узлов (сразу же устанавливается this при добавлении дочернего элемента в закрытый список и значение null при удалении). Вы не будете использовать это для возврата, тем не менее, поэтому поиск по глубине сначала не изменится.