46

有向グラフを「シリアル化」する単純なアルゴリズムを探しています。特に、実行順序に相互依存関係がある一連のファイルがあり、コンパイル時に正しい順序を見つけたいと考えています。私はそれがかなり一般的なことであるに違いないことを知っています-コンパイラは常にそれを行います-しかし、私のgoogle-fuは今日弱いです。このための「頼りになる」アルゴリズムは何ですか?

4

4 に答える 4

63

トポロジカルソート(ウィキペディアより):

グラフ理論では、有向非巡回グラフ (DAG) のトポロジカル ソートまたはトポロジカル順序付けは、各ノードがアウトバウンド エッジを持つすべてのノードの前に来るノードの線形順序付けです。すべての DAG には、1 つ以上のトポロジカル ソートがあります。

擬似コード:

L ← Empty list where we put the sorted elements
Q ← Set of all nodes with no incoming edges
while Q is non-empty do
    remove a node n from Q
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into Q
if graph has edges then
    output error message (graph has a cycle)
else 
    output message (proposed topologically sorted order: L)
于 2008-08-07T10:53:31.237 に答える
1

グラフにサイクルが含まれている場合、ファイルに許可された実行順序はどのように存在するのでしょうか? グラフにサイクルが含まれている場合、解決策がないように思えますが、これは上記のアルゴリズムによって正しく報告されます。

于 2009-01-23T15:09:27.690 に答える
1

これを必要とするツールは単純に深さ優先の方法でツリーをたどり、リーフにヒットしたら、それを処理 (コンパイルなど) してグラフから削除する (または処理済みとしてマークし、すべてのリーフを持つノードを処理する) ことを期待します。葉として処理されます）。

DAG である限り、この単純なスタック ベースのウォークは簡単です。

于 2008-08-07T00:27:19.270 に答える
1

私はかなり素朴な再帰アルゴリズム (疑似コード) を思いつきました:

Map<Object, List<Object>> source; // map of each object to its dependency list
List<Object> dest; // destination list

function resolve(a):
    if (dest.contains(a)) return;
    foreach (b in source[a]):
        resolve(b);
    dest.add(a);

foreach (a in source):
    resolve(a);

これに関する最大の問題は、循環依存を検出する機能がないことです。つまり、無限再帰 (つまり、スタック オーバーフロー ;-p) に陥る可能性があります。私が見ることができる唯一の方法は、手動スタックを使用して再帰アルゴリズムを対話型アルゴリズムに切り替え、繰り返し要素のスタックを手動でチェックすることです。

誰かもっと良いものを持っていますか？

于 2008-08-07T00:30:52.180 に答える