# Tree vs Graphs in search

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

-

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

You can use graphs and trees for both modeling a problem and solving a problem, but sometimes you can convert a graph to a tree by clipping connections to make the problem easier to solve.

Since you ask for simple examples I will give an example for modeling. If you were to model roads you would use a graph since roads can form a circuit, and thus you need a graph. If you were to model a river and its branches, you would use a tree since rivers don't flow in circles. Once could argue that you need a directed acyclic graph for rivers because they have islands, but this is just a simple example.

-