Graphs Overview

[00:00:00]
>> We just got done doing trees. Now, we're gonna do graphs, but what we're gonna be doing with the graph is making trees out of them. So, we're not actually done with trees, we're just done with binary search trees. We're gonna keep on doing tree time, okay, everybody, tree time.

[00:00:14]
All right, so what we're gonna do, I want black. Have I used blue yet? Doesn't matter where you using black, okay, so, we're gonna start talking about graphs. Graphs are exciting, they're extremely complicated. Whenever you're doing a graph algorithm, it seems to be like you're not just doing one algorithm, you're just doing lines of algorithms, okay?

[00:00:33]
There's lots of lines of algorithms, people are getting really excited, police are being called, it's crazy. So we're gonna start doing graph time fun. So let's talk about graphs for a quick second. Graphs are fantastic, this a was written shoddily, all right, better, but a little high. Okay, that's very optimistic for that a.

[00:00:51]
So graphs, a couple terminologies, we usually use Vs and Es for graphs. So Vs stands for vertex, which that means there are vertices, and E stands for edges. Boom, we're about to become edge-lords today. Pretty good joke, I thought it was good, probably not that great, but I like it.

[00:01:10]
Anyways, all right, so now that we're doing that, there are two types of graphs when we're talking about edges and vertices. Is this right here is just a graph. We'd call this an undirected graph, meaning that A can go to B, B can go to A, there's no kind of like, hey, you're only allowed to go one direction.

[00:01:28]
So this would be C, this would be D, so I can go B, A, C, D or D, C, B, A, or A then B. You can do either direction and there's not a single problem here, right? That's called an undirected graph, undirected, meaning no implied direction of edges.

[00:01:54]
Implied is not the right word, but you know what I mean. All right, so if I were to draw arrows, this all of a sudden has a meaning now. This means that you can only go from C to D. You can only go from A to C. You cannot go from A to B, it's just not a thing, okay?

[00:02:15]
Don't make fetch happen, it's not happening, you can't do it, okay? And so, that means, sometimes graphs are like this, and this makes a lot of sense because if you think about a lot of real-world things, this is how it works. Like one way is on streets are directed edges in which you can only go one direction another, was that one time I went the wrong direction on a one way?

[00:02:33]
You can, but it's really bad, okay, if not a positive move at all. So directed means that you can only, directed means, in other words, one way. Now, you can have a double direct, right? I can do something like that. And during today, whenever we're doing directed graphs, I'll be writing it a specific way, which will look like this.

[00:02:53]
I'm just gonna erase this graph cuz it's too hard to erase those little tiny, teeny little arrows. I'll go like this, A, B, we're gonna mix them all up, C and D. When I do a direction, I'm gonna do a single side direction. The reason why, is when I go the other way, I can specify it like this.

[00:03:09]
And if you were to write weights on it, 2 and 3, I can do that. It's kind of like a little old hand trick to writing graphs because it can make it into a pretty compact representation, pretty fantastic. Okay, you get the idea. But what the heck are these?

[00:03:23]
Those are called weights, weights are what it cost to traverse that edge. So you could imagine that if you were doing Google Maps or something like that, you'd want to put the speed limit potentially as the weight, or the distance as the weight. You'd have something that represents traveling from D to A.

[00:03:42]
Maybe you wanna put the distance over speed, right? Because it is kind of a function of two things, which also may have traffic and other things implied, right? That's how you construct a graph in which now you're operating on a graph, doing these data structures on top of, such that you can move cars efficiently through the graph.

[00:04:02]
You get the idea, all right, fantastic. You guys are smart, you guys are getting this. Is there anything else? Yeah. So if I were to draw this again, what kind of graph is this?
>> Undirected.
>> Undirected weightless graph, perfect, nailed it, first try. This right here, this is called a connected component, meaning that I can go from A and visit every other node within this connected component.

[00:04:28]
So if I had a graph that had E over here and F, and they're just like, F yeah, we're having a great time over here, two connected components right here, right? You cannot go from E to B at any one point, so connect to component one, connect to component two.

[00:04:43]
All right, fun times. Just wanna make sure in case I use that term, you kinda know what it means, it's kind of important.