通過有向圖找到路徑的遞歸lambda表達式？

我需要找到一個或多個複雜圖形結構的路徑。通過有向圖找到路徑的遞歸lambda表達式？

class Node 
{ 
    public string Value { get; set;} 
    public List<Node> Nodes { get; set;} 

    public Node() 
    { 
     Nodes = new List<Node>(); 
    } 
}

是什麼讓這個複雜的是，節點可以引用到早期的節點：該圖是使用類似於此建成。例如，

A - >ç - >電子 - >一個

我需要做的就是讓代表通過節點的路徑棧的列表，直到我得到了一個節點具體的價值。由於可能有一些非常大的路徑可用，我們可以有最大節點來嘗試。

List<Stack<Node>> paths = FindPaths(string ValueToFind, int MaxNumberNodes);

有沒有人有辦法建立這個（或類似的東西）？我在過去做過遞歸，但是由於某種原因，我總是在考慮這個問題。我的問題指定了一個lambda表達式，但使用lambda不一定是必需的。我會很感激任何解決方案。

附註：我從aku的this recursion question的優秀答案中解除了課程。雖然他下面顯示的優雅解決方案遍歷樹結構，但它似乎沒有足夠的靈活性來執行我所需的操作（例如，消除循環路徑和跟蹤成功的路徑）。

Action<Node> traverse = null; 
traverse = (n) => { Console.WriteLine(n.Value); n.Nodes.ForEach(traverse);}; 
traverse(root); // where root is the tree structure

編輯：

基於從意見和答案下面我在CodeProject上發現了一個優秀的解決方案在整個輸入。它使用A *路徑查找算法。 Here is the link.

來源

2008-12-28 Sailing Judo

如果你有循環引用，它不再是一棵樹。我認爲「定向圖」是正確的術語。 – 2008-12-28 19:07:07

謝謝。我知道我沒有使用正確的術語，但我不知道什麼是正確的，所以我只是試着盡我所能地解釋它。我現在就搜索正確的術語。 – 2008-12-28 20:10:11

如果你的問題是關係到尋路，你可能想谷歌的「造星」或「A *」。它是一種常用且高效的尋路算法。有關與您的問題直接相關的示例，請參閱this article。

您可能也想看看Dijsktra Algorithm

來源

2008-12-28 20:48:40 Brann

我不確切地知道你想達到什麼，但是這個循環引用問題通常是通過標記已經訪問過的節點來解決的。只需使用一個字典來跟蹤已經訪問過的節點，這樣就不會循環。

例子：

public void ExploreGraph(TreeNode tn, Dictionary<TreeNode, bool> visitednodes) 
     { 

      foreach (Treenode childnode in tn.Nodes) 
      { 
       if (!visitedNodes.ContainsKey(childnode)) 
       { 
        visitednodes.Add(childnode); 
        ExploreGraph(childnode, visitednodes); 
       } 
      } 
     }

來源

2008-12-28 17:19:53 Brann

我不知道你想要的輸出是否所有路徑，目標，最好路徑的目標（通過一些指標，如路徑長度），或只是任何路徑的目標。

假設是後者，我想用遞歸戰略開始，包括布萊恩概述的訪問節點的跟蹤，並進行以下更改：

添加參數來表示目標受到追捧，收藏成功的路徑，以及從一開始的當前路徑。
當進入該目標相匹配的節點，當前路徑（加上當前節點）添加到成功的路徑列表。
擴展與當前節點上創建任何遞歸調用傳遞的路徑當前路徑。
調用初始ExploreGraph呼叫用空路徑和成功的路徑的空列表。

完成後，您的算法將遍歷整個圖形，並且將捕獲到目標的不同路徑。

這只是一個速寫，但你應該能夠加以充實您的特定需求。

來源

2008-12-28 20:50:59

通過有向圖找到路徑的遞歸lambda表達式？

回答

相關問題