Graph:
A graph is a collection of two sets V and E where V is a finite non-empty set of vertices and E is a finite non-empty set of edges.
- Vertices are nothing but the nodes in the graph.
- Two adjacent vertices are joined by edges.
- Any graph is denoted as G = {V, E}.
For example:
G = {{V1, V2, V3, V4, V5, V6}, {E1, E2, E3, E4, E5, E6, E7}}
Trees:
A tree is a finite set of one or more nodes such that –
- There is a specially designated node called root.
- The remaining nodes are partitioned into n>=0 disjoint sets T1, T2, T3, …, Tn
where T1, T2, T3, …, Tn are called the subtrees of the root.
Graph vs Tree:
| The basis of Comparison | Graph | Tree |
|---|---|---|
| Definition | Graph is a non-linear data structure. | Tree is a non-linear data structure. |
| Structure | It is a collection of vertices/nodes and edges. | It is a collection of nodes and edges. |
| Edges | Each node can have any number of edges. | If there is n nodes then there would be n-1 number of edges |
| Types of Edges | They can be directed or undirected | They are always directed |
| Root node | There is no unique node called root in graph. | There is a unique node called root(parent) node in trees. |
| Loop Formation | A cycle can be formed. | There will not be any cycle. |
| Traversal | For graph traversal, we use Breadth-First Search (BFS), and Depth-First Search (DFS). | We traverse a tree using in-order, pre-order, or post-order traversal methods. |
| Applications | For finding shortest path in networking graph is used. | For game trees, decision trees, the tree is used. |
Umesh Chandra 
Leave a comment