c# - 从树（图表）中获取有序列表的最有效方法是什么？

Question

我正在使用一个图表控件，其中包含一个节点，该节点带有指向其父级和子级的链接。我想把树弄平，但要按顺序。最快、最有效的方法是什么？最好在 C# 中。

这是一个树的例子。我很难想出一个好的订单描述，所以我很抱歉。该顺序应按创建顺序列出所有节点。例如，在树吹中，有效的顺序是 (Root,A,B,C,G,D,H,E,F)。此顺序保证在其父节点之前不会将节点添加到列表中。

Answer 1

您的图不是树，因为一个节点可以有多个父节点。我假设你有一个有向无环图（DAG）。您的有序列表称为该有向图的拓扑排序，当且仅当该图是无环的时才存在。幸运的是，这样的排序可以通过线性运行时间产生。

您可以使用从根开始的深度优先搜索来执行此操作：

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();
}

（未经测试的记事本代码）

请注意，这种幼稚的实现将导致深度图的堆栈溢出。如果出现问题，请切换到显式堆栈或替代算法。

阅读维基百科文章拓扑排序了解更多详情。