algorithm - 貪欲なアルゴリズムを使用して DAG 内のすべてのノードにアクセスする

Question

貪欲なアルゴリズムを使用して、有向非巡回グラフ内のすべてのノードにアクセスしようとしています。深さ優先検索のようなものが機能すると考えていましたが、グラフをたどることができないため、これが DAG でどのように機能するかわかりません。

ありがとう。

Answer 1

はい、深さ優先探索（DFS）または幅優先探索（BFS）のいずれかを使用できます。たとえば、ThomasH.Cormenによる「IntroductiontoAlgorithms」などの優れたtexbookを確認してください。

「自分自身をさかのぼる」ためにエッジを使用する必要はありません。スタック（または再帰）またはキューのいずれかを使用します。

Answer 2

void dfs(node V) {
    mark V as visited;
    for each edge E, so that E.source = V, do {
        if(E.destination is not marked as visited) {
            dfs(E.destination);
        }
    }
}

それでおしまい。DFS（再帰）が行うことは、現在のインスタンスが終了したときに呼び出し元のインスタンスに戻ることです。すべてのアクティブなインスタンスを保持するためにスタックを使用するため、自分で戻る必要はありません。現在のノードで関数の実行が終了すると、自動的に前のノードにロールバックされます。