Adjacency Lists & Matrices

[00:00:00]
>> So how do we represent a graph? So I'm going to do A, B, C, D, all roads lead to D, or C, fantastic. This is beautiful. So there are different ways we can represent this graph. First way is an adjacency list. Now adjacency list is a giant list in which, say A maps to the first spot.

[00:00:26]
B maps to the second spot, C maps to the third spot, and D maps to the fourth spot. I'm going to put one more arrow, nope, that's fine, actually, this works out. No, I'm going to do this, I'm going to do one more right there, this is great.

[00:00:41]
This is great, all right, so that means A, we would represent this as A goes to D. And if we had a weight, say five, we could even put the weight in here five, right. A goes to D with a weight of five. A goes to C with a weight, it doesn't really matter if you don't have weights, you don't have to represent weights, but you get the idea.

[00:01:03]
A goes to D, A goes to C, you can represent them either way. You can kinda choose your own adventure here, B exact same thing. B goes to D, and it goes to C, and now I'm just doing weightless, I'm just doing a list in here. That's why it's called an adjacency list, it's a list of lists of adjacencies, what you're connected to.

[00:01:22]
But notice that when I do C, C only goes to D. We don't talk about going to A because this isn't directed graph, there is no connection back from C to A. So therefore, that's how we'd represent it, and D it's lonely, once you're at D, that's all there is, right.

[00:01:40]
No one going out of D, it's a roach motel as they call it and so there we go, that is an adjacency list. There's also an adjacency matrix it sounds fancy, it's really just a lot of numbers. All right, so I'd have A, B, C, D, A, B, C, D draw lines now, not very good box planning.

[00:02:07]
These boxes are way too big, so now all you do is look is A connected to A no. Is A connected to B, no, is A connected to C, yes, is A connected to D. In this situation I put a little fake weight just only on D and so typically an adjacency matrix.

[00:02:22]
If it's just a directed or undirected weightless graph you just put a one, there's a connection there. So, if you had weights you could put the weight inside the adjacency matrix. All right, is B connected to A, no, is B connected to itself, no. You can be connected to yourself like that's a real thing, that's thing that happens, people do that.

[00:02:40]
We're not gonna do that, but people do. All right, is B connected to C, absolutely, is B connected to D, absolutely, is C connected to A, no, no, no, yes, no, no, no, no. There you go, so you can see some obvious advantages and disadvantages here. If you had a lot of connections, an adjacency list kinda sucks because what happened if I wanted to find out is A connected to C?

[00:03:04]
I go to A, easy lookup, right to it. But I then have to go, hey, are you C, you're not C, hey, are you C, you are C, awesome. Let's go to this, and so that sucks, right, you don't wanna do that. And so if there's a lot of edges, something like an adjacency matrix makes way more sense.

[00:03:23]
Because it's easy access in, right here, yes, we are connected. And so, you kind of have to make the trade-off of how you wish to represent it. There's actually a third way, which is, I don't know why people would do it, but you'd actually do what is called an edge list.

[00:03:39]
We're not gonna do that, no, I've never seen it done. I don't know anyone that would do that. But you do something like A goes to D with the weight of five. A goes to C with a weight of one. I'm not sure why you would do that, but it does exist.

[00:03:52]
Okay, I've got to be somewhat complete here. All right, so there you go, that is like the basics of a graph. Is everybody feeling like they understand the basics of a graph? Yeah, feeling good? Okay, yeah, okay, sweet. Hey, pretty cool, all right.