有向非巡回グラフ

Question

私はそれを説明することができます9

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

誰かがページ上の有向非巡回グラフを理解する問題がありますか？

Answer 1

これが一般的な理解であれば、このように考えることができます。それは方向性を持っているため「指示」です。それは一方的に行くので "非周期的"です。次に、ある方向に一方向にナビゲートする方法としてグラフを考えてみましょう。

例として辞書の記憶域に適用されていると考えると、非常に便利です。辞書内のすべての単語をフラットテキストファイルとして保存するのではなく、代わりにDAGとして保存することができます。これの利点は、それがはるかに少ないスペースを占有し、ルックアップを行うために非常に速くなることである。

したがって、「hello」のような単語を別の文字で構成されたグラフとして保存します。各文字は「ノード」になります。 "h"から、あなたはここでどこから行くのですか？グラフは "e"に、 "e"は "l"に、というように指示します。

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

これが役に立ちます。 DAGの私の経験は、私が辞書のためにそれを実装したように、非常に特定の単語です。これがあなたの理解に貢献することを願っています。他の人がより良い理解を持っている、あるいは私が何かを虚偽表現している場合は、コメントをしてください。