## 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.