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.
const DepthFirstSearch = (node) => { // Create a Stack and add our initial node in it
const s = new Stack(this.nodes.length);
const evaluated = new Set();
s.push(node);
// Mark the first node as evaluated
evaluated.add(node);
// Continue until stack it's empty
while (!s.isEmpty()) {
const t = s.pop();
// 1. we search for nodes connected to the node we're checking.
// 2. We filter out the nodes that have already been evaluated.
// 3. Then we mark each unevaluated node as evaluated and push it to the Stack.
this.edges[t]
.filter(n => !evaluated.has(n))
.forEach(n => {
evaluated.add(n);
s.push(n);
});
}
}
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.
Here’s the algorithm
const BreadthFirstSearch = (tree, rootNode, searchValue) => { // make a queue array and populate it with the root node
const queue = [rootNode];
// search the queue until it is empty
while (queue.length > 0) {
// assign the top of the queue to variable Node
const Node = queue[0];
// Break if we find the node
if (Node.value === searchValue) return;
// Add right left of current node to the queue if exist
if (Node.left !== null) queue.push(tree[Node.left]);
// Add right child of current node to the queue if exist
if (Node.right !== null) queue.push(tree[Node.right]);
// remove the Node from the queue.
queue.shift();
}
}
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.
