89

有向グラフが非巡回かどうかを確認するにはどうすればよいですか? そして、アルゴリズムはどのように呼び出されますか? 参考になれば幸いです。

4

12 に答える 12

99

グラフをトポロジー的にソートしようとしますが、それができない場合はサイクルがあります。

于 2009-02-25T02:16:44.540 に答える
38

単純な深さ優先検索を行うだけでは、サイクルを見つけるのに十分ではありません。サイクルが存在しなくても、DFS でノードを複数回訪問することができます。どこから開始するかによっては、グラフ全体にアクセスできない場合もあります。

次のように、グラフの連結成分のサイクルを確認できます。発信エッジのみを持つノードを見つけます。そのようなノードがない場合は、サイクルがあります。そのノードで DFS を開始します。各エッジをトラバースするときは、エッジが既にスタックにあるノードを指しているかどうかを確認してください。これは循環の存在を示しています。そのようなエッジが見つからない場合、その接続されたコンポーネントにはサイクルはありません。

Rutger Prins が指摘しているように、グラフが接続されていない場合は、接続されたコンポーネントごとに検索を繰り返す必要があります。

参考までに、Tarjan の強連結成分アルゴリズムは密接に関連しています。また、サイクルが存在するかどうかを報告するだけでなく、サイクルを見つけるのにも役立ちます。

于 2009-02-25T02:08:37.350 に答える
15

Introduction to Algorithms本(第 2 版)の補題 22.11 は次のように述べています。

有向グラフ G は、G の深さ優先検索でバック エッジが生成されない場合にのみ、非巡回です。

于 2009-05-30T10:45:21.917 に答える
4

グーグルのインタビューでこんな質問がありました。

トポロジカル ソート

V は頂点の数、E はエッジの数である O(V + E) であるトポロジカルに並べ替えることができます。有向グラフは、これが可能である場合にのみ非巡回です。

再帰的なリーフの削除

リーフ ノードがなくなるまで再帰的に削除します。ノードが 1 つ以上残っている場合は、サイクルが発生します。私が間違っていなければ、これは O(V^2 + VE) です。

DFS スタイル ~ O(n + m)

ただし、効率的な DFS 風のアルゴリズム、最悪の場合の O(V + E) は次のとおりです。

function isAcyclic (root) {
    const previous = new Set();

    function DFS (node) {
        previous.add(node);

        let isAcyclic = true;
        for (let child of children) {
            if (previous.has(node) || DFS(child)) {
                isAcyclic = false;
                break;
            }
        }

        previous.delete(node);

        return isAcyclic;
    }

    return DFS(root);
}
于 2018-08-15T19:13:02.480 に答える
2

ShuggyCoUkが提供するソリューションは、すべてのノードをチェックしない可能性があるため、不完全です。


def isDAG(nodes V):
    while there is an unvisited node v in V:
        bool cycleFound = dfs(v)
        if cyclefound:
            return false
    return true

これには時間の複雑さがありますO（n + m）またはO（n ^ 2）

于 2009-02-25T01:29:06.680 に答える
1

DFS の実行中にバック エッジがあってはなりません。DFS の実行中に既にアクセスしたノードを追跡します。現在のノードと既存のノードの間にエッジが発生した場合、グラフにはサイクルがあります。

于 2014-10-28T05:14:07.023 に答える
1

これが古いトピックであることは承知していますが、将来の検索者のために、私が作成した C# 実装をここに示します (これが最も効率的であるとは言いません!)。これは、単純な整数を使用して各ノードを識別するように設計されています。ノードオブジェクトのハッシュと等号が適切に指定されていれば、好きなように装飾できます。

非常に深いグラフの場合、各ノードの深さでハッシュセットが作成されるため、オーバーヘッドが高くなる可能性があります (それらは幅全体で破棄されます)。

検索するノードとそのノードへのパスを入力します。

  • 単一のルートノードを持つグラフの場合、そのノードと空のハッシュセットを送信します
  • 複数のルート ノードを持つグラフの場合、これをそれらのノードの foreach でラップし、反復ごとに新しい空のハッシュセットを渡します。

  • 特定のノードの下のサイクルをチェックするときは、そのノードを空のハッシュセットと一緒に渡すだけです

    private bool FindCycle(int node, HashSet<int> path)
{

    if (path.Contains(node))
        return true;

    var extendedPath = new HashSet<int>(path) {node};

    foreach (var child in GetChildren(node))
    {
        if (FindCycle(child, extendedPath))
            return true;
    }

    return false;
}
于 2013-10-24T17:47:26.703 に答える