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

103

42

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?

user918304

Posted 2011-09-14T21:49:32.640

Reputation: 659

Answers

114

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 search breath first or depth first. The same applies to Tree.

user785287

Posted 2011-09-14T21:49:32.640

Reputation: 1 285

7Graphs 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 – 2012-07-27T15:15:47.543

7@user785287 what you mean by centralized map representation? – Geek – 2013-03-27T15:42:09.813

21"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 – 2014-07-07T09:42:53.357

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 – 2015-11-20T23:11:37.973

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 – 2018-04-09T01:33:39.173

1@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 – 2018-06-11T15:14:44.853

75

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 :

  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

mk..

Posted 2011-09-14T21:49:32.640

Reputation: 8 045

5i like pictures +1 – iliketocode – 2015-11-23T23:45:06.047

5

Difference betweeen Graph and Tree Data Structure

Trees

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

  2. Tree is a special case of graph having no loops, no circuits and no self-loops.

  3. In tree there is exactly one root node and every child have only one parent.

  4. In trees, there is parent child relationship so flow can be there with direction top to bottom or vice versa.

5.Trees are less complex then graphs as having no cycles, no self-loops and still connected.

6.Tree traversal is a kind of special case of traversal of graph. Tree is traversed in Pre-Order, In-Order and Post-Order (all three in DFS or in BFS algorithm)

7.In trees, there are many rules / restrictions for making connections between nodes through edges.

8.Trees come in the category of DAG : Directed Acyclic Graphs is a kind of directed graph that have no cycles.

9.Different types of trees are : Binary Tree , Binary Search Tree, AVL tree, Heaps.

10.Tree applications: sorting and searching like Tree Traversal & Binary Search.

11.Tree always has n-1 edges.

12.Tree is a hierarchical model.

Graphs

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

    1. Graph can have loops, circuits as well as can have self-loops.

3.In graph there is no such concept of root node.

4.In Graph there is no such parent child relationship.

5.Graphs are more complex in compare to trees as it can have cycles, loops etc

6.Graph is traversed by DFS: Depth First Search and in BFS : Breadth First Search algorithm

7.In graphs no such rules/ restrictions are there for connecting the nodes through edges.

8.Graph can be Cyclic or Acyclic.

9.Heaps. There are mainly two types of Graphs : Directed and Undirected graphs.

10.Graph applications : Coloring of maps, in OR (PERT & CPM), algorithms, Graph coloring, job scheduling, etc.

  1. In Graph, no. of edges depend on the graph.

12.Graph is a network model.

Example Tree:

enter image description here

Graph:

enter image description here

coding_ninza

Posted 2011-09-14T21:49:32.640

Reputation: 360

2

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/

Bipon Biswas

Posted 2011-09-14T21:49:32.640

Reputation: 5 813

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.

Rajan Kumar Kharel

Posted 2011-09-14T21:49:32.640

Reputation: 69

0

A tree is a digraph such that:

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

  1. You can remove either the assumption that it is acyclic
  2. 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

  1. 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

BPL

Posted 2011-09-14T21:49:32.640

Reputation: 5 440

0

In tree, each node has exactly one predecessor node, except the root node, and one or two successors nodes. It can be traversed by using In-order, Pre-order and Post-order 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 predecessors nodes and successors nodes. The graph is traversed by using Depth First Search (DFS) and Breath 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.

user10514540

Posted 2011-09-14T21:49:32.640

Reputation:

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.

duffymo

Posted 2011-09-14T21:49:32.640

Reputation: 267 937

"Confusing "graph" for "map" is very confusing." :) – cpz – 2014-07-17T22:53:27.460

1Saying "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 – 2017-06-30T18:41:21.027

I don't care six years later. Surely you can use your time better here. – duffymo – 2017-06-30T18:42:19.887

1Sorry, I mean the graph, I typed the map. – user918304 – 2011-09-14T23:40:53.563

-1

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.

Narender sharma

Posted 2011-09-14T21:49:32.640

Reputation: 17