Hacker News new | past | comments | ask | show | jobs | submit login

A tree is a DAG that is connected: if a and b are nodes of a tree, there is a path between a and b. But in general a DAG doesn't have to be connected. So all trees are DAGs but not all DAGs are trees: some are forests i.e. unions of trees.



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.


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


Trees are, in general, undirected (although it is often convenient to treat edges in rooted trees as being all directed towards or away from the root, to determine whether or not a graph is a tree it is necessary to consider the edges as undirected).

A tree is a connected undirected acyclic graph (or, equivalently, an undirected graph in which there is exactly one path between any pair of vertices).

A DAG may represent a tree (usually rooted) or it may not. Not all connected DAGs are trees e.g.:

a->b, a->c, b->d, c->d is a DAG, but not a tree.


A tree is a DAG that's simply connected.




Join us for AI Startup School this June 16-17 in San Francisco!

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

Search: