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

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?

Solution 1:

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.

Solution 2:

Instead of explaining I prefer to show it in pictures.

A tree in real time

A graph in real life use

Yes a map can be visualised as a graph data structure.

Seeing them like this makes life easier. Trees are used at places where we know that each node has only one parent. But graphs can have multiple predecessors(term parent is generally not used for graphs).

In real world, you can represent almost anything using graphs. I used a map, for example. If you consider each city as a node, it can be reached from multiple points. The points which lead to this node are called predecessors and the points which this node will lead to are called successors.

electrical circuit diagram, the plan of a house, computer network or a river system are few more examples of graphs. Many real world examples can be considered as graphs.

Technical diagram could be like this

Tree :

Graph :

Make sure to refer to below links. Those will answer almost all your questions on trees and graphs.

References :

1. http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-17-trees-and-graphs/#_Toc362296541

2. http://www.community-of-knowledge.de/beitrag/data-trees-as-a-means-of-presenting-complex-data-analysis/

3. Wikipedia

Solution 3:

The other answers are useful, but they're missing the properties of each:

Graph

^{Undirected graph, image source: Wikipedia}

^{Directed graph, image source: Wikipedia}

• Consists of a set of vertices (or nodes) and a set of edges connecting some or all of them
• Any edge can connect any two vertices that aren't already connected by an identical edge (in the same direction, in the case of a directed graph)
• Doesn't have to be connected (the edges don't have to connect all vertices together): a single graph can consist of a few disconnected sets of vertices

• Could be directed or undirected (which would apply to all edges in the graph)
  As per Wikipedia:

  For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person A can shake hands with a person B only if B also shakes hands with A. In contrast, if any edge from a person A to a person B corresponds to A admiring B, then this graph is directed, because admiration is not necessarily reciprocated.

Tree

^{Image source: Wikipedia}

• A type of graph
• Vertices are more commonly called "nodes"
• Edges are directed and represent an "is child of" (or "is parent of") relationship
• Each node (except the root node) has exactly one parent (and zero or more children)
• Has exactly one "root" node (if the tree has at least one node), which is a node without a parent
• Has to be connected
• Is acyclic, meaning it has no cycles: "a cycle is a path [AKA sequence] of edges and vertices wherein a vertex is reachable from itself"

There is some overlap in the above properties. Specifically, the last two properties are implied by the rest of the properties. But all of them are worth noting nonetheless.

Solution 4:

Tree is special form of graph i.e. minimally connected graph and having only one path between any two vertices.

In graph there can be more than one path i.e. graph can have uni-directional or bi-directional paths (edges) between nodes

Also you can see more details: http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/