3 ms·
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 tr
by nandemo 14y ago
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.
- ot 14y agoThat'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 14y agoYou're totally right (I had a thinko and managed to miss the D in the DAG). My apologies for the misinformation.
- qlkzy 14y agoTrees 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.
- deleted 14y ago[deleted]
- shasta 14y agoA tree is a DAG that's simply connected.