News for hackers. Stuff that matters.

A comment on The Racket Blog: Dynamic Programming versus Memoization. Parent comment

Re:The Racket Blog: Dynamic Programming versus Memoization by pilgrim689 on Sunday August 26, 2012 @10:23AM (#4435143)
A DAG has directed edges, whereas a tree does not. Also, a node in a tree can only have 1 parent.

Here's an example of a DAG that can't be a tree because of the edge directions:

http://en.wikipedia.org/wiki/File:Directed_acyclic_graph_3.s...

[ Parent | on HN ]
Re:The Racket Blog: Dynamic Programming versus Memoization by Evbn on Sunday August 26, 2012 @02:50PM (#4435853)
Trees are commonly directed. Single in edge per node is the important distinction.
[ Parent | on HN ]
Re:The Racket Blog: Dynamic Programming versus Memoization by pilgrim689 on Sunday August 26, 2012 @03:25PM (#4435957)
Right, but then we'd be talking about the difference between a "directed tree" and a DAG...or a "rooted tree" and a DAG. But yea, I'm sure grand-parent gets the point by now
[ Parent | on HN ]
Re:The Racket Blog: Dynamic Programming versus Memoization by lukev on Sunday August 26, 2012 @05:40PM (#4436321)
Yep, thanks. I realize that in graph theory trees aren't directed, but in programming, saying "tree" almost always implies a parent-child relationship (i.e, directedness).

I was missing that nodes in a DAG can have two "parents", that makes sense.

[ Parent | on HN ]