directed-acyclic-graphs - 有向非巡回グラフ

Question

9ページの有向非巡回グラフを理解するのに問題があります

http://mitpress.mit.edu/books/chapters/0262033844chap27.pdf

それを説明できる人はいますか？

Answer 1

それがあなたが必要とする一般的な理解であるならば、あなたはそれをこのように考えることができます。方向性があるので「方向性」があります。それは一方向に行くので「非周期的」。次に、グラフをある方向に一方向にナビゲートする方法と考えてください。

これを例として辞書の保存に適用すると考えると、非常に便利です。辞書にあるすべての単語をフラットテキストファイルとして保存するのではなく、DAGとして保存することもできます。これの利点は、占有するスペースがはるかに少なく、ルックアップを非常に高速に実行できることです。

したがって、「こんにちは」のような単語を、さまざまな文字で構成されるグラフとして保存します。各文字は「ノード」になります。「h」からあなたは大丈夫と言うでしょう、私はここからどこへ行きますか？グラフは、「e」、「e」から「l」などに移動します。

したがって、「グラフ」はナビゲーションの方法であり、「有向」および「非巡回」はそのナビゲーションがどのように行われるかを示します。

お役に立てれば。私のDAGの経験は、辞書に実装したため、非常に単語固有のものです。ご理解のほどよろしくお願いいたします。他の人がよりよく理解している場合、または私が何かを誤って伝えた場合は、コメントしてください。