That's wrong, not all connected DAGs are trees. A DAG is a directed graph that h... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

ot on Aug 26, 2012 | parent | context | favorite | on: Dynamic Programming versus Memoization

That's wrong, not all connected DAGs are trees.

A DAG is a directed graph that has no (directed) loops. Consider the following:

     A
    / \
   v   v
  B     C
   \   /
    v v
     D

This is a DAG but not a tree, because it has an undirected loop but no directed loops.

nandemo on Aug 26, 2012 [–]

You're totally right (I had a thinko and managed to miss the D in the DAG). My apologies for the misinformation.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact