从Tree（图）获取有序列表的最有效方法是什么？

我正在使用一个图表控件，其中包含一个带有指向其父母及其子女的链接的节点。 我想扁平化树，但要按顺序。 什么是最快和最有效的方式来做到这一点; 最好用C＃。

这是一个树的例子。 我很难提出对订单的很好的描述，所以我很抱歉。 订单应按照其创建顺序列出所有节点。 例如，在树木击打中，有效顺序是（Root，A，B，C，G，D，H，E，F）。 这个命令保证没有节点被添加到它的父节点之前的列表中。

---

你的图不是树，因为一个节点可以有多个父节点。 我假设你有一个有向无环图（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();
}

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

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

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

链接地址: http://www.djcxy.com/p/30467.html

上一篇: What is the most efficient way to get an ordered list from a Tree (Diagram)?

下一篇: Efficient delete of a tree data structure