深度優先搜索的返回路徑

Question

我試圖通過深度優先搜索在圖中找到特定節點。我目前的（簡單的）實現正在工作，但只返回bool，即是否已找到該節點。

我想添加的功能從操作返回的路徑，因此，例如，如果我在下面的例子中搜索5，我會得到"1-2-3-5"，而不是隻true。

public class BinaryTreeNode 
{ 
    public List<BinaryTreeNode> Children { get; set; } 
    public int Data { get; set; } 
} 
public class DepthFirstSearch 
{ 
    private Stack _searchStack; 
    private BinaryTreeNode _root; 
    public DepthFirstSearch(BinaryTreeNode rootNode) 
    { 
     _root = rootNode; 
     _searchStack = new Stack(); 
    } 
    public bool Search(int data) 
    { 
     BinaryTreeNode _current; 
     _searchStack.Push(_root); 
     while (_searchStack.Count != 0) 
     { 
      _current = _searchStack.Pop(); 
      if (_current.Data == data) 
      { 
       return true; 
      } 

      foreach(BinaryTreeNode b in current.Children.AsEnumerable().Reverse()) 
       _searchStack.Push(b); 
     } 
     return false; 
    } 
} 

任何幫助表示讚賞。

Answer 1

只是另一種方式來做到這一點。 此方法在每個節點上存儲父級信息，並沿着樹並返回值。但是你的樹不是二叉樹，也許你應該把類名改爲TreeNode或其他東西。

static void Main(string[] args) 
{ 
    var root = createNode(); 
    var search = new DepthFirstSearch(root); 
    var result = search.Search(5); 
    var arr = result.getPath(); 
    arr.Reverse(); 
    Console.Write(String.Join("-",arr)); 
} 
public class DepthFirstSearch 
{ 
    private Stack _searchStack; 
    private BinaryTreeNode _root; 
    public DepthFirstSearch(BinaryTreeNode rootNode) 
    { 
     _root = rootNode; 
     _searchStack = new Stack(); 
    } 

    public BinaryTreeNode Search(int data) 
    { 
     BinaryTreeNode _current; 
     _searchStack.Push(_root); 
     while (_searchStack.Count != 0) 
     { 
      _current = (BinaryTreeNode)_searchStack.Pop(); 
      if (_current.Data == data) 
      { 
       return _current; 
      } 

      foreach (BinaryTreeNode b in _current.Children.AsEnumerable().Reverse()) 
       _searchStack.Push(b); 
     } 
     return null; 
    } 
} 

public class BinaryTreeNode 
{ 
    public BinaryTreeNode parent { get; set; } 
    public List<BinaryTreeNode> Children { get; set; } 
    public int Data { get; set; } 

    public List<int> getPath() 
    { 
     var list = new List<int>(){Data}; 

     if (parent != null) 
     { 
      list.AddRange(parent.getPath()); 
     } 
     return list; 
    } 
} 

Answer 2

最簡單的方法是在您的BinaryTreeNode類中存儲BinaryTreeNode Parent { get; set; }，如果沒有父節點，則爲null，否則爲節點的父節點。這些將在您最初構建樹時設置。然後，你可以簡單地返回（如果沒有被發現或null）被發現的節點，並經過家長來重建有什麼列表類似

List<int> path = new List<int>(); 
BinaryTreeNode found = new DepthFirstSearch(root).Search(); 
while(found != null) 
{ 
    path.Push(found.Data); 
    found = found.Parent; 
} 
string stringPath = String.Join("-", path); 

我不記得確切Push的語義，所以你可能最終不得不扭轉列表或追加到列表的末尾或類似的東西，而不是使用Push。

Answer 3

首先，樹形圖中的示例不是二叉樹節點，因爲第一個節點（根）有3個子節點。二叉樹應該有隻有兩個子節點的節點，一個叫做「左」，另一個叫「右」，因此「二叉樹」中的「bi」也是，你的BinaryTreeNode的實現有兩個好主意：

1. 一個名爲「Data」的值（節點需要存儲這個「data」）是正確的。但我建議而不是命名變量「數據」，因爲C＃中還有其他變量和庫，其中包含單詞「數據」。如何命名它「nodeData」？越具描述性和獨特性越好。

2. 你有正確的想法來存儲孩子，但其他BinaryTreeNodes列表列表是不正確的，因爲如果該列表意外地有超過2個孩子？再次，如果你願意，你可以做到這一點，但這將是一個「樹」，而不是「二叉樹」數據結構。怎麼樣，而不是：

   public List<BinaryTreeNode> Children { get; set; } 
   

做

public BinaryTreeNode LeftNode { get; set; } 
public BinaryTreeNode RightNode { get; set; } 

現在你的 「布爾搜索」 功能：

您正在推動一個節點的所有孩子到堆棧。根據定義，這幾乎是「廣度優先搜索」而不是「深度優先搜索」。 「寬度」，因爲您首先通過「行」（或「寬度」）存儲節點。認爲行0是根節點，行1是根的孩子，行2是根的孩子的孩子，...等等。使用堆棧的事實意味着您要搜索最後一個彈出到堆棧_searchStack的子節點。一個正確的寬度優先使用隊列而不是堆棧（FIFO vs FILO），但這超出了這個問題的範圍。

您的深度優先搜索應該集中在一次保存一個（且只有一個）節點。對於第一個根節點，您選擇一個孩子。然後你對這個孩子進行深度優先搜索。那個孩子會選擇其中的一個孩子，並且在那裏調用深度優先。等等。如果節點沒有子節點，則返回/退出該功能。節點完成一個孩子後，調用另一個孩子的深度優先搜索。深度優先搜索的一般概念是，在覆蓋任何兄弟節點之前，您想深入到樹中。

要回答你的問題：

一旦你成功實施DFS，你需要找到一個方法來「記住」它的父節點上，您已通過遍歷並建立從發現的子節點，邁向了一個字符串父節點，當你退出「深度」時。

所以在你的榜樣，後DFS發現 「5」 下來的樹，它會再上去樹： 3-5 2-3-5 1-2-3-5