Searching an Adjacency Matrix

[00:00:00]
>> So how are graphs represented? Usually, there's two ways you represent a graph. There are third ways, you could actually build a full graph node structure in which has references to other graph nodes. And it'd be some sort of tuple of say, weight and other node, right? You could have a list of children in this kind of sense.

[00:00:21]
But often, it's not made that way. Often, graphs look a little bit different. So the two major ways in which I've seen graphs be implemented, which was true when I went to college, not all these things that are true when I went to college, things have changed since I went to college, especially when it comes to maps.

[00:00:37]
But when it comes to graphs, there's usually two ways. So there is the adjacency list and then there's the adjacency matrix. And they both kind of have their uses, but in general, what you're going to see is predominantly this. You will rarely see this, and the reason why is that it takes a lot of memory and setup to be able to do.

[00:00:58]
If you were to set it up, it takes OV squared. In other words, running time of OV, yeah, vertex squared. So let's first do an adjacency list. So often, when you're representing a graph here, I'm gonna draw this out, let's just draw one out. We'll go like this.

[00:01:13]
I'll just call this one 0, 1, 2, 3. So let's draw this as I directed to. So 0 is gonna point to 3 and 1, 3 will point to 1, and 3 will point to 2, 2 will point to 0. There we go, we kinda have this little graph going on here.

[00:01:32]
So an adjacency list will be a list in which the indice maps to this. So 0 represents node zero. So node zero will have a list of edges. So you could imagine something that looks a little something like this, to: 1, and then we could put a weight that's associated with it.

[00:01:53]
So if this thing was 10, we could put 10. There we go, there would actually be another one, obviously, right? We'd also have to specify three, right? So we could have 3 and then some sort of value. You see what we're doing there. You can do a tuple.

[00:02:05]
It doesn't have to be an object here, but you need some way to describe where it's going plus the weight that is associated with that connection. So it's a list of edges in this, in other words, an adjacency list. What am I adjacent to? Adjacency meaning you have a connection to.

[00:02:20]
And so then position one would have the same thing. It would also have a list in which is an empty list. I didn't even realize it, 1 is a terminal right there. And then 2 would have a single item pointing to 0. So 2 would be 0 with a weight of something.

[00:02:36]
And then 3 would have its own, which would actually have two items in there, right? Does that make sense? Yeah, I think that that's usually a pretty good way to kinda look at it. This seems to be a pretty popular way to represent it. The other way is an adjacency matrix.

[00:02:52]
In other words, what we're going to have is we're gonna have rows, each representing a node. So this is node 0, 1, 2, 3. And this, of course, is 0, 1, 2, 3. So that means, does 0 have a connection to 0? No. Does 0 have a connection to 1?

[00:03:10]
Yes, and its weight is 10. Does 0 have a connection to 2? No. Does 0 have a connection to 3? Yes, it's weight is 5. There we go. So, we write it out that way, which means we can also have asymmetric relationships. Let's look at one, because 0 has a connection to 1, but 1 does not have a connection to 1 or any other node.

[00:03:30]
So you can kind of see how this is working. We're saying how the connections are made. And so there you go. This is usually a way that I've seen these things done, and the problem, of course, again, is memory and how you have to represent it. If you had 100 nodes, you'd have to create 100 by 100 matrix to be able to represent it all.

[00:03:47]
If you had 1000 nodes, it grows. If it's sparsely connected you're gonna use a ton of memory to represent a few points of connection. And as you can imagine, you could just never use one of these for say maps. You'd only just have just a little bit of a city in there, and you'd have so many connections that this thing would immediately explode.

[00:04:06]
So it's unlikely that this is used in maps. And unless of Google has done something very magical that we do not know about. Do we have any questions on the representation of a graph? All right, cool. All right, so basic searches are still available, correct? Well, they should be, right?

[00:04:30]
Because if all trees are graphs, and we can breadth first search a tree, why can't we do with a graph? Of course, we can, right? Of course, we can. So we do the exact same thing. Let's say we start at 0, and let's do a depth first search.

[00:04:44]
We are going to push in 1. So right now, we have 0 on the stack, and we're gonna push in 1 on the stack. 1 is gonna have no connection. So we'll pop 1 off the stack. We're gonna push in 3 on the stack, 3 has two connections.

[00:04:58]
One we've already seen, so we're not gonna go to that one. And 2, 2 has one connection, which is 0, which we've already seen. We'll pop that one off the stack three has no more children, we'll pop that one off the stack zero has no more children, we'll pop that one off the stack.

[00:05:12]
There we go. Exact same thing, except we don't pop and push on a stack. We call a function we use recursion, right? Absolutely, all right, same thing with breadth first search, we just simply have a queue, right? So we start off with 0 in the queue, and then from 0, we need to push on some items.

[00:05:30]
We're gonna push on 1, and we're gonna push on 3. From 1, so 0 gets popped off, then 1 gets popped off, and what we have left is 3, because 1 has no connections. We then pop off 3, 3 pushes on 2 because we've already seen 1. So therefore, we now do that, we push off 2, 2 tries to look at 0, 0 has already been seen.

[00:05:48]
We do not need to put it on there, therefore, we're done. So breadth first search, depth first search work identical as they do with graphs, because again, trees are graphs, makes it pretty simple. If you know how to do one, you can really do the other. And just for fun, let's do one.

[00:06:05]
We'll do a breadth first search on an adjacency matrix, and we'll do a depth search on an adjacency list. You guys excited? Awesome, let's leave this thing. And let's go into here and let's do a, look at that, a BFS on a weighted adjacency matrix. Of course, I created this type just so I don't have to type it out.

