Learning Algorithms: Graphs as Data Structures
We’ve made it from the beginnings of algorithms to our first bridge: graphs. If you’d like to read the first part of this series, check out my introduction to algorithms here. If you’d like to check out a good introductory book on Algorithms, Panos Louridas wrote a book called Algorithms, which is part of The MIT Press Essential Knowledge Series
A side note on this blog: covering graphs will be done in multiple parts to keep these articles bite-sized and manageable. This article will focus on introducing graphs as a data structure and highlight areas graphs are used today. In the next part of this series, we’ll aim towards the specifics of algorithms for graphs.
What is a graph?
It didn’t take much time in the programming world to realize there’s more to the term “graphs” than the bar graphs I was used to. But what else is a graph? I searched it on Google and the first result (from Wikipedia) was “an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within mathematics.” I hope this helps you in your journey with learning graphs. It did not help my journey.
P. Louridas did a much better job of explaining graphs: a structure composed of sets of vertices (nodes) and edges (links).
I’ll try to simplify this a bit more by clarifying some of the terminologies.
Vertices or Nodes
Nodes can be things like locations or items. When thinking about traveling, we can think of New York or Los Angeles (LA) as nodes. When thinking of programming we can think about the Document Object Model and the body of the document being a node (a child node of the document to be more specific). One last comparison: if you’ve ever done a connect the dots, nodes can be visualized as the dots.
Edges or Links
Links are the connections between the nodes. We’ll use our same examples as above. The flight from New York to LA that connects these two nodes would be a link. The connection which allows us to move from the document node to the body node (this action can be written in JavaScript as “document.body”) is a link. Lastly, the lines drawn to connect the dots would represent the links. A quick note to remember is that a link is represented by its starting node and ending node. In the example of flights from New York to LA, there is only ever one link but if there were multiple flights then each flight would be considered an “instance” of the particular link. While this can complicate things as you start being in the realm of multisets (a set is composed of two nodes and their link)and multigraphs let’s stay focused on learning basics right now and pretend there is only one flight between New York and LA.
Paths
Paths are another important piece of the graph structure. A path is a sequence of links connecting a sequence of nodes. Consider our trip from New York to LA. Let’s add a third node, say Chicago (because who doesn’t love getting to experience JFK, O-Hare, and LAX in one trip). Now, instead of flying direct from New York to LA, we’ll fly from New York to Chicago and then Chicago to LA. The sequence of these two flights and the cities they’re connecting (you can think of these as sets) would combine to make a path from the New York node to the LA node. A path that starts and ends in the same node is called a tour or circuit. This is easy enough to add to our example. We would simply add a flight path back to New York. Our tour with New York, Chicago, and LA as our three nodes could look something like this: starting in New York, flying from New York to Chicago, flying from Chicago to LA, and flying from LA to New York. We started in New York and ended in New York so our path is a tour.
Graphs and History
Thanks to a mathematician named Leonhard Euler, we have graph theory. Check out this video from Ted-Ed for an easy-to-follow origin story of graph theory.
Graph Theory Makes History
Now that we’ve gotten a chance to look at the basics of what makes up a graph. Let’s take a sneak peek at how graphs have been and are changing the world we all live in. Two big examples of graphs are social networks and the world wide web. Think about the basics of nodes and links and paths in relation to your group of friends and family. It’s a big example but when we think about it in terms of the people as nodes and the relationships as links, it allows us the chance to visualize a complex graph with something familiar. When we combine social networks and the world wide web, it’s not a far leap to social media networks. Now, the positive or negative influence of social media is outside the scope of this post but my hope is that you see how graphs and their associated algorithms have been able to create some of the most influential companies in all of history. Graph theory is powerful. Social media is not the only area where graph theory has been used. The last time you used maps on your phone or took a Lyft ride, you probably used an algorithm designed for graphs (likely rooted in Dijkstra’s Algorithm).
Hopefully, you’ll be able to walk away with a basic understanding of graphs after this post and be prepared for the next post in this series as we dive into the algorithms based on this field. If you’re looking for a deeper dive, there are graph theory courses as part of MIT’s OpenCourseWare (which offers free, online courses on a wide range of topics, computer science and beyond).
