0

依存関係のリストがあります。たとえば、BLT はベーコン、レタス、トマトに依存していますが、今日のランチは BLT とトマトのスープに依存しています。関係を逆にしたい、つまり、すべての成分について、それらに依存するすべてのものをリストします。したがって、BLT と今日のランチの両方にベーコンが必要です。パッケージマネージャーがこれを実行できることは知っていますが、基礎となるアルゴリズムが必要です。ありがとう。

4

1 に答える 1

2

あなたが探しているのは、幅優先検索です。B が A に依存している場合、A が B に接続するグラフを作成します。次に、任意のノード (A と呼びます) から BFS を開始し、終了 (到達可能なすべてのノードがトラバースされる) まで、それに依存するものを検索し、各ノードに遭遇します。 BFS 中は A に依存します。

http://en.wikipedia.org/wiki/Breadth-first_search

于 2013-09-20T16:32:59.380 に答える