Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

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.

share|improve this answer
    
"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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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