1 00:00:06,780 --> 00:00:11,310 In this section, we are going to start talking about the graph. 2 00:00:11,310 --> 00:00:17,490 Data structure and graphs are an important data structure for us to understand because it allows us 3 00:00:17,490 --> 00:00:26,620 to begin implementing an algorithms such as the Dijkstra algorithm breadth first search and depth first 4 00:00:26,640 --> 00:00:29,460 search, which we will see in the coming sections. 5 00:00:30,450 --> 00:00:38,190 But for us to be able to understand how graphs work, there is some terminology that we need to first 6 00:00:38,190 --> 00:00:45,000 go over, such as what a what the vertices are and what edges are. 7 00:00:46,670 --> 00:00:56,210 So if we create a simple graph, we have nodes as such. 8 00:00:58,010 --> 00:01:00,950 And so these are going to be our. 9 00:01:02,300 --> 00:01:03,320 Vertices. 10 00:01:06,680 --> 00:01:11,510 So our vertices can also be just called nodes. 11 00:01:12,690 --> 00:01:17,280 And so what edges are going to do is they're going to connect the vertices. 12 00:01:21,350 --> 00:01:30,230 So we can have an edge and we'll give these labels A, B, C, and D so we can have an edge going from 13 00:01:30,230 --> 00:01:38,090 A to B, from B to D, from D to A and from A to C. 14 00:01:39,650 --> 00:01:47,210 So all of these are R edges and I'll label them E for edge. 15 00:01:49,800 --> 00:01:56,610 So you can see where this might be useful for us in a real world scenario. 16 00:01:56,790 --> 00:02:07,020 So assume that our vertices here is a city and then we have an edge and it's a road. 17 00:02:08,490 --> 00:02:15,690 So we have a bunch of cities and we have a bunch of edges, a.k.a. roads. 18 00:02:16,260 --> 00:02:27,120 So if these are our roads and these are our cities, so we'll say C, C and C, and then r, r and R 19 00:02:27,120 --> 00:02:28,300 for our roads. 20 00:02:28,320 --> 00:02:37,500 Well, now we can create or use an algorithm to figure out the quickest way to get from this node or 21 00:02:37,500 --> 00:02:44,730 this city to this city, because this road and this road might have more traffic than taking these three 22 00:02:44,730 --> 00:02:45,450 roads. 23 00:02:46,440 --> 00:02:48,870 So that's just one use case for a graph, right? 24 00:02:48,870 --> 00:02:55,950 So think of it as cities and then you take the edge a.k.a the road to get to the next city and so on 25 00:02:55,950 --> 00:03:00,210 and so forth until you're able to hit your desired destination. 26 00:03:02,280 --> 00:03:07,650 So we have some additional terminology that we can go over. 27 00:03:09,380 --> 00:03:14,660 And what we have is we have adjacent, vertices 28 00:03:17,990 --> 00:03:19,160 adjacent. 29 00:03:23,010 --> 00:03:24,000 Vertices. 30 00:03:25,170 --> 00:03:30,480 And this is the what connects the nodes. 31 00:03:32,700 --> 00:03:34,530 So a direct edge. 32 00:03:40,210 --> 00:03:43,150 Between the nodes, a.k.a. the vertices. 33 00:03:43,690 --> 00:03:47,800 We have the degree degree of a node. 34 00:03:53,410 --> 00:04:00,790 And this is the number of edges going to a vertex. 35 00:04:06,190 --> 00:04:08,050 So in this city. 36 00:04:08,050 --> 00:04:09,190 Note up here. 37 00:04:11,300 --> 00:04:17,540 The degree would be two because we have two edges going into this city. 38 00:04:19,820 --> 00:04:24,800 We have the path and this is how to get from one. 39 00:04:26,570 --> 00:04:28,700 Node to another. 40 00:04:45,060 --> 00:04:46,980 Oh, there you go. 41 00:04:49,020 --> 00:04:52,920 How to get from one note to another. 42 00:04:56,220 --> 00:04:58,290 We have our connected graph. 43 00:05:02,430 --> 00:05:04,210 And this is the path. 44 00:05:04,380 --> 00:05:09,270 This means that our graph has a path between. 45 00:05:11,600 --> 00:05:15,860 Every two nodes. 46 00:05:19,240 --> 00:05:22,180 And we also have a complete graph. 47 00:05:25,880 --> 00:05:29,330 And this means that there is a direct edge. 48 00:05:32,470 --> 00:05:33,580 Between. 49 00:05:37,440 --> 00:05:38,310 Any. 50 00:05:40,320 --> 00:05:41,250 To. 51 00:05:42,660 --> 00:05:43,530 Protects. 52 00:05:43,560 --> 00:05:56,940 So if we created a very simple graph with three, three nodes and we did this, this would be a connected 53 00:05:56,940 --> 00:06:03,660 graph because we have a path between every two vertices we can get from any vertices here to another 54 00:06:04,650 --> 00:06:05,220 vertices. 55 00:06:05,910 --> 00:06:12,600 And then if we add it in this edge, will we now have a complete graph because we have a direct edge 56 00:06:12,600 --> 00:06:14,580 between any two vertices. 57 00:06:14,580 --> 00:06:20,790 So in this case we can any, any node can get to any other vertex directly. 58 00:06:20,790 --> 00:06:22,890 So that is what a complete graph is. 59 00:06:25,820 --> 00:06:29,030 So now we have different types of graph. 60 00:06:33,920 --> 00:06:40,790 And there's quite a number types of graphs that we can talk about. 61 00:06:42,160 --> 00:06:44,970 And we have an undirected graph. 62 00:06:49,420 --> 00:06:53,860 And undirected means that you can go from one node. 63 00:06:54,710 --> 00:06:55,610 To another. 64 00:06:56,000 --> 00:06:57,950 And it's always both ways. 65 00:07:06,160 --> 00:07:09,040 We have a directed graph. 66 00:07:12,620 --> 00:07:18,170 And in this case only the A node can go to the B node. 67 00:07:20,090 --> 00:07:20,840 So. 68 00:07:23,090 --> 00:07:27,320 And here the edge only goes. 69 00:07:30,030 --> 00:07:33,000 From Node A to B? 70 00:07:37,160 --> 00:07:37,490 Right. 71 00:07:37,490 --> 00:07:43,220 So that's the difference here between our undirected and our directed and the undirected. 72 00:07:43,820 --> 00:07:50,450 We can go either from A to B or B to A, but as soon as we have A directed, we can only go in this 73 00:07:50,450 --> 00:07:54,290 case from A to B, we cannot go from B to A. 74 00:07:56,690 --> 00:07:59,150 We also have an unweighted graph. 75 00:08:03,410 --> 00:08:05,810 So that means we can go from a 76 00:08:08,660 --> 00:08:09,890 I don't want to have a directed. 77 00:08:09,890 --> 00:08:18,920 We can go from A to B to C, and there are no weights associated with any of these edges. 78 00:08:19,490 --> 00:08:26,860 So you can imagine a weighted graph is the counterpart to this. 79 00:08:26,870 --> 00:08:36,440 And if we have A, B, C, and this is still an undirected graph, we can have a weight of five and 80 00:08:36,440 --> 00:08:38,320 we can have a weight of three. 81 00:08:38,330 --> 00:08:45,650 So from A to B, it's going to cost us five and from B to C, it will cost us three. 82 00:08:45,650 --> 00:08:51,470 So an easy way to think of this is think of weights. 83 00:08:53,700 --> 00:08:55,710 As distance. 84 00:08:58,500 --> 00:08:59,430 Or time. 85 00:09:02,250 --> 00:09:14,390 So if we go back to using a city for an example, so we have City A city B, city C, and we'll say 86 00:09:14,970 --> 00:09:15,960 City D. 87 00:09:16,900 --> 00:09:19,360 But we have, say, six. 88 00:09:20,470 --> 00:09:21,430 Three. 89 00:09:24,340 --> 00:09:29,830 Two, and let's add one here and we'll say that this is one. 90 00:09:31,330 --> 00:09:33,880 Well, for us to get from A to DH. 91 00:09:35,670 --> 00:09:37,560 Yeah, let's change it from one. 92 00:09:37,570 --> 00:09:38,440 Let's make it. 93 00:09:39,720 --> 00:09:41,680 Five just that way. 94 00:09:41,730 --> 00:09:46,380 It's not as obvious for us to get to a2d here. 95 00:09:47,460 --> 00:09:56,070 We would go from A to C, so A to C where our weight is equal to five and then we would go from C to 96 00:09:56,070 --> 00:09:58,460 D, where our weight equals two. 97 00:09:58,470 --> 00:10:02,430 So our total weight for that path would be seven. 98 00:10:02,670 --> 00:10:09,360 Whereas if we went A, B, C to D, then we would have six plus three plus two obviously, which is 99 00:10:09,360 --> 00:10:09,810 nine. 100 00:10:09,810 --> 00:10:16,020 So that would not be the most efficient path for us to take in this case to get from A to D. 101 00:10:17,100 --> 00:10:26,280 So think of that back to the going from city to city you could think of these weights is how much traffic 102 00:10:26,280 --> 00:10:27,120 there may be. 103 00:10:27,750 --> 00:10:31,170 So how much time it will take if we go a certain route. 104 00:10:31,170 --> 00:10:36,090 So we want to find obviously the most optimal path which we can do. 105 00:10:37,590 --> 00:10:42,960 Using algorithms such as Dijkstra's or breadth first and depth first. 106 00:10:45,400 --> 00:10:53,380 So the last thing that we can do is how we can represent a graph data structure. 107 00:10:53,830 --> 00:11:01,930 And what I'm going to do is use an adjacency matrix to represent. 108 00:11:05,250 --> 00:11:07,380 Nodes and our edges. 109 00:11:07,950 --> 00:11:18,030 So let's imagine that we have A, B, C, and D for our nodes. 110 00:11:20,780 --> 00:11:30,500 So what we can do is we can create A matrix, A, B, C, and D, and then we can also have a. 111 00:11:31,260 --> 00:11:38,790 B, C, and D here and inside we create our matrix. 112 00:11:39,930 --> 00:11:41,640 And that was not what I wanted to do. 113 00:11:43,880 --> 00:11:46,070 So in here, we're creating our matrix. 114 00:11:50,420 --> 00:11:53,450 And so so that we can visually represent this. 115 00:11:53,480 --> 00:12:06,590 Let's do A, B, C, and D, and we'll create our graph from above. 116 00:12:07,100 --> 00:12:14,660 So we see that we go from A to B so we can put a one and we go from A to C. 117 00:12:15,110 --> 00:12:16,510 So we put a one. 118 00:12:16,520 --> 00:12:22,880 And since there is nothing, there's not a path from A to a meaning. 119 00:12:22,880 --> 00:12:24,630 This is what that would look like. 120 00:12:24,650 --> 00:12:26,030 So we don't have that. 121 00:12:27,270 --> 00:12:34,800 So now we can go to the B node we see we connect to from B to A and also from B to C, C connects to 122 00:12:34,800 --> 00:12:44,760 B and C connects to D, and then D only connects to C, And this is an example of an unweighted undirected 123 00:12:44,760 --> 00:12:53,460 graph, and this is how we were able to represent this very simply with what nodes connect to what other 124 00:12:53,460 --> 00:12:54,990 nodes via the edges. 125 00:12:55,440 --> 00:13:00,570 So our representation in here is our edge if it exists or not. 126 00:13:02,070 --> 00:13:10,050 Otherwise everything can be initialized to zero to indicate that there are no edges between those two 127 00:13:10,950 --> 00:13:11,550 nodes. 128 00:13:13,030 --> 00:13:20,440 So now that we have a good understanding of how graphs work and how we can represent a graph, we will 129 00:13:20,440 --> 00:13:24,730 begin implementing in our own graph and the next lecture. 130 00:13:25,850 --> 00:13:31,250 And if you have any questions at any point, please feel free to ask them in the Q&A section.