Implementing BFS on Adjacency Matrix

[00:00:00]
>> So let's go right here and let's set up our seen array equals a new array. And let's do a graph cuz remember, our length is a square cuz it's an adjacency matrix. So there's as many rows as there is columns. So long as I have that, we have everything filled with false, awesome.

[00:00:20]
So we haven't seen anything yet. Next, we do our previous array, which means we need to go in here and add in a -1. There we go. Nothing has any parents right now. Next, we are gonna see our first one, which of course, is gonna be our source, which now equals true.

[00:00:37]
We have seen our source because our q, Contains our source. There we go. That is the setup, just like the setup was right here, where are you? There we go, exact same setup right here. Our source has a -1, but it has a true for seen. So we don't really go visit it again.

[00:01:01]
That'd be kind of wasteful if we did it. I mean, you technically could, but it'd just be shoddy programming. No one wants to do that. Now, of course, the Lord's loop, a do while, while (q.length), right? We're gonna keep doing this while we have length. Again, we're gonna step through.

[00:01:16]
We need to grab our current item out of our q, const current = q.shift as number, right? Cuz shift, this is the type of thing, shift could be undefined cuz you can do that on an empty one, blah, blah, blah, blah, blah. There we go. So if it equals needle, then we can break, right?

[00:01:34]
We have found it, but we probably shouldn't break right away, right? We probably wanna first set up. Do we need to set up anything? No, we don't need to set up anything. Actually, what am I saying? There we go. So if we find our needle, we're done searching, we found it.

[00:01:49]
If we haven't found it, we need to do some bookkeeping, seen of our current is now true. Previous, oopsies, we don't need to do that. We have now seen current, correct? Awesome, we don't need to look for it again. We don't actually have to do this cuz we were doing it in our written one.

[00:02:07]
We were actually doing it, we're doing it right here. So you can kinda choose where you wanna do it. Let's just do it. Let's just do it in the for loop to kinda keep our written version equal to the other one. So there we go. So what are we using?

[00:02:20]
We're using a weighted adjacency matrix, awesome. So let i = 0, i has to be less than graph.length i++, right? So now we have our current one, which remember, anything we select, we grab out the row, right? So by grabbing out the row, that represents our connections to other nodes.

[00:02:41]
All right, so our adjacencies is gonna be graph, not graph[i], what am I saying? It's gonna be const adjacencies equals graph current, right? There we go. So then we can just do this one if you really wanted to. So there we go. So now we're gonna walk through and grab each one of these edges out.

[00:03:01]
Sorry, my bad on that one. So if there is no edge right here, we continue, right? There's just no edge at this point. Also, if we have seen i before, we continue. We don't need to do anything here, right? We've already seen it, let's move on. Else, that means we haven't seen it, so we need to push it into our q, mark it as seen, and add from whence it came, right?

[00:03:30]
Give it the old Elrond approach here. So seen[i] = true, oopsies, I added that one, prev, so this, who is my previous from i? Well, it's current, right? The thing we pop out of the q had this as a child. We're saying we've seen this, so that's its parent.

[00:03:51]
That's its parent in this breadth first search. Does that make sense? That's kinda like the hardest part about the whole breadth first search is really rederiving how to walk backwards through a breadth first search, but there we go. All right, so now that we've seen it, we've done all that, we can go q.push, of course, i.

[00:04:10]
Most excellent, and might I add, it is just really easy using an adjacency matrix. When you see us using an adjacency list, you'll see that having these little items on the list does make it a bit harder. So there we go. We now have it. We have our seen, this.

[00:04:28]
We'd go like that. We'll eventually run out of items to look through. Now we just have to build it backwards, right? So we now have to walk our previouses until we get to a -1. Does that make sense? So we'll go like this. Let's go let current equals needle, all right?

[00:04:48]
We're gonna start at the point we need to search from or where we were hoping to find. We're gonna start there. And then we also want a out array. Our out array is gonna represent our path through the graph, starting at the needle back to the source. So we'll go like this, while, what's it called, previous current does not equal -1, meaning, keep on doing this until we found a point that has no more parent.

[00:05:18]
So if we never found needle, it will be -1 to begin with, we'll immediately stop and we'll return out an empty array, meaning, we didn't find a path. There's no path from source to sink. Do I call it, okay, I do call it needle, just wanna make sure.

[00:05:33]
I mean, I should have saw that there's no length right here, but blah, blah, blah, blah, blah. All right, so now that we have that, we now just build it backwards. We go out.push current, right? So we can just push in current every single time we see this, and then go current equals previous current.

[00:05:49]
So set it to my parent or who added me to this search really is what that says. Whoever added me to the search, set it to that. Cuz there's not really such thing as a parent-child relationship in a graph, but in a search path, there kind of is.

[00:06:04]
So at that point, all we have to do is if (out.length), meaning that we did have a path from beginning to end, we can simply return our out and we can reverse it, right? We reverse it, but there is one more thing. If we reverse it, did we add our source?

[00:06:25]
No, cuz our source has a parent of -1. And when we get to the point of actually being at our source, we say, hey, does this have a parent? No, it doesn't. So little fun fact, you gotta do something that probably looks more like this, [source].concat, right? I'm sure there's a better way to do this, but there you go, we now have added everything together, or we can just simply return nothing.

[00:06:50]
We could have done this check up here with, say, our needle having a parent of -1. That would have also done the exact same thing. Meaning that if we would have one like this, if previous needle equals -1, return that, right? There is no path there. And then we don't have to do this check.

[00:07:12]
There we go, right? You can kind of choose your adventure of how you want to implement these things. I don't really have a preference. It's all the same thing to me, right? It's all the same set of logic. So there we go, we've done it, we've officially made it.

[00:07:22]
If I am the most bestest, then this should work. All right, so npx jest BFS. Every time I see BFS, I almost think best friends forever. All right, hold on, we have a couple items in there. All right, do we actually get that? Yep, this one doesn't exist.

[00:07:41]
Dang it, I didn't look at my interface. It's returned null if there's no path. I was such a dummy. There we go, it wanted us to return null. Who wrote that interface to begin with? All right, there we go, awesome. We passed the thing we wanted to build.

[00:08:00]
I technically have two, I have two functions in here. There's also BFS on a graph list, which we just didn't do. So we did it on a matrix, awesome. We've built the path through the matrix and found the reverse path, did all the swapping, and the source. Do all the magic, keeping how we got here from whence we came has been calculated.

[00:08:18]
This effectively is an identical algorithm to what I had to do with Falkor, which I showed you yesterday, where I actually had to be able to remap backwards through a graph how I got there.