4 ms·
Isn't a tree just a graph that is directed and acyclic (DAG)? So a tree is just a subtype of a graph?
by OoooooooO 3y ago
Isn't a tree just a graph that is directed and acyclic (DAG)?
So a tree is just a subtype of a graph?
- ironSkillet 3y agoA tree is a subtype of graph. However, a DAG is not a tree if it has cycles once you forget direction, meaning paths can join up again after splitting. This distinction matters because when different paths "join up" again, there is often complicated data duplication/integration that is necessary in order order to combine the results. On a distributed system, it may mean data passing over a network, which you want to avoid.
- Ruphin 3y agoA tree is a subtype of a graph, but it is not the same as a DAG. A diamond-shaped directed graph (edges A->B, A->C, B->D, C->D) is a DAG, but not a tree.
- pxc 3y agoIn graph theory, trees are undirected. In computing, trees usually have two features that differentiate them from their more minimal graph theoretical cousins: they are (a) directed and (b) rooted (a particular vertex is designated as the root, and every vertex can be walked to from that vertex). But yeah. Some graphs are trees. And you can construct trees within graphs for efficiently navigating connected graphs, which is done in various important and famous algorithms.