Sunday 30 June 2013

differences between Graphs and Trees? [excluded Graphical Concept]

Topic
Graph
Tree


Rules & Restriction:
In general graph doesn’t really have any rules and restrictions.
Tree is the restricted specialized version of graph with numerous rules specially how to connect nodes.

Direction :
Graph can have Uni-directional or Bi-directional paths between nodes.
Tree has linear direction (only one path between each two vertices) that comes along with “Parent-children” relationship.

*point to be noted: one child can have only one parent (as it is in real.)

Circles and all :
Can be cyclic (or acyclic) or have loop, circuit and self loop.
Tree doesn't have any circles back or self loop or circuit or cycles.

Recursive Data :
No such thing.
Tree is Recursive Data Structure due to the nodes with children.

DAG:
Can only be cyclic or acyclic
Tree fits within the category of Directed Acyclic Graphs in short DAG (graph that has no cycles).

Complexity:
Graphs are more complex due to all the loops and cycles it got.

Trees are really easy to understand.
Connection:
In graph objects connects themselves by Links.

*in mathematical abstractions it calls Vertices or in between same pair it calls edges.

Tree is actually Minimally connected graph. In easy English its: one path between each two vertices.
Outlook:
It’s more likely a diagrammatic overview.
It’s more likely a flow looking overview.
(e.g. flow chart)

Root node:
No such thing.
Exactly only one root node.

Parent child relation:
No such thing.
In tree, there is parent child relationship for the sake of flow so there can be the direction top to bottom or vice versa.

Traversal kinds:
Graph traversed by DFS (depth First Search) and BFS (Breadth First Search) algorithm.
3 types:
a. Pre order
b. In order
c. post order
*all of these are in DFS or BFS algo.

Different types:
Basically only two types can be highlighted:
a. Directed graph
b. Undirected graph

There are actually too many. Like, Binary tree, Binary Search Tree, AVL tree, Heaps etc.
Number of edges:
No boundary.
Always have to have n-1 numbers of edges.

Model type:
Network model.
Hierarchical model




No comments:

Post a Comment