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

Question

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?

score 195 · Answer 1 · edited Mar 25 '20 at 16:27

195

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.

edited Mar 25 '20 at 16:27

djvg

11,722
5
72
103

answered Oct 10 '11 at 02:24

user785287

2,111
1
11
6

9

Graphs are very useful and can be used to model an enormous amount of things. Lots of other data structures can be seen as a graph with restrictions. For example, a singly linked list is a special case of a DAG. – J.R. Garcia Jul 27 '12 at 15:15
9

@user785287 what you mean by *centralized map representation*? – Geek Mar 27 '13 at 15:42
54

"Trees aren't a recursive data structure" is misleading and wrong. A tree *can* be represented with a non-recursive data structure (e.g. an array of edges; a full tree, like that underlying a binary heap, can be represented very compactly in an array; there are other *succinct* representations etc. etc.), but probably the most popular and useful way to represent them is using a recursive pointer-based structure. The representation is not unique for unrooted trees, but that is immaterial. – j_random_hacker Jul 07 '14 at 09:42
3

Not quite. Tree's don't necessarily have direction. https://en.wikipedia.org/wiki/Tree_(graph_theory) shows an example of a tree without direction. These are frequently used in biological contexts. – Michal Palczewski Nov 20 '15 at 23:11
The wikipedia article for tree states "a tree is an undirected graph" but all answers on this page say directed, can somebody explain the discrepancy? https://en.wikipedia.org/wiki/Tree_(graph_theory) – harshpatel991 Apr 09 '18 at 01:33
4

@harshpatel991 trees are not directed in the sense that: "X and Y are in a parent-child relation" doesn't have a direction. The individual relations though, "X is the child of Y", and "Y is a child of X", are directed relations. Direction indicates just that; the direction of 'movement'. In trees the idea of direction is not really needed unless it is meaningful (which is the most often case with trees). That's how I view it at least. – Kostas Mouratidis Jun 11 '18 at 15:14
A tree can be recursive but it's recursion can always be represented by a loop and always terminates, whereas some recursive graph's recursion may not terminate and it may not be reduced to a loop. – Mateja Petrovic Jan 13 '19 at 18:10
@harshpatel991 Good point, but a "tree" in the context of computer science most often refers to a "tree" in the context of graph theory that is additionally directed and rooted (a "directed rooted tree"). The article you posted talks about this in the third paragraph. – Niko Bellic Jul 12 '20 at 22:54
can you clarify what you mean by trees cannot be implemented as a recursive data structure? It's common to have a node class that points to a list of nodes (the same node class type) which I would have considered recursive. – Charlie Parker May 07 '21 at 18:54
tree is undirected while polytree is directed – Chen Li Sep 14 '22 at 03:12

Sandeep · Answer 2 · 2016-07-04T01:15:07.113

Instead of explaining I prefer to show it in pictures.

A tree in real time

A tree in real time

A graph in real life use

A real time graph

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 :

enter image description here

Graph :

enter image description here

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

References :

Bernhard Barker · Answer 3 · 2019-04-30T09:39:37.580

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.

Is "has to be connected" redundant given "each node (except **the** root node) has exactly one parent"? — JamesTheAwesomeDude, Aug 26 '22 at 14:30
@JamesTheAwesomeDude Yes, the last two properties (connected and acyclic) are implied by (or redundant given) the rest of the properties. But I noted all those properties because connected and acyclic are important terms in graph theory, while the rest of the properties are framed in terms of how we typically think of trees. — Bernhard Barker, Aug 29 '22 at 10:47

spirito_libero · Answer 4 · 2021-09-14T08:12:20.980

TREE :
 1. Only one path exist between two vertices (Nodes).
 2. Root node is the starting node of the tree.
 3. Tree doesn't have loops.
 4. Number of edges: n-1 (where n is number of nodes)
 5. Tree looks like Hierarchical
 6. All trees are graph.

GRAPH :
 1. More than one path is allowed between two vertices.
 2. There is no root node concept (we can start from any node).
 3. There can be loop in graph.
 4. Number of edges are not defined.
 5. Graph looks like Network.
 6. All graphs are not tree.

