從樹（圖）中獲取有序列表的最有效方法是什麼？

Question

我正在使用圖表控件，其中包含一個包含指向其父母及其子女的鏈接的節點。我想扁平化樹，但要按順序。什麼是最快和最有效的方式來做到這一點;最好用C＃。

這裏是一個樹的例子。我很難提出對訂單的很好的描述，所以我很抱歉。訂單應按照其創建順序列出所有節點。例如，在樹木擊打中，有效順序是（Root，A，B，C，G，D，H，E，F）。這個命令保證沒有節點被添加到它的父節點之前的列表中。

Answer 1

您的圖形沒有樹，因爲一個節點可以有多個父母。我假設你有一個directed acyclic graph (DAG)。您的有序列表稱爲該有向圖的toplogical ordering，當且僅當該圖是非循環圖時才存在。幸運的是，這樣的排序可以用線性運行時間產生。

您可以用深度優先搜索從根（S）開始這樣做：

public static IEnumerable<Node> GetTopologicalGraphOrdering(IEnumerable<Node> roots) 
{ 
    var list=new List<Node>(); 
    var visited=new HashSet<Node>(); 

    Action<Node> visit = null; 
    visit = (n)=> 
    { 
     if(visited.Add(n) 
     { 
      foreach(Node child in n.Children) 
      { 
       visit(child); 
      } 
      list.Add(n) 
     } 
    } 

    foreach(Node n in roots) 
    { 
     visit(n); 
    } 

    return list.Reverse(); 
} 

（未經測試的記事本代碼）

注意這個天真的實施將導致深堆棧溢出圖表。切換到顯式堆棧或替代算法，如果這成爲一個問題。

閱讀維基百科文章Topological sorting瞭解更多詳情。