Don’t Understand Graphs? Here’s Why You Should Study Graphs in Computer Science

Bennett Garner
Dec 15, 2018 · 5 min read

Graphs are everywhere, all around you! But chances are you don’t really understand them.

A directed, weighted, cyclic graph. A lot of jargon. Don’t worry, I’ll explain.

For many self-taught devs, graphs can be intimidating and difficult to learn.

For that matter, graphs can be baffling to experienced devs and computer science grads who haven’t worked with them for a while.

But graphs are cool and vital ways of representing information and relationships in the world around us. We can use graphs to do amazing stuff with computers, and graph algorithms offer a lot of tools to understand complex networks and relationships.

In this simple post, I’ll expose you to the basics of graphs. Nothing too fancy, complex, or mathematical here. Just the essentials. By the end, I hope you’ll see why they’re worth learning about and playing with.

A little motivation

Before we dive into the theory, I thought I’d provide some motivation for learning graphs in the first place. What are graphs and what can we do with them?

At its most basic, a graph is a group of dots connected by lines.

That’s the essential picture you need in your head. All the complicated notation you find in comp sci textbooks (e.g. G(V, E)) is simply a way to abstract the concept of dots connected by lines.

We use graphs to model relationships in the world. For example:

  • Google Maps uses a series of dots and lines to model the road network and give you directions to your final destination

We can model objects in physical space, relationships between people, and document structures all using graphs, simple dots and lines!

The upshot is once we have the relationships modeled, we can:

  • Find the shortest path between two points

Nodes/Vertices & Edges

When computer scientists talk about graphs, they don’t use the terms “dots” and “lines.”

Instead, each dot is called a node or a vertex (plural “vertices”).

Each line is called an edge or an arc.

By far, the most common combination of these terms is vertex and edge. When you see someone represent a graph with the notation G(V, E) it literally means “a graph with vertices and edges.”

Directed vs. Undirected

Directed vs undirected graphs

Google Maps wouldn’t be very useful if its instructions told you to turn the wrong way down a one way street, would it?

Sometimes edges of graphs need to point in a direction. When this is the case, we call it a directed graph. We use arrows when we draw a directed graph so everyone knows what we mean.

Twitter is a directed graph because relationships only go in one direction. You can have lots of followers without needing to follow all of them back.

In contrast, Facebook friends are an undirected graph. When you become friends with someone new, that relationship goes both ways and there’s no directionality to your relationship.

Some terminology to describe the way an edge is pointing:

  • The head of an edge is the vertex that the edge is pointing toward

Cyclic vs. Acyclic

If your undirected graph contains a loop where you can follow the edges and return to a point, then you have a cyclic graph.

If your directed graph has a loop where you can follow the edges in the correct direction and return to a point, then that graph is also cyclic.

An acyclic graph, on the other hand, has no loops.

For instance, this graph is acyclic because it has no loops. While the vertices are well-connected, they only go in one direction.

Directed acyclic graph

Weighted edges

If we want to make our calculations more interesting when finding the shortest path, for instance, we can add weight to the edges of our graph.

Weighted, undirected, cyclic graph (whew, mouthful of jargon)

Google uses weighting to take into account things like traffic when it gives you directions.

There are all kinds of applications of weights. They might represent strength, distance, difficulty, or desirability. It’s up to you!

Problems You Can Solve with Graphs

That about covers the basic concepts and jargon you’ll need to know to start learning more about these essential data types in computer science.

So what can you do with them?

There are well-established algorithms for many tasks:

  • Is there a path between two points?

These algorithms could help you do things like:

  • Build a Sudoku puzzle solver

Get your graph on!

Chances are if you build anything complex with computers, you’re going to use a graph, whether you know it or not. I hope this simple introduction gives you the basics you need.

This is by no means exhaustive, and PhDs have dedicated their entire lives to studying graphs. In many ways, the field of computer science is the study of graphs.

If you liked this article, it’d mean a lot if you’d give it a few 👏claps👏.

About Bennett

I’m a software developer in New York City. I do web stuff in Python and JavaScript.

Like what you’ve read here? I have an email list you can subscribe to. Infrequent emails, only valuable content, no time wasters. I’d love to have you there.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store