-1

親と子へのリンクを持つノードを含むダイアグラムコントロールを使用しています。木を平らにしたいのですが、順番に。これを行うための最も速くて最も効率的な方法は何ですか。できればC＃で。

これが木の例です。注文の適切な説明を思い付くのに苦労しているので、お詫び申し上げます。順序には、作成順にすべてのノードがリストされている必要があります。たとえば、ツリーブローでは、有効な順序は（Root、A、B、C、G、D、H、E、F）になります。この順序により、親の前にノードがリストに追加されないことが保証されます。

私の質問をデモするための簡単な図

4

1 に答える 1

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

（テストされていないメモ帳コード）

この単純な実装では、深いグラフのスタックオーバーフローが発生することに注意してください。問題が発生した場合は、明示的なスタックまたは代替アルゴリズムに切り替えてください。

詳細については、ウィキペディアの記事「トポロジカルソート」を参照してください。

于 2012-11-22T12:45:03.477 に答える