Graphs Overview

[00:00:00]
>> So we're now gonna come to graphs, graphs being usually the hardest, and largest part of all algorithms. Everything we've done up until this point is effectively a graph. I know, might be a hard pill to swallow. There's that meme, hard pill to swallow, everything's a graph. This is always the terminus of all these things cuz it's just, there's so much to graph problems, it's out of control.

[00:00:24]
I believe it was Euler, and I forget what city, I think it's in Germany, he was asked, hey, we have these seven bridges and we want someone to be able to walk over all the bridges once cuz we're giving some king a tour or whatever. And we wanna be able to uniquely walk over all bridges and see all parts of the city, but we can't figure it out.

[00:00:43]
We're gonna go hire a mathematician known as Euler, which most people don't realize that this is pronounced Euler, that's Euler. People call it Euler, it's Euler. He came and said, okay, I'm gonna figure this out. And he reduced that problem literally down to how we draw a graph problems to this day.

[00:01:02]
He realized that the bridges or connections, each land area's just a circle. So he's just like, here's the nodes, here's the connections, and came up with a principle effectively stating that, if there is an odd amount of connections into any one node you can't do this type of traversal.

[00:01:17]
And so he kind of proved that mathematically, sorry, your city is incapable of doing this. You're gonna have to do this differently. And so, it was actually pretty cool. It's a pretty cool thing, you can read about it, but I didn't. Out of the two algorithms book, there's a third one that I've read and that one told that story super neat, very fantastic.

[00:01:34]
I'm sure I butchered a little bit of it, but it's mostly correct, what I just said, mostly correct. All right, it's not as good as the Hamilton draw the equation of the quaternion while talking to your mother-in-law, that is the greatest story of them all. But that is almost an imaginary story.

[00:01:53]
That's a really good joke if you get it. It's a really good joke. Okay, anyways, so, what is a graph? A graph, as simple as it is put, is a series of nodes with some amount of connections, right? There's no rules. It's not like, you can only be top down.

[00:02:11]
It can only have a left or a right. It's just, there's a lot of connections, or some connections, or no connections. So, there we go. I just draw a graph, right? That is a graph. So there's a lot of terminology when it comes to a graph. And so let's kind of go through all the terminology, blah, blah, all trees are graphs.

[00:02:30]
So here's the terminology. This is not obviously exhaustive, but it should be enough for us to be able to kind of communicate about it for the rest of the day. So a cycle, a cycle is as simple as this, if I can start at A and visit at least, I believe a cycle requires three nodes for it to be a cycle.

[00:02:49]
Means that if I can visit a series of nodes and going back to myself, that should be considered a cycle. So A to D is not considered a cycle cuz it's only two nodes. So A, to B, to C, to D, to A, would be a cycle, right?

[00:03:06]
There we go. We now have a cycle all the way through. So that is a cycle, of course, and our acyclic graph is an acycle, a meaning not in this case. So there is no cycles in the graph. A connected graph means that every node can reach every other node.

[00:03:24]
So a good example of this is, if we had this, and let's just say we actually had a direction to this arrow, right? E, E can reach no other nodes, but every node can reach E. So, therefore, this is not a fully connected graph, there's actually kind of two sub parts to this graph, right?

[00:03:43]
We're not quite fully connected. We're not gonna go over strongly connected components, blah, blah, blah, blah, blah. But just something to know about. Directed, as I just showed right here is, oops, as I showed right here, is when you actually have directions on your arrows. Meaning that there are one-way connections, or the connections are asymmetric.

[00:04:02]
Let me give you an example. Let's say that we have A connected to B. First, I'll draw it like this. I'll do that, that, to that. It's kind of like an old college trick right here. And I can put a number up here and a number down here.

[00:04:16]
Meaning if you go from A to B, the weight's 20, or the cost of that connection is 20. If you go from B to A, the cost of that connection is only 10. And so you can have these weird asymmetric relationships in a graph, it happens. You could imagine traffic creates an asymmetric contention on a highway.

[00:04:35]
If you lived in the bay area, you would know that if you're coming from Netflix's office going north up the 880, it totally sucks at four o'clock. Cuz everybody arrives to work, of course, between the hours of eight to one, but everybody leaves work at four o'clock on the dot.

[00:04:50]
Bay Area, just the worst. So that always happens. So it creates this asymmetric relationship. So if you're going south, you can go 100 miles an hour. If you're going north, you can go five miles an hour, it's just the worst. So you get the idea, so obviously Google Maps has this.

[00:05:05]
They have these changing weights in which they know, hey, if you're going this direction, it's much slower than, say, the recommended speed, but if you're going this direction, people are going ten over. So we may route you a different way than you would expect. All right, undirected, of course, meaning that the links like these ones, they don't have any direction associated with them, you can go both ways.

[00:05:29]
Weighted, I just kind of went over that, weighted. They actually have some sort of value associated with that connection. In an undirected graph, a weight would be for both directions, it'd be a symmetric relationship. Whereas in a directed graph, it can be asymmetric. Oopsies, a dag is kind of like a pretty common phrase, it means a directed acyclic graph.

[00:05:50]
So a good example of a directed acyclic graph, we could just draw one really quickly. Remember, a cycle is when three nodes, you can go back and forth. So I could have something that looks like this. That's just fine. And then we can do something like this. There we go.

[00:06:09]
So there you go. That would be a directed acyclic graph, I believe. Let me just make sure, right? If you're at A, you can only go to D, you can't go here, yep. So there you go. You kind of have this whole thing where you can't quite make it to any other node, everything has a terminus.

[00:06:24]
So B would be the closest, which you could go all the way to here but you can't go any further. C, you can't even go anywhere, poor C, pour one out for C. Implementation terms, I will refer to a node usually as a vertex. I've seen them also referred to as a point, but that's pretty rare.

[00:06:42]
But mostly vertex is kind of like the Canonical term for a node in a graph. You can also use the term node, but that means when I'm doing Big O, I'm gonna be using probably V to describe the nodes. This is the vertex, this is the running time based on the vertex.

[00:06:59]
Second, an edge is the connection betwixt two nodes, you get the idea. So that means if we had a running time of O times V, that means for every vertex, we would visit every single edge in the graph. Does that make sense? Yeah, I think that makes sense.

[00:07:15]
So there we go.
>> Do the vertices have weights, too, or?
>> Vertices have values, right? I mean, usually weights are only associated with the traversal betwixt two nodes. But in this case, you can put whatever you want as the value, okay.