Difference between Graph and Tree in DSA

Graph

            A graph is a set of items that are connected by edges and each item is known as node or vertex. In other words, a graph can be defined as the set of vertices and there is a binary relation between these vertices.

             In an implementation of a graph, the nodes are implemented as objects or structures. The edges can be represented in different ways. One of the ways is that each node can be associated with an incident edges array. If the information is to be stored in nodes rather than edges then the arrays act as pointers to nodes and also represent edges. One of the advantages of this approach is that additional nodes can be added to the graph. Existing nodes can be connected by adding elements to arrays. But there is one disadvantage because time is required in order to determine whether there is an edge between the nodes.

           Another way to do this is to keep a two-dimensional array or matrix M that has Boolean values. The existence of edge from node I to j is specified by entry Mij. One of the advantages of this method is to find out if there is an edge between two nodes.

Tree

           The tree is also a data structure used in computer science. It is similar to the structure of the tree and has a set of nodes that are linked to each other.

          A node of a tree may contain a condition or value. It can also be a tree of its own or it can represent a separate data structure. Zero or more nodes are present in a tree data structure. If a node has a child then it is called parent node of that child. There can be at most one parent of a node. The longest downward path from the node to a leaf is the height of the node. The depth of the node is represented by the path to its root.

          In a tree, the topmost node is called root node. The root node has no parents as it is the topmost one. From this node, all tree operations begin. By using links or edges, other nodes can be reached from the root node. The bottom-most level nodes are called leaf nodes and they don’t have any children. The node that has a number of child nodes is called inner node or an internal node.