# Difference between graph and tree

**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 = {{V_{1}, V_{2}, V_{3}, V_{4}, V_{5}, V_{6}}, {E_{1}, E_{2}, E_{3}, E_{4}, E_{5}, E_{6}, E_{7}}} **Tree**** :**

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 T
_{1}, T_{2}, T_{3}, …, T_{n}

where T_{1}, T_{2}, T_{3}, …, T_{n}are called the subtrees of the root.

The concept of a tree is represented by following Fig.

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