ノードは複数の親を持つことができるため、グラフはツリーではありません。有向非巡回グラフ(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();
}
(テストされていないメモ帳コード)
この単純な実装では、深いグラフのスタックオーバーフローが発生することに注意してください。問題が発生した場合は、明示的なスタックまたは代替アルゴリズムに切り替えてください。
詳細については、ウィキペディアの記事「トポロジカルソート」を参照してください。