Graph theory is a field of mathematics that studies a variety of graphs. But, instead of graphs being bar graphs or line graphs, we are referring to graphs that look like networks.
Looking at these networks, we can discover many different ways to model real-life scenarios and solve problems. For example, you could think about a map as being a network of cities, where you could try to figure out the shortest path between all the cities. Or, you could think about your social media and the network of who follows who, and in that network you could search to find a friend.
In this lesson, we will define graphs in the perspective of graph theory and introduce two types of searching algorithms. These search algorithms are particularly important for when you can’t see all of the information at once. For example, if you wanted to program a computer to go through the data points, or perhaps you’re clicking through people’s social media accounts in search of a person. The two algorithms we will discuss are quite effective and useful when you want to search a network.
A graph is a collection of vertices and edges that create a network, like above.
A vertex is a point on a graph. The plural of vertex
is vertices. Typically, vertices are represented on graphs using
circles. They sometimes also have labels, and we can use these labels to
write them. The vertices in the graph above are
An edge is a line that connects two vertices. The
endpoints of an edge are the vertices that it connects.
We can write an edge as the pair of its endpoints. The edges in the
graph above are
Two vertices,
When we have that a vertex is adjacent to
What are the vertices and edges in the graph below? What is the
neighbourhood of
The vertices in the graph are
Sometimes when we have a graph, we might want to search through it to see what vertices we can reach from a start point or to try to find a vertex.
In this lesson, we will go over two search algorithms called “Breadth-First Search" (BFS) and “Depth-First Search" (DFS). These are different but both use a similar concept of colouring vertices.
As said earlier, we can add labels to vertices. Unlike our examples,
they don’t always have to be letters, and vertices can have more than
one label. For our search algorithms, it’ll make it much easier if we
add a colour label to our vertices. In this case, we can pair the labels
for vertices, similar to how we pair endpoints to represent edges. For
example, if we wanted to colour vertex
When we do BFS, it’ll be important to understand what a queue is. For
our purposes, it’s best to describe that a queue
(pronounced like “cue") is like a line-up, where the people at the front
of the line get served first (like at a bank). We will use the letter
To help demonstrate this algorithm, we will do BFS on the example graph below. Note that if we are trying to find a vertex in particular, we can stop the search once we get to it. However, for the sake of showing how the algorithm goes through the whole graph, we will continue the search until we have throughly searched each vertex.
To start, we have that all of the vertices are coloured white. When a vertex is in the queue, it will be coloured grey to help us visualize where we’ve been. Lastly, when we are done with a vertex, we will colour it black. You can feel free to use your own colours for this when you do it!
To begin the search, we want to have a starting point. You may be
given a starting point or be able to choose it yourself. Let’s pick our
starting point to be
Whenever the queue is not empty, we should look the vertex at the front of the queue. In this looking stage, if we were searching for a vertex and the current vertex is the vertex we are looking for, we’d stop the algorithm. However, we are not searching for a vertex in this example, so we continue.
To continue, we remove our current vertex,
Now, since our queue isn’t empty, we take the first vertex, which is
The pattern continues while the queue is not empty. Next, we would
look at
Now, as you can see, there are no neighbours left that are coloured
white. Therefore, we are just going to start emptying the queue without
adding any more vertices. Whenever we look at a vertex, we remove it
from the queue and colour it black. Since the queue is currently
What is the queue for each of the five graphs above?
The queue for the first graph is
As you can see, drawing each graph takes up a lot of space!
Therefore, if we feel confident, we can simply list out the order that
we look at each vertex to show how we completed the steps too. For
example, for our BFS of the graph above, we looked at the vertices in
the following order:
Furthermore, as an example, if we were looking for vertex
Lastly, now that we’ve gone through the algorithm, we can see that it searches the closest points to the starting point as its first steps, going from side to side. In other words, we start by stretching the search area to be wide or side-to-side and close to the start point. This is why it’s named breadth-first search!
For the same graph as above, use BFS to do the following searches. Add neighbours to the queue in alphabetical order for both searches and list the order that you looked at the vertices.
Search for vertex
Search for vertex
The order that the vertices were looked at should be
The order that the vertices were looked at should be
When we do DFS, we search as far as we can, and then backtrack when we reach a dead-end.
We can use the same colour scheme as with BFS, except this time, we don’t have a queue and instead we will colour vertices grey when we’ve looked at them but are not done with them yet. White will still mean we haven’t interacted with that vertex yet and black will still mean we are completely done with that vertex.
We will use the same graph as with BFS to help show the differences between the two search methods. Note again that if we are trying to find a vertex in particular, we can stop the search once we get to it. However, for the sake of showing how the DFS algorithm goes through the whole graph, we will continue the search until we have throughly searched each vertex.
To begin the search, we want to have a starting point. You may be
given a starting point or be able to choose it yourself. Let’s pick our
starting point to be
In this looking stage, if we were searching for a vertex and the current vertex is the vertex we are looking for, we’d stop the algorithm. However, we are not searching for a vertex in this example, so we continue.
The next step in DFS is to look at a single neighbour of our current
vertex that’s coloured white. We can pick a neighbour in a variety of
ways, like alphabetically, from left-to-right on the graph, or from
right-to-left. Let’s choose neighbours alphabetically. So, the neighbour
we will look at next is
We again choose a neighbour of our current vertex that’s coloured
white. Since our current vertex is
Our current vertex is
A similar outcome occurs when we look at
Now, looking at
At this point, looking at
Looking at
Now, looking at
With
Similar to BFS, we needed to draw a lot of graphs to show our DFS
process. Instead, again similar to BFS, we can create a list of what
order we looked at each vertex to show our process. For our DFS of the
graph, we looked at the vertices in the following order:
Furthermore, as an example, if we were looking for vertex
Lastly, now that we’ve gone through the algorithm, we can see that it searches as far as possible away from the start point as its first steps. In other words, we start by stretching the search area to be longer and farther from the start point. This is why it’s named depth-first search!
For the same graph as above, use DFS to do the following searches. Choose neighbours in alphabetical order for both searches and list the order that you looked at the vertices.
Search for vertex
Search for vertex
How do the ordered lists using DFS in this exercise compare to the ordered lists using BFS in Exercise 3? Which search method is quicker for each search?
The order that the vertices were looked at should be
The order that the vertices were looked at should be
For search (a), BFS is faster. For search (b), DFS is faster. The answer for other comparisons may vary. A few things that could have been said are:
The BFS and DFS for the searches start with the same two letters
(
Vertex
Graph theory is a very cool field of mathematics and has many
different applications and problems to solve. In this lesson, we’ve
looked at a couple of search algorithms that can help us when we want to
search through a graph or network. Both BFS and DFS have pros and cons
and it might be better to use one or the other in different situations!
For example, in our example graph, we noticed that finding vertex
As an optional activity, try to think of other scenarios where BFS would be better, or alternatively where DFS would be better. An example where BFS would be better is if you’re looking at a map and trying to find a store that’s the closest to you. Each store could be a vertex and each edge could be a road! Clearly if you want a shorter distance, it’s better to look at all the vertices closer to the start point first, which is exactly what we do with BFS.