Well it’s been a week of doing this challenge! For today, I wanted to share a little reflection and keep my learning tidbit a bit shorter than I usually would. I think that writing down what I’ve been learning has really helped make the concepts clear in my mind. For day 1, I shared what I’d learned about applied probability. I didn’t realize how little I had understood until I had to put it down and kept referring back to the lecture notes and other online resources until I had it clear. I think what’s great to see too, is the variety. I’ve written about math, accessibility, algorithms, how to name things, testing and more. I’ve recently a course started on Ancient Greek heroes so once I really get into it, I hope to share what I learn from there too! I’m happy to have started this challenge and I hope I can keep it up for the next 3 weeks. It’s definitely been harder than I thought it would be to post daily, but I feel like it’s been worth it.
For today’s learning tidbit, I wanted to talk about “breadth-first search”. There are lots of different searching algorithms and I’ve never even considered it until I started my deep dive into algorithms. We deal with these underlying pieces of technology all the time without even realizing it, and it’s been great to gain an appreciation of it. As I try to wrap my head around all these different algorithms, one I thought particularly elegant was the one you use for “breadth-first” search. Now this isn’t the be all, end all for searching algorithms. It really depends on what your needs are, but it’s definitely interesting. BFS (breadth-first search) helps us look for a certain point in a graph. A graph is essentially a bunch of connected points, sometimes it’s a two way connection and sometimes it’s only one way. For example, let’s say we have points 1, 2 and 3. 1 is connected to 2 (and vice versa), and 2 is connected to 3. Our graph would then look like this:
Now that we have a grasp on graphs, we're ready to move onto the next step. Before we can understand BFS though, we need to have one more concept to understand: queues. It's not the waiting in line kind, although it is similar. A queue can do two things, it can get you the first element or add an element to the end. That’s it. To start things off, we pick a starting point and add it to our queue. Our algorithms kicks off by getting the first element of our queue, which is the starting point. We now add all the neighbours of that point to our queue. Now we get the first element of the queue and repeat the above steps again. And again. And again, until our queue is finally empty. At that point, we’ve either found the thing we’re looking for or it doesn’t exist. To make sure our queue ends and doesn’t add the same neighbours on and on forever, before we add a neighbour to the queue, we add it to a visited list. Then we check our visited list each time before we add a neighbour to a queue. That way we’re only looking at each point once. That's it! With that, you can implement BFS. Until next time!