Skip to main content

Difference between Tree and Graph Data Strucutre

In this tutorial you will learn about the difference between tree and graph.

Both trees and graphs are two well known mostly used data structures in algorithms.

Tree Data Structure

In Computer science, a tree is a widely used Abstract Data Structure (ADT). It can be defined recursively as a collection of nodes, where each node contains a value, starting with root node and list of references to other nodes (children), with the constraint, that no reference from it, is called leaf node.

Graph Data Structure

In Computer science, graph also an abstract data structure (ADT), that is mean to implement undirected graph and directed graph concepts of mathematics especially the field of graph theory. Graph is a mathematical representation of a set of objects and relationships or links between objects. We represent objects as nodes or vertices in graph and relations between vertices as edges or arcs. So, we can define that graph is set of vertices V and set of edges E. These edges may be directed or undirected.

Now let’s see what are the differences between graph and tree in tabular form.

Difference between Tree and Graph

Trees Graphs
1. A tree is a special kind of graph that there are never multiple paths exist. There is always one way to get from A to B. 1. A graph is a system that has multiple ways to get from any point A to any other point B.
2. Tree must be connected. 2. Graph may not be connected.
3. Since it connected we can reach from one particular node to all other nodes. This kind of searching is called traversal. 3. Traversal always not applicable on graphs. Because graphs may not be connected.
4. Tree contains no loops, no circuits. 4. Graph may contain self-loops, loops.
5. There must be a root node in tree. 5. There is no such kind of root node in graphs
6. We do traversal on trees. That mean from a point we go to each and every node of tree. 6. We do searching on graphs. That means starting from any node try to find a particular node which we need.
7. pre-order, in-order, post-order are some kind of traversals in trees. 7. Breath first search, Depth first search, are some kind of searching algorithms in graphs.
8. Trees are directed acyclic graphs. 8. Graphs are cyclic or acyclic.
9. Tree is a hierarchical model structure. 9. Graph is network model.
10. All trees are graphs. 10. But all graphs are not trees.
11. Based on different properties trees can be classified as Binary tree, Binary search tree, AVL trees, Heaps. 11. We differ the graphs like directed graphs and undirected graphs.
12. If tree have “n” vertices then it must have exactly “n-1” edges only. 12. In graphs number of edges doesn’t depend on the number of vertices.
13. Main use of trees is for sorting and traversing. 13. Main use of graphs is coloring and job scheduling.
14. Less in complexity compared to graphs. 14. High complexity than trees due to loops.

Example

Tree:

Tree Data Structure

Graph:

Graph Data Structure

Comment below if you have queries or found any information incorrect in above tutorial for difference between tree and graph data structure.

The post Difference between Tree and Graph Data Strucutre appeared first on The Crazy Programmer.



from The Crazy Programmer http://www.thecrazyprogrammer.com/2017/08/difference-between-tree-and-graph.html
Labels:

Comments

Post a Comment

Popular posts from this blog

Rail Fence Cipher Program in C and C++[Encryption & Decryption]

Here you will get rail fence cipher program in C and C++ for encryption and decryption. It is a kind of transposition cipher which is also known as zigzag cipher. Below is an example. Here Key = 3. For encryption we write the message diagonally in zigzag form in a matrix having total rows = key and total columns = message length. Then read the matrix row wise horizontally to get encrypted message. Rail Fence Cipher Program in C #include<stdio.h> #include<string.h> void encryptMsg(char msg[], int key){ int msgLen = strlen(msg), i, j, k = -1, row = 0, col = 0; char railMatrix[key][msgLen]; for(i = 0; i < key; ++i) for(j = 0; j < msgLen; ++j) railMatrix[i][j] = '\n'; for(i = 0; i < msgLen; ++i){ railMatrix[row][col++] = msg[i]; if(row == 0 || row == key-1) k= k * (-1); row = row + k; } printf("\nEncrypted Message: "); for(i = 0; i < key; ++i) f...
3 comments
Read more

Data Encryption Standard (DES) Algorithm

Data Encryption Standard is a symmetric-key algorithm for the encrypting the data. It comes under block cipher algorithm which follows Feistel structure. Here is the block diagram of Data Encryption Standard. Fig1: DES Algorithm Block Diagram [Image Source: Cryptography and Network Security Principles and Practices 4 th Ed by William Stallings] Explanation for above diagram: Each character of plain text converted into binary format. Every time we take 64 bits from that and give as input to DES algorithm, then it processed through 16 rounds and then converted to cipher text. Initial Permutation: 64 bit plain text goes under initial permutation and then given to round 1. Since initial permutation step receiving 64 bits, it contains an 1×64 matrix which contains numbers from 1 to 64 but in shuffled order. After that, we arrange our original 64 bit text in the order mentioned in that matrix. [You can see the matrix in below code] After initial permutation, 64 bit text passed throug...
Post a Comment
Read more

Experimental: Reducing the size of .NET Core applications with Mono's Linker

The .NET team has built a linker to reduce the size of .NET Core applications. It is built on top of the excellent and battle-tested mono linker . The Xamarin tools also use this linker so it makes sense to try it out and perhaps use it everywhere! "In trivial cases, the linker can reduce the size of applications by 50%. The size wins may be more favorable or more moderate for larger applications. The linker removes code in your application and dependent libraries that are not reached by any code paths. It is effectively an application-specific dead code analysis ." - Using the .NET IL Linker I recently updated a 15 year old .NET 1.1 application to cross-platform .NET Core 2.0 so I thought I'd try this experimental linker on it and see the results. The linker is a tool one can use to only ship the minimal possible IL code and metadata that a set of programs might require to run as opposed to the full libraries. It is used by the various Xamarin products to extract...
Post a Comment
Read more