Hello, internet. I am back after a short break wherein my mind was fully and thoroughly exhausted by the concepts of my Algorithms course. But, there is a light at the end of that tunnel and we’re on the downhill side of things.

So, with that in mind, I wanted to post a bit about this weeks material. If you’ve perused the site, you’ve seen that I have a rudimentary implementation of Breadth-first search in my portfolio. This weeks concepts kick that version of BFS up a notch by including a mechanism for tracking vertices we’ve already visited during the search where ‘White’ is undiscovered, ‘Grey’ is discovered and ‘Black’ is discovered with all neighbors explored as well as tracking the nodes depth. See the graphic below.

You’re probably thinking, “So what?” well I was too. But there are some pretty interesting things we can do with just this constant amount of additional space in each node. For starters, we can build a relationship tree, even on cyclical graphs. We can also compute distance from one node to another. And once we can compute distance, we can find shortest paths as well. All of which have applications to real life problems. Neat!