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}}
A graph is a collection of vertices (also known as nodes) and edges that connect these vertices. Each edge represents a relationship or connection between two vertices.
Graphs can be directed or undirected, meaning that edges have a specific direction or they do not.
A directed graph is also known as a digraph. Graphs can also have weighted edges, where each edge has a weight or cost associated with it. Graphs can be represented in various ways, such as adjacency matrix or adjacency list.
Tree :
A tree is a special type of graph that is connected and acyclic, meaning that there are no cycles in the graph.
In a tree, there is a unique path between any two vertices, and there is a single vertex called the root that is used as the starting point for traversing the tree.
Trees can be used to model hierarchical relationships, such as the structure of a file system or the organization of a company.
Trees can be binary or non-binary. In a binary tree, each node has at most two children, while in a non-binary tree, each node can have any number of children.
Binary trees can be used to solve problems such as searching and sorting, as well as to represent expressions and parse 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.
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. |
| Structure cycle | A graph can be connected or disconnected, can have cycles or loops, and does not necessarily have a root node. | A tree is a type of graph that is connected, acyclic (meaning it has no cycles or loops), and has a single root node. |
| 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. |
| Node relationships | In a graph, nodes can have any number of connections to other nodes, and there is no strict parent-child relationship. | In a tree, each node (except the root node) has a parent node and zero or more child nodes. |
| Commonly used for | Graphs are commonly used to model complex systems or relationships, such as social networks, transportation networks, and computer networks. | Trees are commonly used to represent data that has a hierarchical structure, such as file systems, organization charts, and family trees. |
| Connectivity | In a graph, nodes can have any number of connections to other nodes. | In a tree, each node can have at most one parent, except for the root node, which has no parent. |
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
