DFS算法正在從右向左搜索

我已經編寫了深度優先搜索算法，但是它從樹的右側向左搜索。我可以從代碼中看到它爲什麼這樣做，但我無法想出一個解決方案來更改它，以便從左到右進行搜索。DFS算法正在從右向左搜索

public class DFS { 

    public LinkedList<Node> search(Node root, Node target) {  
     LinkedList<Node> open = new LinkedList<>(); 
     LinkedList<Node> closed = new LinkedList<>(); 

     open.addLast(root); 
     while (!open.isEmpty()) { 
      Node current = open.removeFirst(); 
      if (current.equals(target)) { 
       closed.addLast(current); 
       return closed; 
      } 
      else { 
       ArrayList<Node> children = current.getChildren(); 
       closed.addLast(current); 
       for (Node child : children) { 
        if (!open.contains(child) && !closed.contains(child)) { 
         open.addFirst(child); 
        } 
       } 
      } 
     } 
     return null; 
    } 
}

closed是按訪問順序訪問的節點列表。

Node.getChildren()按照添加它們的順序返回節點子項的ArrayList。

編輯

這裏是節點類：

public class Node { 

    private ArrayList<Node> children; 
    private String name; 

    public Node(String name){ 
     children = new ArrayList<Node>(); 
     this.name = name; 
    } 

    public ArrayList<Node> getChildren(){ 
     return new ArrayList<Node>(children); 
    } 

    public Node addChild(Node child){ 
     children.add(child); 
     return child; 
    } 

    public void removeChild(Node child){ 
     children.remove(child); 
    } 

    public String getName() { 
     return name; 
    } 

    public boolean equals(Node other){ 
     return (this.getName().compareTo(other.getName())==0); 
    } 
}

來源

2016-09-27 KOB

你爲什麼要做'children.remove（child）'，特別是在'children'循環中？ – user2357112

既然你指出了，我不知道它的目的是什麼！基本上我只是想放棄那個節點。我現在將編輯我的代碼 – KOB

@ user2357112固定。 – KOB

簡單的回答「如何避免從右到左」的問題是：

  ArrayList<Node> children = current.getChildren(); 
      closed.addLast(current); 
      // *** Not like this *** 
      // for (Node child : children) { 
      // if (!open.contains(child) && !closed.contains(child)) { 
      //  open.addFirst(child); 
      // } 
      //} 
      // **** But like this **** 
      for(int i=children.size()-1; i>=0; i--) { 
       Node child=children.get(i); 
       if (!open.contains(child) && !closed.contains(child)) { 
        open.addFirst(child); 
       } 
      } 
      // If you are **absolutely** sure your structure is a 
      // Tree (thus, no cycles) then testing against 
      // open/closed is unnecessary and the code can be simplified: as 
      // open.addAll(0, children);

您ALGO反正是有缺陷的：有沒有規定到飽和/丟棄在沒有樹一個下降通道結果（你永遠不會從closed中刪除） - 但這不在你的問題的範圍之內。

來源

2016-09-27 22:08:14

這完美的工作，我現在也明白了爲什麼通過在紙上寫出一個測試用例。謝謝。該算法作爲僞代碼給予我們，並且該任務要求編寫一個測試類，該類指出是否可以在目標節點上找到路徑 - 我認爲這是您指出的內容的保護。我們剛剛開始使用這些搜索算法，因此在這種情況下可能儘可能簡單。 – KOB

雖然我的答案是從「訪問順序」的角度出發的，但請注意，您已關閉的列表不會包含從根開始的下降路徑，而是包含您訪問過的所有節點，直到找到答案 - 包括失敗的分支*。如果分配要求您返回實際的「根路徑」，則您仍有工作要做。 –

我意識到這一點，但分配的範圍要求打印在目標節點之前訪問過的所有節點。謝謝你的幫助 – KOB

如果你真的DFS依賴於方向，扭轉你的孩子，或addfirst僅代替addlast僅？

來源

2016-09-27 21:35:40 Jaleks

的getChildren有1..1

元素然後你有一個堆棧「開放」，從中你在每次執行主循環時彈出的第一個元素。

通過將孩子推到堆棧的前面（addFirst）來填充該堆棧，然後對於1..n以n..1結尾（插入1，現在是第一個，插入2，現在是第一個，1是第二個，依此類推）。

彈出從最後一個索引打開，或將孩子推到堆棧的末尾，它應該工作，除非getChildren沒有按照您聲明的順序返回。

來源

2016-09-27 21:36:51 gia

在編寫這個DFS算法之前，我寫了一個BFS，其中唯一的區別就是你提出的解決方案。從最後一個索引彈出創建一個BFS算法。我測試過'getChildren（）'，它確實按照正確的順序返回列表。 – KOB

是的，你一直在編輯你的問題，代碼會改變每次訂購 – gia

DFS算法正在從右向左搜索

回答

相關問題