What is a Graph?

In this video we cover all of the basics about graphs. We start be defining the different parts of a graph, and then jump into a real world example where we translate a map with cities and highways into a graph. Finally, we discuss some of the common attributes you might find on a graph, such as cost, capacity, directional edges, and even cycles, and relate these all to our graph derived from a map of cities and highways.

This post is part of the Let's Learn Algorithms series where we learn how algorithms work, see how to implement them, and then spend some time working on practice problems to reinforce how the implementation details work, as well as to help you learn to recognize problems that could be solved using any particular algorithm.

This particular tutorial is part of the section on Graph Theory where we discuss all of the basics about a graph and slowly build our way up to more advanced graph algorithms. This is the first video in the series, so if you are new just sit back and enjoy!

Ready to watch the next video in the series? Trees are also Graphs

You can view all of the videos in the Let's Learn Algorithms Graph Theory subsection to see if there is one covering a particular topic you are interested in. You can also check out the transcripts for the video below.

• 0:00 - welcome to let's learn algorithms in
• 0:02 - this series we've been covering
• 0:04 - different types of algorithms and data
• 0:06 - structures and not only how how they
• 0:09 - work and how you might go about
• 0:10 - visualizing them but we're also trying
• 0:12 - to cover how you would implement them in
• 0:14 - your code and working through real-world
• 0:16 - problems that you show this in action so
• 0:19 - in this series of videos we're going to
• 0:22 - talk about graph theory which is
• 0:23 - essentially the study of graphs so that
• 0:26 - leads us pretty much straight into the
• 0:28 - question of what is a graph so to answer
• 0:31 - that I'm going to first just show you a
• 0:33 - graph and I'm going to sort of talk
• 0:35 - about the components of a graph so that
• 0:37 - you can understand what I'm talking
• 0:38 - about as we proceed through these videos
• 0:40 - and you really understand near the
• 0:42 - pieces of it and then after I show you
• 0:44 - the names of these different pieces and
• 0:46 - sort of talk about them i'm going to
• 0:47 - show you an actual real world example of
• 0:49 - how you might map data to a graph so in
• 0:52 - this case we've got a graph with random
• 0:54 - numbers and we're going to start with
• 0:56 - the blue part which is called a vertex a
• 0:59 - vertex is sometimes called a node or a
• 1:01 - point or a data point it's essentially
• 1:04 - just something that represents a you
• 1:07 - know a stage a process a piece of data
• 1:09 - something like that in your graph so
• 1:12 - you'll see this one we've got the one
• 1:14 - colored in blue but all of these circles
• 1:15 - are vertexes and they represent
• 1:18 - different data points in this case
• 1:20 - they're just numbers the next thing that
• 1:22 - you want to look at is the red line
• 1:24 - which is an edge so you'll also hear
• 1:27 - these called an arc or a line and edges
• 1:29 - are going to represent relationships
• 1:32 - between different pieces of data or
• 1:33 - different stages and basically they're
• 1:35 - representing relationships between
• 1:37 - vertices so an edge is any of these
• 1:40 - black lines you're seeing including the
• 1:42 - red one they represent some sort of
• 1:44 - relationship between these two items and
• 1:46 - oftentimes what they'll mean is that you
• 1:49 - can maybe transition from one new data
• 1:51 - point to another or maybe you can use
• 1:53 - this to to generate a four then you can
• 1:56 - use the four to generate an eight so
• 1:58 - this graph isn't really clear what the
• 1:59 - lines mean but the the edges are new
• 2:02 - there they're going to mean that there's
• 2:03 - some relationship between them that it
• 2:04 - means it's something you know something
• 2:06 - important is there
• 2:09 - so this will all make a lot more sense
• 2:12 - if we look at a real world example so
• 2:14 - I'm going to pull up this map from
• 2:16 - google maps and I've intentionally
• 2:18 - zoomed in and gotten rid of you there's
• 2:21 - not many roads here we've just got a
• 2:22 - couple roads in a couple cities but
• 2:24 - we're going to show you how you might
• 2:26 - turn a map of cities and roads into a
• 2:28 - graph
• 2:30 - the first thing that you'd want to do is
• 2:33 - to decide what your vertices are so in
• 2:36 - this case our vertices are going to be
• 2:38 - the cities so each city is a you know a
• 2:41 - point on our map that we might want to
• 2:43 - travel to and we might want to calculate
• 2:45 - things like the minimum distance between
• 2:48 - two different cities or the minimum
• 2:49 - distance you need to travel or you might
• 2:51 - want to calculate you know the cost to
• 2:54 - travel from one city to another both in
• 2:56 - terms of maybe tolls or you might want
• 2:58 - to calculate it in terms of you know
• 2:59 - time taken to travel so every city
• 3:03 - becomes a vertex and then after you've
• 3:05 - created all the vertex or vertices you
• 3:07 - would put the highways as edges between
• 3:10 - the two cities so what these highways
• 3:12 - represent is a connection where you can
• 3:15 - drive from one city to another so the
• 3:17 - relationship represented by these edges
• 3:19 - is ok you can drive from dickinson to
• 3:21 - Bismarck and that's why we have an edge
• 3:23 - there so you'll notice that even though
• 3:26 - you can go a long way from dickinson all
• 3:28 - the way to Rapid City we don't actually
• 3:30 - make a connection between Dickinson
• 3:31 - Rapid City right now right now we're
• 3:33 - just doing the the most basic
• 3:34 - connections possible so we do Dickinson
• 3:36 - to Bismarck that's one direct connection
• 3:38 - we go dictor Bismarck to Fargo you know
• 3:41 - and that's one you know one piece of
• 3:43 - this relationship so we aren't doing any
• 3:45 - other connections just yet you could and
• 3:48 - it wouldn't necessarily break your graph
• 3:49 - or anything like that but for now I find
• 3:51 - this to be the easiest ways to sort of
• 3:53 - you know break it up as Bismarck as an
• 3:55 - actual newest and you don't have to stop
• 3:57 - there but it is like a spot that you
• 3:59 - could go through to get to Fargo now
• 4:01 - before we can sort of jump into your the
• 4:04 - rest of these videos and talk about
• 4:06 - algorithms and stuff like that it is
• 4:08 - important to look at the different
• 4:09 - pieces of data that might be associated
• 4:10 - with your edges your vertices in your
• 4:13 - graph now the first part isn't
• 4:15 - necessarily something that is specific
• 4:18 - to an edge or vertex but it's just sort
• 4:20 - of an attribute of a graph in general
• 4:22 - and that's whether or not the graph is
• 4:24 - cyclical or a cyclical now this doesn't
• 4:27 - always matter for what you're doing but
• 4:28 - I think it's worth mentioning because a
• 4:30 - lot of these algorithms will be working
• 4:31 - with the way you implement them in the
• 4:34 - way you sort of you actually use them
• 4:36 - will vary slightly depending on whether
• 4:38 - an autograph is cyclical or not so a
• 4:40 - cyclical graph means that you can leave
• 4:42 - one spot and
• 4:44 - getting back to that same vertex you
• 4:46 - know through a series of edges now in
• 4:49 - this case there's not really a good
• 4:51 - example of it so let's imagine that this
• 4:53 - this road from Fargo to Sioux Falls you
• 4:55 - could drive from Fargo to Sioux Falls
• 4:57 - and then you could get in your car turn
• 4:58 - around and drive back to fargo so that
• 5:01 - comes from the fact that this edge here
• 5:03 - doesn't have a direction it says you can
• 5:05 - go either direction you can go your
• 5:06 - north or south on it so technically this
• 5:09 - graph is cyclical it is possible to go
• 5:11 - one way or the other so whenever you're
• 5:13 - bringing your writing your algorithms
• 5:15 - you might want to sort of take that into
• 5:16 - consideration is how does that affect
• 5:18 - what I can and can't do or do I need to
• 5:20 - change my code to sort of prevent those
• 5:22 - cycles from happening the next thing
• 5:24 - that I want to talk about is that edges
• 5:26 - can be directed and I sort of alluded to
• 5:28 - this in the you know in the last example
• 5:29 - where I talked about Fargo and Sioux
• 5:31 - Falls that is a bi-directional edge
• 5:33 - where you can go either direction but
• 5:35 - sometimes you'll have hedges where you
• 5:36 - can only go one direction so from Sioux
• 5:38 - Falls to Sioux City I'm going to pretend
• 5:41 - like this is a one-way road and you can
• 5:42 - only drive south there's no way to drive
• 5:45 - back north on that road so when you have
• 5:48 - directed edges it's generally a way of
• 5:51 - you know you're saying that there's only
• 5:53 - data or new cars or whatever can only go
• 5:55 - one direction another thing to keep in
• 5:58 - mind is that edges can sometimes have
• 6:00 - costs associated to them so in this case
• 6:03 - we've got a five dollar toll going from
• 6:05 - Bismarck to Fargo now the toll or the
• 6:09 - cost can be different depending on you
• 6:11 - know what what situation you're in
• 6:13 - sometimes the cost will be time
• 6:14 - sometimes they'll be money and they
• 6:16 - might be something else entirely but
• 6:18 - costs are just something that say that
• 6:20 - every time you send one unit of
• 6:22 - something so in this case one car across
• 6:24 - that road it's going to cost you this
• 6:26 - much the last thing that we're going to
• 6:29 - look at our capacities and I have this
• 6:31 - from Rapid City to Sioux Falls and a
• 6:34 - capacity is it's going to seem similar
• 6:36 - to a cost but they're different in the
• 6:38 - sense that a cost is basically something
• 6:42 - it says you can send as much as you want
• 6:44 - to cross this edge but there's a cost
• 6:45 - associated for every single unit a
• 6:47 - capacity says you can only send this
• 6:50 - many things across this edge so in this
• 6:53 - case it might say you can only do 20
• 6:55 - cars per minute but it could also just
• 6:56 - be a constant number
• 6:57 - of this road only handles 20 cars and
• 7:00 - then it crumbles apart and breaks and
• 7:01 - that road is no longer a valid road so
• 7:04 - you the capacity is going to be
• 7:06 - something that limits the number of
• 7:08 - things you can send across an edge and
• 7:10 - where those sort of come into play in
• 7:13 - the real world is well in this example
• 7:16 - it's not entirely realistic but there is
• 7:19 - going to be some maximum number of lanes
• 7:21 - in a road there's going to be some
• 7:22 - maximum speed limit and you know you
• 7:24 - will have some maximum capacity of cars
• 7:26 - you can send through a road if you've
• 7:28 - ever gone to LA during traffic hour
• 7:29 - you've probably seen that there's
• 7:31 - definitely some maximum capacity of cars
• 7:32 - that can be sent down highway