Graphs vs. Trees: The Short Story
Graphs and trees are two very important data structures in the computer science world that at first glance, might sound quite similar. You may have heard that graphs are just unordered trees, but do you understand why? Let’s take a quick look at both graphs and trees to see how they differ, hopefully allowing you to better distinguish the two data structures (and their respective uses) in your head.
Trees
Take a look at the illustration of a tree to the left. Notice the hierarchical pattern of the nodes. In other words, with a tree, there is always a root node, and everything else is branched off from there. Never at any point will there be any loops of any sort, ensuring the valid structure of the tree.
Below is what a tree node would look like in Python.
Uses
Because of the structured nature of trees, it lends itself quite useful to many scenarios. Take your computer, for example. Your computer’s filesystem is structured exactly that of a tree. Think about it: every computer has a “root” folder of some sort, and from there, every single file stored on that machine lies in that root folder, likely within multiple subfolders.
Graphs
Shifting focus over to graphs, again, referring to the illustration to the left. One thing you may notice right away is the lack of structure. If the vertices were not alphabetical, and people were asked where the graph starts, there would probably be varying answers. In addition to the starting point, there seems to be no obvious path for traversal. What way are you supposed to go when vertices are looping into each other? Things change a bit when edges are weighted and/or directed, but that serves little importance of explaining in this case, where we are just trying look at the bigger picture of these data structures.
Also, do note that in contrast to trees, the drawn out appearance of graphs can vary greatly thanks to their unstructured nature. Take a look at the two images below to see some examples of other ways they could look.
Uses
Graphs, just like trees, have tons of uses in the real world. Think of many popular social networking platforms; keeping track of each user, who they are friends with, what posts they like, and so on. It can get messy really quick, but deep down, it’s all one big graph.
The Difference
So, where does all of this information lead us? Put simply, trees are derived from graphs and graphs are just trees without certain rules. Despite sounding similar at first, graphs and trees have distinctly different uses. If you are still struggling with this concept, try and think of graphs as a giant ball of clay. No matter how you bend, manipulate, or shape that clay, it is always going to be a graph. If you want to create a tree, however, that clay has to conform to a certain shape, no exceptions. Every tree is a graph, but not every graph is a tree.
I would like to end this off by clarifying that this is by no means meant to be an in-depth look into trees or graphs. Rather, the purpose of this article is purely to help people new to these data structures see the main differences and recognize them as two distinct entities.
Resources
As graphs and trees are a widely covered CS topic, there are plenty of resources out there to expand your knowledge. If you are looking for a good starting point, I recommend Tutorials Point as they have great coverage of both topics.
Trees, tutorialspoint
Graphs, tutorialspoint