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?
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.
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 :
http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-17-trees-and-graphs/#_Toc362296541
http://www.community-of-knowledge.de/beitrag/data-trees-as-a-means-of-presenting-complex-data-analysis/
Wikipedia
Difference betweeen Graph and Tree Data Structure
Trees
Tree is special form of graph ie minimally connected graph and having only one path between any two vertices.
Tree is a special case of graph having no loops, no circuits and no self-loops.
In tree there is exactly one root node and every child have only one parent.
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
In graph there can be more than one path ie graph can have uni-directional or bi-directional paths (edges) between nodes
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.
12.Graph is a network model.
Example Tree:
Graph:
上一篇: 用偶数个节点从树中获取森林