Data structures are just ways we organize data.
The one I'm sure you're familiar with is the list or array, a linear ordered sequence of values. This is your shopping list, your to-do, your reading, whatever.
Lets explore the way more exciting realm of non-linear graphs!
But first, some basics:
A graph is comprised of objects connected by lines.
In JavaScript (and computer science at large), we refer to those objects and lines as vertices and edges.
The benefit of a graph structure is that not only can you represent nodes of data but also their relationship to each other through properties assigned to their edges.
Two common properties of edges are weights and direction.
If a graph has weights, it is considered weighted and if it has direction, it is considered directed. Direction can go one way or both ways.
Susan can have a crush on Sally, but that doesn't mean Sally has a crush on Susan.
Now, imagine yourself, just floating in space all by your lonesome. You have a lot of knowledge, and no one to share it with.
Another space traveler appears, "Hey friend! Lets keep in contact". You give them your number, and suddenly, you have meaning and cease to be a singular speck of dust in space. You have become a node and you have created a connecting edge.
But it costs you.
Each time you call your space friend, you're billed by your telephone company $12393900.00. This is the weight of your connecting edge.
Lets come back from space and look at IRL graph data structures
Classic example is Google Maps. Its just one big graph!
Streets intersecting are vertices, and the streets themselves are edges.
They are weighted by distance in length and time. The streets also have a directionality property...some streets only go one way.
Traversing a Graph refers to finding a path between two nodes, finding the shortest path from one node to another and finding the shortest path that visits all nodes [1].
On of many methods to traverse a graph is using Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, SPF algorithm). This is the one Google used (or a variant of) to implement their map application. This algorithm was originally conceived by Dijkstra in 1958 in 20 minutes at a cafe in Paris [2].
Here's what it looks like in Javascript:
A note on Tree Graphs...
That family tree you had to make in Kindergarten? Yup, a Tree Graph.
Here's the thing, Tree Graphs are a highly specialized form of a Graph, with a root node that all other nodes are decedents of.
Its important to make the distinction between a Tree Graph and a Graph, because they have some overlapping qualities like , but their rules on structuring data are completely different.
So in JavaScript, they are considered entirely different data structures.
For an in-depth and entertaining read on Trees, check out this article by fellow DEV community member Jill.
Graphs are a non-hierarchical structures of how data relates, connecting our entire world!
Title Image: Social Network Analysis Visualization [Grandjean, M. (2016)]
[1] https://www.jenniferbland.com/the-difference-between-a-tree-and-a-graph-data-structure/
[2]https://www.vice.com/en_us/article/4x3pp9/the-simple-elegant-algorithm-that-makes-google-maps-possible
Top comments (19)
This is one Subject that I'm always trying to understand and so far I'm not getting it. I read, watch, and try to practice graphs, but so far I don't think I'm doing much progress.
But the way you wrote, made it more clear to me. Thank you very much!
If you want to write more about it, I think it would be really great.
( If you want to write more, and have some free time to do it. No pressure )
Is there any material you could recommend to me? This is a concept/theory that I want to learn.
Thanks!
Thanks for commenting Fernando and I'm glad I could help provide some clarity on Graphs! There is definitely a lot more to say about this data structure and I'll let you know if I get around to writing more. One recommendation I have is the book "A Common-Sense Guide to Data Structures and Algorithms: Level Up Your Core Programming Skills by Jay Wengrow". I found it very easy to understand. :) Good luck!
This is a nice introduction, but I think it would be helpful if you could explain Dijkstra's algorithm a bit rather than here is what it looks like in JS.
Thanks
Hey Steve thanks for the feedback!
Thanks for the writeup, Amber! As someone a little familiar with Dijkstra's and very unfamiliar with Javascript it was a nice little exercise in learning some Javascript syntax.
Awesome! Thanks Ryan. :)
This is great! The space example puts it all together.
Thanks Guillermo!
Hey Amber, thanks for sharing!
Thank you so much for this article. Simple and easy understand !
Thanks !
Thanks Tuan!
Nice blog post, always looking forward to read posts like this :) I'd love to see the code of google shortest path, I am sure they added lot more logic about traffic, road works, etc...
Same! For sure!
This article is appreciated! Its given me a nice starting place and some "google-able" words to put to some thoughts to... thanks for writing!
Keep writing.
I Amber-y impressed the way you explain the graph. Very creative.