Wellcome to Mujtaba Khan blog

Home > Technology > IT > Programming > Graph and Tree Compared

Difference Between Graph and Tree

Jan 19th, 2011 | By Andrew

Graph vs Tree

Graph and Tree are used in data structures. There are certainly some differences between Graph and Tree. A set of vertices having a binary relation is called a graph whereas tree is a data structure that has a set of nodes linked to each other.

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

Other 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 any edge between two nodes.

Tree

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 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 top most 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 number of child nodes is called inner node or internal node.

Difference between graph and tree:
• A tree can be described as a specialized case of graph with no self loops and circuits.
• There are no loops in a tree whereas a graph can have loops.
• There are three sets in a graph i.e. edges, vertices and a set that represents their relation while a tree consists of nodes that are connected to each other. These connections are referred to as edges.
• In tree there are numerous rules spelling out how connections of nodes can occur whereas graph has no rules dictating the connection among the nodes.