Directed acyclic graph

I have problems understanding the directed acyclic graph on page 9

http://mitpress.mit.edu/books/chapters/0262开发者_StackOverflow社区033844chap27.pdf

Someone who can explain it?

---

If it's a general understanding you require, you could think of it this way. It's "directed" because it has a direction. "acyclic" because it goes one way. Then, think of the graph as a way to navigate one way, in a direction.

If you consider this as applied to the storage of a dictionary as an example, it can be very useful. Rather than store every single word in the dictionary as a flat text file, you could instead store them as a DAG. The benefit of this is that it takes up much less space, and can be very fast to do look ups.

So, you would store a word like "hello" as a graph made up of different letters. Each letter would be a "node". From "h" you would say ok, where do I go from here? The graph directs you to "e", and from "e" to "l" and so on.

A "graph" therefore is a method of navigation, and "directed" and "acyclic" refer to how that navigation is done.

Hope this helps. My experience of DAGs is very word specific as I implemented it for a dictionary. I hope this contributes to your understanding. If others have better understanding or if I have misrepresented anything please do comment.