- 3 months ago
Learn graph basics: nodes, edges, neighbors, adjacency. Undirected vs directed, unweighted vs weighted. Representations including edge list, adjacency list, and matrix. Great intro for computer science students.
00:00 Graph Basics Introduction
00:41 Nodes and Edges
01:20 Node and Edge Classes in C++
03:46 Simple Graph Examples
04:29 Adding Edges - Undirected Unweighted
05:26 Real World Uses of Graphs
07:08 Graph Terminology - Neighbors and Adjacency
08:32 Edges Incident on Nodes
09:20 Graph Representations - Edge List
09:59 Adjacency List
10:27 Adjacency Matrix
11:19 Directed Graphs
13:04 Weighted Graphs and Path Costs
15:24 Video Conclusion
graph data structure, graphs computer science, nodes and edges, adjacency list, adjacency matrix, edge list, undirected graph, directed graph, weighted graph, C++ graph tutorial, data structures tutorial, computer science basics, graph terminology, graph representations
=-=-=-=-=-=-=-=-=
Thanks for watching!
Find us on other social media here:
- https://www.NeuralLantern.com/social
- Twitter / X: https://x.com/NeuralLantern
- Rumble: https://rumble.com/c/c-3696939
- BitChute: https://www.bitchute.com/channel/pg1Pvv5dN4Gt
- Daily Motion: https://www.dailymotion.com/neurallantern
- Minds: https://www.minds.com/neurallantern/
- Odysee: https://odysee.com/@NeuralLantern:5
Please show your support!
- Buy me a coffee: https://ko-fi.com/neurallantern
- Subscribe + Sharing on Social Media
- Leave a comment or suggestion
- Subscribe to the Blog: https://www.NeuralLantern.com
- Watch the main "pinned" video of this channel for offers and extras
00:00 Graph Basics Introduction
00:41 Nodes and Edges
01:20 Node and Edge Classes in C++
03:46 Simple Graph Examples
04:29 Adding Edges - Undirected Unweighted
05:26 Real World Uses of Graphs
07:08 Graph Terminology - Neighbors and Adjacency
08:32 Edges Incident on Nodes
09:20 Graph Representations - Edge List
09:59 Adjacency List
10:27 Adjacency Matrix
11:19 Directed Graphs
13:04 Weighted Graphs and Path Costs
15:24 Video Conclusion
graph data structure, graphs computer science, nodes and edges, adjacency list, adjacency matrix, edge list, undirected graph, directed graph, weighted graph, C++ graph tutorial, data structures tutorial, computer science basics, graph terminology, graph representations
=-=-=-=-=-=-=-=-=
Thanks for watching!
Find us on other social media here:
- https://www.NeuralLantern.com/social
- Twitter / X: https://x.com/NeuralLantern
- Rumble: https://rumble.com/c/c-3696939
- BitChute: https://www.bitchute.com/channel/pg1Pvv5dN4Gt
- Daily Motion: https://www.dailymotion.com/neurallantern
- Minds: https://www.minds.com/neurallantern/
- Odysee: https://odysee.com/@NeuralLantern:5
Please show your support!
- Buy me a coffee: https://ko-fi.com/neurallantern
- Subscribe + Sharing on Social Media
- Leave a comment or suggestion
- Subscribe to the Blog: https://www.NeuralLantern.com
- Watch the main "pinned" video of this channel for offers and extras
Category
🤖
TechTranscript
00:03Hello there, let's talk about graphs in the context of data structures and computer science.
00:09I just want to talk to you about some of the basics of graphs, some ways that we could
00:15implement them in the future, and some terminology.
00:27Okay, so for starters, we have a little blank graph sheet here.
00:31If you saw my previous video, you'll know already that this is a valid graph, it's just
00:35totally empty, there's nothing on it.
00:38But let me draw some data in this graph.
00:41So graphs are collections of nodes and edges, or vertices and edges, or vertex and edges.
00:49The nodes themselves, they are custom classes sometimes, other times not.
00:54But you can imagine that they hold some sort of custom data.
00:57So I know I did this in my last video, but I just want to emphasize that this graph class,
01:03if we're talking about C++, it should be a template class, meaning we can specify a custom data
01:08type that the nodes will hold and also a custom data type that the edges will have as their
01:13weight.
01:15You know, typically, when you see examples of this in the wild, it's just going to be integers.
01:20But you know, you could do other data types, like floats and strings, exotic custom classes,
01:27depending on your use case, it may or may not be useful to do that.
01:30But so we'll have a data type for our nodes.
01:33And I'll call it like n type for like our node type.
01:36And then we'll do another one called E type for edge type.
01:41I don't know if that's the best way to write those.
01:44But I'm just going to do it anyway.
01:46Imagine that your graph, like we said before, is a collection of nodes and edges.
01:51So I'm going to put a node class here, you can imagine this as a vertex class.
01:56And I'm going to say that this node holds an n type data, and we'll just call it data,
02:03or node value or whatever you want.
02:06And then the same thing for the edges, we'll say we have an edge class.
02:10I think in my last video, instead of doing a node class, I did a vertex class, it's kind
02:15of all the same.
02:16We'll say we have an E type, and we'll call it weight, or value or data if you want.
02:21But I think weight is a little bit closer to what we're going to actually be doing with it.
02:26And what do I mean by n type and E type?
02:28Like what are those data types there?
02:30That just means these are placeholder tokens.
02:32So when the user actually uses your graph by making an instance of your graph class,
02:38like they create an actual graph off of your blueprint class here,
02:42they might decide that they want integers inside of their nodes.
02:45So that's what I'm going to do right here, integers.
02:47They might decide that they want floats inside of your nodes, inside of their nodes,
02:52or some other data type.
02:53And so that means like at runtime, or I think actually at compile time for C++,
02:59this n type would actually change to int if they chose to use integers on the inside.
03:04Same thing would happen for the edge.
03:06Whatever they choose for the E type token is just going to end up being used at compile time to
03:13replace that E type.
03:14So I don't know. Here's an example.
03:16I got a fly in my room. It's bothering me.
03:21Imagine the user says, I want a graph, and I'll call it G.
03:25And so they just have to kind of specify the two data types.
03:28Maybe they want the graph to have integer values in the nodes,
03:32and maybe, you know, floating point, double precision floating point values on the edges in terms of weights.
03:39You know, you could do something like that.
03:41But anyway, so we have nodes and we have edges.
03:45And this graph right here is valid.
03:48It's just one node kind of floating around by itself.
03:51This graph is also still valid, even though we have two nodes that are floating unconnected and also with the
03:56same value.
03:56I'm just going to change the value to be different.
03:59Maybe I'll get rid of this extra thing here.
04:01So this is a valid graph still.
04:03We could have like a whole bunch of nodes all over the place.
04:08And they don't really have to be connected.
04:09This is still a valid graph.
04:11I'm going to change this to like a 3.
04:14Maybe change this to like an 11.
04:17Change that to a 6.
04:19What else can I change?
04:20How about like a 13?
04:21How about like a 17?
04:23Are there any duplicates?
04:26I don't think I see any.
04:27All right.
04:27So this is a valid graph.
04:29The next thing that we could add to our graph is edges.
04:34So edges are, you know, little mini data structures that connect nodes.
04:40In this particular graph, I'm choosing to not have direction on my edges, which means this is a special type
04:47of graph.
04:48Or four that we talked about in the previous video.
04:50This is unweighted and also undirected, meaning there's no weight assigned to the edges, which means that template weight value
04:59or the weight data type that we just talked about before.
05:01It's kind of useless for this particular graph because I'm saying it's unweighted.
05:08And well, all the edges, if we wanted to travel through the graph along the edges, we could just sort
05:14of go in any direction we felt like.
05:16So this is unweighted and undirected.
05:20Let's see.
05:21What else can I show you real fast?
05:23Okay.
05:23So let's talk about, well, really fast.
05:26Let's talk about the uses that you can have for a graph.
05:29I think I talked about this in the last video.
05:32But, you know, what can we use graphs for?
05:34Some people think they're databases.
05:36They're not really databases.
05:37You could technically do that, but it would be pretty slow.
05:40There are much better data structures for databases.
05:44Really what graphs are mostly used for is to represent relationships between different things.
05:49I think I said this in the last video.
05:51Imagine if every single node that you see here is a city and the edges represent flight paths.
05:56So we could fly between city seven and 11.
06:00Oh, that's funny.
06:01I'm hungry for candy bar.
06:03Now we can fly between city seven and 11 and back and, you know, back in the other direction if
06:09we want to, but we can't actually fly from city seven to six because there's no edge there.
06:14So we could represent computer networks.
06:18We could represent road maps, airports, dependency graphs, game maps.
06:24You could say like every node is somewhere your character could stand and an edge represents where your character could
06:30move or represents a connection to another node so that you know your character could move there.
06:36There's all sorts of different things that you could represent with the graph, but it's not necessarily a fast database.
06:42It's more of like a relationship, not to be confused with relational database, which is supposed to be lightning fast.
06:49Like if I wanted to search for the number 17 in this graph, it's not going to be long time
06:54like a proper database should be.
06:55It's not going to be constant time like a hash table based database should be either or like a no
07:02SQL or whatever.
07:05So we have undirected and unweighted.
07:07We talked about like different uses.
07:09Let's talk a little bit about terminology.
07:11Okay.
07:12For starters, notice how there's no hierarchy in this graph.
07:15In other videos, we're going to talk about binary search trees and we have to have like a hierarchy.
07:19There's no parent.
07:20There's no child in these graphs.
07:23There's no, you know, like grandchildren, ancestors, descendants, because there's not really like a hierarchy.
07:28It's just things are connected to each other or they're not.
07:31But we can have something called neighbors.
07:34For example, if you can reach a node in one hop, then you might be able to call that a
07:40neighbor.
07:41So six and 17, those are neighbors.
07:44Maybe I'll just type neighbors right here.
07:47Oops.
07:47Neighbors.
07:48Because we can reach them in one hop.
07:51Later on, or especially if I don't remember to mention this, if we add direction to our graph,
07:56then something is only considered a neighbor if you can reach it while respecting the direction of the graph.
08:01So we have like neighbors as six and 17.
08:04So that means six and 11 are also neighbors.
08:07Six and 12, not neighbors, because they can't reach each other in one hop.
08:13Let's see.
08:15Adjacency is basically the same thing.
08:17I can't remember.
08:18I think we use adjacency more often in directed graphs, but we could say that six and 17 are adjacent
08:24to each other,
08:24which is in this context sort of a synonym for neighbors.
08:28Okay.
08:29Something else that I want to talk about in terms of edges.
08:32Edges are considered to be incident upon nodes or vertices.
08:38So like, you know, if I have an arrow that just kind of points to these two things, I could
08:43say,
08:43you know, edge is incident upon three and 12.
08:48It's just, it just means, what are you touching?
08:50It's incident upon three and 12.
08:53Okay.
08:54What else should we talk about?
08:55We should talk about connected versus, no, that's another video.
09:01Okay.
09:01I'm going to do another video for connected versus not connected graphs.
09:04Maybe I should mention that there are three ways that we can represent the graph.
09:09And then maybe I'll upgrade to a directed graph in a second.
09:12If you want to know about the four different types of graphs, see my previous video.
09:15But for now, I'm going to say there are three ways we could represent these graphs.
09:23The first way, and I'm talking about how can you represent these graphs inside of the machine?
09:28Like how can your computer store and process this graph and maybe run algorithms on it?
09:34So the first way that we could represent, at least that I'm going to talk about, is an edge list.
09:39Edge lists are super simple.
09:40I'm going to do a dedicated video just for edge lists in the future.
09:45They're not very fast, but they're very easy to implement.
09:48So honestly, if you're just starting with this stuff, I would recommend just implementing an edge list first.
09:53The next thing that you can do to represent a graph in the machine is make an adjacency list.
10:00Adjacency lists are just a little bit more complicated, but they're typically faster than edge lists.
10:05Not always, not in all cases.
10:07And in terms of time complexity, you might not feel like you notice much of a difference.
10:13But empirically, adjacency lists just kind of give you the option of skipping a lot of examinations.
10:19When you don't need to examine something, you kind of skip it.
10:21We'll talk more about that in the future.
10:23But we have an edge list and an adjacency list of representation.
10:27And then we have an adjacency matrix.
10:31I wish I had spellcheck on this.
10:32Otherwise, this is going to be humiliating.
10:35An adjacency matrix is sometimes a lightning fast representation of a graph.
10:41At first, you might think, wow, that's amazing.
10:43I'm always going to use that.
10:45But all of these representations have strengths and weaknesses.
10:49None of them are better than the others in every single circumstance.
10:53So, you know, computer science and data structures, it's all about weighing the pros and cons and
10:58picking the right representation or algorithm or whatever.
11:01That's best for you and the code and the data that you're actually going to run.
11:04So three different ways that we can represent a graph in the future.
11:10And let's see, we spent 12 minutes already on this.
11:13We talked about the basic ways to use them, sort of.
11:17We talked about neighbors and adjacency.
11:20Oh, I got to upgrade to a directed graph real fast just to kind of show you the difference here.
11:25OK, so I'm going to duplicate this and I'm just going to start adding direction to all my edges.
11:31In my previous video, we talked about this.
11:33If you add direction to even one edge, then you have to add direction to all the other edges.
11:38Otherwise, you will have an invalid graph.
11:40So notice how I added direction to one edge.
11:43I now have an invalid graph.
11:45So I'm just going to do this.
11:47Change every single edge so that every single edge has a direction.
11:52You know, the basic thing we kind of talked about this in my previous video is that
11:56when traveling through the graph, you're supposed to only be able to travel in the direction of an edge,
12:02which means if you look at this thing right now, you're supposed to be able to go from 11 to
12:067,
12:07but you're not supposed to be able to go from 7 to 11 because that violates the direction of the
12:11edge.
12:12When we add direction, we're sort of like reducing, you know, the flexibility of the graph.
12:18So you can imagine that the previous version that was undirected, it was sort of like every single edge here
12:22was really two edges pointing in opposite directions, if that makes sense.
12:27So if you wanted to make sure that you could go back and forth between edge, sorry, between node 7
12:33and 11,
12:34well, just add another edge going in the opposite direction.
12:38You can also do things called parallel edges, which is just to say I'm going to add multiple edges that
12:45go in the same direction from the same start node to the same end node.
12:50But I'm not going to do that here. That makes it more complicated for some representations.
12:55But we can just sort of add a whole bunch of edges. I'm just going to say one going back
12:59and forth there and so forth.
13:02Remember in my previous video, we talked about weighted edges, which means we could add a cost to traveling along
13:07an edge.
13:08So you could say something like, I don't know, going from 7 to 12. Let's add another edge here.
13:15If there was a cost on all these weights, maybe I should just add that for fun.
13:19We could maybe calculate which path would be better.
13:22So let's say we got ones over here and we got fives over here and maybe like a two here
13:29and then sixes here and I'm going to do like an eight.
13:33By the way, these sixes don't have to be the same. It could just be two different numbers.
13:37So I'm going to do like a three here and let me just see if I added a weight to
13:40every single edge.
13:43So I know I did this in the previous video, but I want to do it again real fast.
13:46If we chose to take a path from seven to 12 and we said seven to 11 and then 11
13:52to 12.
13:53That's a very specific path, which is it's going to cost us five to go along that first.
14:00You have to go along that first edge.
14:02And then the second edge is going to cost us six and we're only traveling along two edges.
14:07So the total cost of that path is 11.
14:11On the other hand, let me actually make this look pink.
14:16On the other hand, if we're taking a different path, we might come up with a different cost depending on
14:22the graph.
14:23So let's say we start at seven.
14:26Maybe we want to go down to three and then from three, we'll go to 12.
14:31Well, that might be a different cost.
14:33So I'm going to say the cost of this particular path is traveling.
14:37It's going to cost us one to go down that first edge and then a two to go down that
14:41second edge,
14:42which means the total cost of getting to 12 is only three.
14:46Maybe if we take that orange path versus 11, if we take that pink path, I hope you're starting to
14:51visualize how graphs might be useful to visualize costs.
14:55If this is a network map, we just figured out that one route through the network might be faster or
15:01less costly than the other.
15:02Or if this is like an airport map, maybe you do want to take, you know, that layover that goes
15:07down south instead of that layover that goes east
15:11in terms of, I don't know, frequent flyer miles that it costs you or money it costs you or jet
15:17fuel that it costs the airport or whatever.
15:22So I think that's all I wanted to talk about in this video.
15:26I'm going to make one more video today.
15:28Well, it'll be released.
15:30I don't know when, but like in my present moment.
15:33I want to make another video right after this where we just talk about connected graphs versus not connected graphs.
15:38Thank you so much for watching this video.
15:40I hope you learned a little bit of stuff and had a little bit of fun.
15:46See you in the future.
15:53In the future.
15:56Hey everybody.
15:57Thanks for watching this video again from the bottom of my heart.
15:59I really appreciate it.
16:00I do hope you did learn something and have some fun.
16:03If you could do me a please, a small little favor, could you please subscribe and follow this channel or
16:10these videos or whatever it is you do on the current social media website that you're looking at right now.
16:15It would really mean the world to me and it'll help make more videos and grow this community.
16:19So we'll be able to do more videos, longer videos, better videos, or just I'll be able to keep making
16:24videos in general.
16:25So please do me a kindness and subscribe.
16:30You know, sometimes I'm sleeping in the middle of the night and I just wake up because I know somebody
16:34subscribed or followed.
16:35It just wakes me up and I get filled with joy.
16:37That's exactly what happens every single time.
16:39So you could do it as a nice favor to me or you could, you could troll me if you
16:43want to just wake me up in the middle of the night, just subscribe and then I'll, I'll just wake
16:46up.
16:47I promise that's what will happen.
16:49Also, uh, if you look at the middle of the screen right now, you should see a QR code, which
16:53you can scan in order to go to the website, which I think is also named somewhere at the bottom
16:57of this video.
16:58And it'll take you to my main website where you can just kind of like see all the videos I
17:03published and the services and tutorials and things that I offer and all that good stuff.
17:07And, uh, if you have a suggestion or, uh, uh, clarifications or errata or just future videos that you want
17:16to see, please leave a comment or if you just want to say, Hey, what's up?
17:20What's going on?
17:20You know, just send me a comment, whatever.
17:22I also wake up for those in the middle of the night.
17:24I get, I wake up in a cold sweat and I'm like, it would really, it would really mean the
17:29world to me.
17:30I would really appreciate it.
17:31So again, thank you so much for watching this video and, um, enjoy the cool music.
17:37As, as I fade into the darkness, which is coming for us all.
17:41Well, thanks very much.