What's the difference between the data structure Tree and Graph?

search data-structures map tree
user918304 picture user918304 · Sep 14, 2011 · Viewed 96.4k times · Source

Academically speaking, what's the essential difference between the data structure Tree and Graph? And how about the tree based search and Graph based search?

Answer

user785287 picture user785287 · Oct 10, 2011

A Tree is just a restricted form of a Graph.

Trees have direction (parent / child relationships) and don't contain cycles. They fit with in the category of Directed Acyclic Graphs (or a DAG). So Trees are DAGs with the restriction that a child can only have one parent.

One thing that is important to point out, Trees aren't a recursive data structure. They can not be implemented as a recursive data structure because of the above restrictions. But any DAG implementation, which are generally not recursive, can also be used. My preferred Tree implementation is a centralized map representation and is non recursive.

Graphs are generally searched breadth first or depth first. The same applies to Tree.

Related questions

How to implement a binary tree?

Which is the best data structure that can be used to implement a binary tree in Python?

Read More
O(klogk) time algorithm to find kth smallest element from a binary heap

We have an n-node binary heap which contains n distinct items (smallest item at the root). For a k<=n, find a O(klogk) time algorithm to select kth smallest element from the heap. O(klogn) is obvious, but …

Read More
grep a file, but show several surrounding lines?

I would like to grep for a string, but also show the preceding five lines and the following five lines as well as the matched line. How would I be able to do this?

Read More