More detailed explanation you can find in this video -> https://www.youtube.com/watch?v=KVHrjVTp9_w

score 6 · Answer 5 · answered May 08 '17 at 04:03

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/

score 2 · Answer 6 · answered Jul 24 '20 at 12:00

Tree is basically undirected graph which not contain cycle,so we can say that tree is more restricted form of graph. However tree and graph have different application to implement various algorithm in programming. For example graph can be used for model road map and tree can be used for implement any hierarchical data structure.

score 2 · Answer 7 · answered Feb 13 '21 at 17:44

2

Simple concept is Tree doesn't have cycle formation and its unidirectional whereas Graph forms cycle and it will be Bidirectional in some cases and Unidirectional in another.

answered Feb 13 '21 at 17:44

Velkumaran A P

114
1
4

score 1 · Answer 8 · answered Jun 01 '18 at 15:33

A tree is a digraph such that:

a) with edge directions removed, it is connected and acyclic

You can remove either the assumption that it is acyclic

If it is finite, you can alternatively remove the assumption that it is connected

b) every vertex but one, the root, has indegree 1

c) the root has indegree 0

If there are only finitely many nodes, you can remove either the assumption that the root has indegree 0 or the assumption that the nodes other than the root have degree 1

Reference: http://www.cs.cornell.edu/courses/cs2800/2016sp/lectures/lec27-29-graphtheory.pdf

score 0 · Answer 9 · answered Feb 09 '14 at 18:17

0

one root node in tree and only one parent for one child. However, there is no concept of root node. Another difference is, tree is hierarchical model but graph is network model.

answered Feb 09 '14 at 18:17

Rajan Kumar Kharel

129
1
2

score 0 · Answer 10 · edited Apr 23 '19 at 10:43

In tree, each node (except the root node) has exactly one predecessor node and one or two successor nodes. It can be traversed by using In-order, Pre-order, Post-order, and Breadth First traversals. Tree is a special kind of graph that has no cycle so that is known as DAG (Directed Acyclic Graph). Tree is a hierarchical model.

In graph, each node has one or more predecessor nodes and successor nodes. The graph is traversed by using Depth First Search (DFS) and Breadth First Search (BFS) algorithms. Graph has cycle so it is more complex than tree. Graph is a network model. There are two kinds of graph: directed graphs and undirected graphs.

Tree nodes can have zero or more successor nodes, not just one or two. A binary tree limits the number of successors/children to 2, but every tree has leaf nodes with no children. — Aaron, Nov 29 '20 at 19:45

duffymo · Answer 11 · 2011-09-15T00:12:48.633

0

Trees are obvious: they're recursive data structures consisting of nodes with children.

Map (aka dictionary) are key/value pairs. Give a map a key and it will return the associated value.

Maps can be implemented using trees, I hope you don't find that confusing.

UPDATE: Confusing "graph" for "map" is very confusing.

Graphs are more complex than trees. Trees imply recursive parent/child relationships. There are natural ways to traverse a tree: depth-first, breadth-first, level-order, etc.

Graphs can have uni-directional or bi-directional paths between nodes, be cyclic or acyclic, etc. I would consider graphs to be more complex.

I think a cursory search in any decent data structures text (e.g. "Algorithms Design Manual") would give more and better information than any number of SO answers. I would recommend that you not take the passive route and start doing some research for yourself.

edited Sep 15 '11 at 00:12

answered Sep 14 '11 at 21:58

duffymo

305,152
44
369
561

1

Sorry, I mean the graph, I typed the map. – user918304 Sep 14 '11 at 23:40
"Confusing "graph" for "map" is very confusing." :) – cpz Jul 17 '14 at 22:53
2

Saying "graphs are more complex than trees" is like saying "Crows are more specialized than birds". Shouldn't we say instead that "All trees are graphs, but not all graphs are trees"? – dudewad Jun 30 '17 at 18:41

score -1 · Answer 12 · answered Mar 06 '13 at 18:31

In mathematics, a graph is a representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges.[1] Typically, a graph is depicted in diagrammatic form as a set of dots for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

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

12 Answers12

Graph

Tree

Linked