[00:06:29]
It's just a 2D number grid, right? Pretty easy, I think we could have seen that one coming. Just to make this a little bit easier, if we're gonna do a breadth first search, what do we need to do? Well, we need a source. We need to know where we're starting from.

[00:06:43]
We need to know what we're looking for. And we want to be able to return the path that we took. Now, this is kind of interesting, all right? So if we were to do this, we're gonna really apply this whole breadth first search thing to graph. We're gonna need to come up with a path.

[00:06:59]
Now, this is kind a tricky problem, cuz it's like, okay, how do we do this? Well, let's go back to this thing for a quick second. So it doesn't really matter how we represent our graph, whether it's an adjacency list or a matrix. Breadth first search still involves a queue.

[00:07:13]
But it needs to involve one other thing to be able to understand a path. Normally in a tree operation, we don't consider path. It's usually irrelevant cuz we're just going down until we find the value. But in a graph, when we're doing a search, we often want the path or something associated with it, right?

[00:07:29]
Yeah, that's right. Okay, cool. Thank you, everybody in the audience. So, how are we gonna represent that? Well, depth first search is obviously much easier. Again, we have a pre-condition, we have a post-condition, which means we can push and it means we can pop, right? So we can just build our path as we recuse, which makes it super simple.

[00:07:54]
But a breadth first search, we don't have recursion, we don't have something that maintains the shape or the structure of our search. Therefore, we need to maintain it ourselves. And so the best way I've seen this done is you create something called a previous array, which is usually filled with something like negative ones.

[00:08:09]
Since no node has a -1, we don't have to worry about that. And so then what we have here is the previous array is with whom I came from, right? And so we also mean we need this couplet with like a scene array, something in which or a visited array, which means I've already visited this node.

[00:08:28]
So this would be a series of falses to begin with. Does that make sense? That means, let's say we visit node zero. All right, we visit node zero, it doesn't have any parents. This is where we started. So we don't have to worry about putting a parent or anything in there, right?

[00:08:47]
That makes sense. It just starts off with a -1. There is no parents. That's where we started. But we can set seen the truth. So let's actually work this thing out. I'm gonna create a new graph or a new window right here, and let's redraw something very, very similar to what we just had.

[00:09:04]
And for fun, I'm gonna add in a fifth item right over here just to make this little bit better. So like this 0, 1, 2, 3, 4, 0 can go to 2 with a weight of 4. It can go to 3 with a weight of 2. We can go here with a weight of 5.

[00:09:23]
And of course, we can go here with 1,1, and then we can go here. Let's not do that one cuz I don't wanna ruin the searching. I'll just be so quick if I do it that way. And a weight of 5, right? There we go. This looks great.

[00:09:40]
So we can actually make it through this. So of course, we start off with our seen array as a bunch of falses. And we see our previous array as a bunch of negative ones. No one has a parent yet, they haven't been visited yet. And of course, we start off with our queue, which has our source node in, I'll use 0 as my source node.

[00:10:01]
We're all good? Awesome. All right, so let's try to do this, we're gonna do a breadth first search. So breadth first search, of course, we pop off the current node, and we'll also set the first one to true. I just realized we should probably set that one to true, and the rest will be falses cuz we do put it into our array before we start our cursing.

[00:10:20]
So we kinda need to say hey the source one, that one's true. We've already seen that one, and it has no parent. So we're gonna do the lord's loop again, a nice do while. And we'll keep doing that until our queue is empty. So I'm just gonna go way down here to where I can't screw this up.

[00:10:35]
I say I can't screw it up but there's always a chance, queued up. While we have length inside of our queue. We're gonna assume the JavaScript array behaves like a queue. We're not going to just consider its n like properties for shifting off. All right, awesome. So the first thing we're gonna do is we're gonna go like this, current equals Q.deque, grab the first thing out of our queue.

[00:11:01]
All right, from here, we need to get all of its children and add them all to our Q, correct? Well, technically we're searching for something. So we're definitely going to want to do our effectively our break case, which is going to be, if current value or if current equals what we're searching for, say our needle, then we're gonna want to break.

[00:11:25]
If not, we need to do something? So, for each child in our current, right? So pretending either this is adjacency array or an adjacency matrix. So in a matrix, you'd have to go through, and every time you hit a zero, you'd continue, every time you hit a non-zero, you'd say, hey, this is a connection.

[00:11:41]
Let's look at it. If we've seen this, if seen, we continue. If we're not seen, we had to do a couple things. We're gonna go seen[C] = true. Then we also need to say previous, c was added by current. Do you see how that works? So now we know who brought us into this search.

[00:12:10]
By doing that, that will give us our path backwards through our search. All right, at this point, we now push into our Q, right? Q push, it's not push, it should be in Q but that's such a long word, it has so many use and ease in it I don't know how to spell that word.

[00:12:29]
We're gonna push in C. There we go, that's pretty much it, that's how we're gonna do it at the very, very end. Of course, we're gonna have to walk backwards in our previous array, right? We'll have our previous, if we start from our needle, if we never got to our needle, it should equal -1.

[00:12:48]
If we did get to our needle, we would know who added it, then we could go to our previous array for who added it, and we'd know who add that. We went to a previous array for that, we know who add buzz, and who had buzz would be buzz and who had a buzz would be foo, right?

[00:13:01]
We'd be able to walk through all the arrays until we got back. So let's see this in more practical terms.