contador Saltar al contenido

Difference between tree and graph

Tree and graph fall into the category of nonlinear data structure where the tree offers a very useful way of representing a relationship between nodes in a hierarchical structure and the graph follows a network model. Tree and graph are differentiated by the fact that a tree structure must be connected and can never have loops while there are no such restrictions in the graph.

A nonlinear data structure consisting of a collection of elements that are distributed over a plane, which means that there is no such sequence between elements as it exists in a linear data structure.

Comparative chart

Basis for comparing TreeGraph
Pathway Only one between two vertices. more than one route allowed.
Root node It has exactly one root knot. The chart does not have a root node.
Loops Loops are not allowed. The graph can have loops.
complexity Less complex More complex in comparison
Crossing techniques Pre-order, in-order and post-order. Search in breadth and search in depth.
Number of edges n-1 (where n the number of nodes) Undefined
Type of model Hierarchical Network

Definition of tree

A tree a finite collection of data items usually referred to as nodes. As mentioned above, a tree is a nonlinear data structure that organizes data elements in an orderly order. used to show a hierarchical structure between the various data elements and organizes the data in branches that relate the information. Adding a new edge to a tree results in a circuit or circuit formation.

There are different types of trees such as a binary tree, binary search tree, AVL tree, threaded binary tree, tree B, etc. Data compression, file archiving, arithmetic expression manipulation and game trees are some of the applications of the data structure tree.

Tree properties:

  • There is a designated node at the top of the tree, known as the tree root.
  • The remaining data elements are divided into disjoint subsets which they refer to as a substructure.
  • The tree expanded in height downwards.
  • A tree must be connected, which means that there must be a path from one root to all the other nodes.
  • It does not contain any rings.
  • A tree has n-1 edges.

There are various terms associated with trees such as terminal node, edge, level, grade, depth, forest, etc. Among these terms, some of them are described below.

  • board : a line connecting two nodes.
  • Level – A tree divided into levels so that the root node is at level 0. So its immediate children are at level 1, and its immediate children are at level 2 and so on up to the terminal or leaf node.
  • degree : the number of sub-trees of a node in a given tree.
  • depth – the maximum level of any node in a given tree is also known as height .
  • Terminal node – The top level node is the terminal node while other nodes, with the exception of the terminal node and root, are known as non-terminal nodes.

Definition of the graph

A graphic also a nonlinear mathematical data structure that can represent various types of physical structure. It consists of a group of vertices (or nodes) and a set of edges that connect the two vertices. The vertices on the graph are represented as points or circles and the edges are displayed as arcs or line segments. A border represented by E (v, w) where vew are the pairs of vertices. Removing a board from a circuit or a connected graph creates a subgraph that a tree.

Charts are classified into various categories as direct, non-direct, connected, unconnected, simple and multi-graph. Computer network, transportation system, social network graph, electrical circuits and project planning are some of the applications of the graph's data structure. It is also used in the management technique called TO T (program evaluation and review technique) e CPM (critical path method) in which the structure of the graph is analyzed.

Properties of a chart:

  • A vertex in a graph can be connected to any number of other vertices using edges.
  • An edge can be bidirectional or direct.
  • An edge can be weighted.

In the graph we also use various terms such as adjacent vertices, path, cycle, degree, connected graph, complete graph, weighted graph, etc. We understand some of these terms.

  • Adjacent vertices – A vertex a adjacent to vertex b if there is an edge (a, b) or (b, a).
  • Path : a path from a random vertex w to an adjacent sequence of vertices.
  • Cycle : a path in which the first and the last vertex are the same.
  • degree : a number of edges incident on a vertex.
  • Connected chart – If there is a path from a random vertex to any other vertex, then that graph known as a connected graph.

Key differences between tree and graph

  1. In a tree there is only one path between two vertices, while a graph can have one-way and two-way paths between nodes.
  2. In the tree, there is exactly one root node and each child can have only one parent. By contrast, the concept of the root node does not exist in a graph.
  3. A tree cannot have loops and self-loops while the graph can have loops and self-loops.
  4. Charts are more complicated as they can have loops and self-loops. In contrast, trees are simple compared to the graph.
  5. The tree is traversed using the pre-order, in-order and post-order techniques. On the other hand, for the graphic traversal, we use BFS (First search width) and DFS (Depth First Search).
  6. A tree can have n-1 edges. In contrast, there is no predefined number of edges in the graph and depends on the graph.
  7. A tree has a hierarchical structure while the graph has a network model.

Conclusion

Graph and tree structure are the nonlinear data structure used to solve various complex problems. A graph is a group of vertices and edges in which an edge connects a pair of vertices while a tree considered as a minimally connected graph that must be connected and free from rings.