Could anyone give a clear and concise explanation for when you use graphs vs when to use trees for data structures?
1 Answer
Trees are Graphs.
They are specifically directed, acyclic graphs where all child nodes only have one parent. If you need more than one parent then you use a DAG. If you need cycles or the graph needs to be undirected you'd use some kind of graph implementation. Note that the time and space complexity increases dramatically once you move into full graphs.
-
"where all child nodes have one parent": In order to speak of a child-parent relation you need a directed tree. In an undirected tree you can pick an arbitrary leaf as root (and define the parent-child relation accordingly). In fact, a DAG is a directed acyclic graph, and a tree is a DAG with no parallel paths. So I think you should define trees as "directed acyclic graphs where all child nodes have only one parent" or "directed acyclic graphs with a distinct root node such that there exists exactly one path from the root node to any other node".– GiorgioDec 2, 2012 at 1:11
-
typed undirected when I meant directed.– user28988Dec 2, 2012 at 1:13