尋找在vb.net或c＃中的算法，但我不知道它的名字！

Question

我會盡我所能解釋算法應該做什麼：

有一個類'食譜'。每個食譜都可以包含其他食譜，但不能包括其自身或包含它的任何其他食譜。

所以，一個簡單的例子是，我們只有兩個食譜& B.

如果A對B首先增加了B，後來不能添加，因爲它會導致一個循環。

一個更復雜的例子是：

A，B，C

（1）配方Ç再添乙
（2）配方B加上甲
（3）配方A試圖將C ，但不能因爲這種關係。 C - B - 答：

我可以自己做這個，我只是想知道這是一個標準的命名算法，我可以獲得最佳解決方案。

謝謝

Answer 1

Topological ordering/loop detection？ （如果檢測到循環，則拓撲排序算法停止。）

這應該與您正在做的事情接近。

Answer 2

在數學/計算機科學術語中，您的結構稱爲directed graph。你想要一個「Directed Acyclic Graph」 - 這是一個沒有周期的。

要找出圖表中是否有循環，您可以使用一種算法，稱爲Topological sorting。它試圖重新排列一個圖，以便如果A指B，那麼A總是在B之前出現。如果圖形有循環，它會停止。

如果您想查找圖表中的所有周期（這對錯誤消息有幫助），那麼this stackoverflow question and answer會提供很多幫助。

作爲背景：
圖 =由邊鏈接節點任何東西（在你的情況節點是配方和引用邊緣）。
定向 =邊緣有方向。在你的情況下，這是真的，因爲'A'是指'B'，而不是'A'和'B'。

Answer 3

看看cycle detection。

Answer 4

鑑於你的條件，我認爲你最終會得到的結構是DAG。

所以我們可以找出是否添加新節點創建循環，如果是的話，那麼我們不添加它，否則我們添加它。

class Foo 
{ 
    public List<Foo> Reachables { get; set; } 

    public Foo() 
    { 
     this.Reachables = new List<Foo>(); 
    } 

    public bool Add(Foo other) 
    { 
     this.Reachables.Add(other); // add it 

     if(other.IsReachable(this)) // then see if it create a cycle 
     { 
      this.Reachables.Remove(other); // if yes remove it 
      return false; 
     } 
     else 
     { 
      return true; // else keep it 
     } 
    } 

    private bool IsReachable(Foo goal) 
    { 
     // BFS 

     Queue<Foo> nextQueue = new Queue<Foo>(); 
     List<Foo> traversed = new List<Foo>(); 

     bool found = false; 

     nextQueue.Enqueue(this); 

     while (!found) { 

      Foo node = null; 

      try { node = nextQueue.Dequeue(); } 
      catch { break; } 

      traversed.Add(node); 

      if (node.Equals(goal)) { 
       found = true; 
       break; 
      } 
      else 
      { 
       foreach (Foo neighbor in node.Reachables) 
        if (!traversed.Contains(neighbor) && !nextQueue.Contains(neighbor)) 
         nextQueue.Enqueue(neighbor); 
      } 
     } 
     return found; 
    } 

} 

class Program 
{ 
    static void Main(string[] args) 
    { 
     Foo A = new Foo(); 
     Foo B = new Foo(); 
     Foo C = new Foo(); 

     Console.WriteLine(C.Add(B)); 
     Console.WriteLine(B.Add(A)); 
     Console.WriteLine(A.Add(C)); 
     Console.WriteLine(C.Add(A)); 

    } 
} 

輸出：在該上下文中

True 
True 
False 
True