Two important Graph Algorithms - BFS and DFS

Today we are going to see two very well known graph algorithms.

Modeling the world with graphs helps us solve a lot of problems. Computer network problems, data structures, pathing and maps, molecules and other kinds of problems.

The path problems are really common. Let's say you have a set of cities in a region (map), and you would like to know the shortest path between cities A and B. This is a problem well-suited to a graph-based solution.

Now let's say you have an array containing -1, 6, 3, 2, and you would like to find the longest sum. We can model it as a Directed Acyclic Graph (DAG), add a source and destination and we can connect the points with edges whose weights correspond to each number we have in our array.

Depth First Search

In the Greek Mythology, the Minotaur is a mythical creature. He dwelt at the center of the Labyrinth, which was an elaborate maze-like construction.

How can we find a solution for the Labyrinth? We use a Depth First Search to solve problems like that.

Before showing the algorithm, let's imagine how a potential solution for this would be. As we don't know the solution we could mark all the paths we've visited, and then once we have no more solutions in front of us, we go back and we search another path. In short, we walk walk and walk and then when we cannot walk anymore, we go back, and we try another path.

This idea we had is similar to a stack, and this is the best data structure we could use for this problem.

Here is the algorithm.

Breadth First Search

Now imagine we want to find the shortest path between two cities. This algorithm is used as a building block for other algorithms.

The Breadth first search starts by searching a start node, it explores the neighbour nodes first before going to the next level. In general, the algorithm executes everything in layers. It visits first all the neighbours and then the neighbours of these neighbours and so on, in layers.

Why should you care? These two algorithms are fundamental building blocks for other algorithms. All Computer Science students know them or at least have studied them at one time. Studying these topics might help us indirectly in our daily jobs, and it always opens our mind to abstractions.

Well-rounded individual, crafter of softwares.