0

Could anyone give a clear and concise explanation for when you use graphs vs when to use trees for data structures?

9

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". – Giorgio Dec 2 '12 at 1:11
  • typed undirected when I meant directed. – World Engineer Dec 2 '12 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.