1 00:00:01,540 --> 00:00:02,640 - [Instructor] And now we're gonna move on 2 00:00:02,640 --> 00:00:06,510 to the very last topic that we're going to cover. 3 00:00:06,510 --> 00:00:09,710 The last new material that we're gonna have in this course, 4 00:00:09,710 --> 00:00:12,203 which is the minimum spanning tree. 5 00:00:13,230 --> 00:00:16,000 And here in this video, we're gonna present 6 00:00:16,000 --> 00:00:19,150 what's called Prim's algorithm, which is one algorithm 7 00:00:19,150 --> 00:00:22,790 for finding a minimum spanning tree in a graph. 8 00:00:22,790 --> 00:00:25,990 And in a subsequent video, we're going to present 9 00:00:25,990 --> 00:00:29,170 another algorithm called Kruskal's algorithm, 10 00:00:29,170 --> 00:00:31,263 both named after their inventors. 11 00:00:32,240 --> 00:00:35,130 But before we talk about minimum spanning trees, 12 00:00:35,130 --> 00:00:37,920 let's just do a quick review of trees. 13 00:00:37,920 --> 00:00:39,650 So, what is a tree? 14 00:00:39,650 --> 00:00:43,640 You'll recall that a tree is an acyclic, 15 00:00:43,640 --> 00:00:46,950 connected, undirected graph. 16 00:00:46,950 --> 00:00:48,440 Now here's an example of a tree 17 00:00:48,440 --> 00:00:50,230 and let's check its properties. 18 00:00:50,230 --> 00:00:51,840 Is it acyclic? 19 00:00:51,840 --> 00:00:54,950 Yeah, we can see that there are no cycles. 20 00:00:54,950 --> 00:00:56,840 A cycle exists when there's more 21 00:00:56,840 --> 00:00:59,600 than one path connecting any two nodes in a graph. 22 00:00:59,600 --> 00:01:02,590 And here we can see that for each pair of nodes 23 00:01:02,590 --> 00:01:05,110 there is not more than one path connecting them. 24 00:01:05,110 --> 00:01:07,330 In fact, there's exactly one path. 25 00:01:07,330 --> 00:01:09,090 It's a property of a tree. 26 00:01:09,090 --> 00:01:10,140 Is it connected? 27 00:01:10,140 --> 00:01:13,060 Yep, for each pair of nodes in the graph, 28 00:01:13,060 --> 00:01:15,430 there is some path that connects them. 29 00:01:15,430 --> 00:01:17,323 So we have a tree and not a forest. 30 00:01:19,670 --> 00:01:21,490 Is it undirected? 31 00:01:21,490 --> 00:01:23,600 Yes, the edges are undirected, 32 00:01:23,600 --> 00:01:26,263 and so this graph has all the properties of a tree. 33 00:01:27,560 --> 00:01:29,440 Here are some counterexamples. 34 00:01:29,440 --> 00:01:33,150 We can see on the left here, this is not acyclic 35 00:01:33,150 --> 00:01:36,840 because we have a cycle here, so that's not a tree. 36 00:01:36,840 --> 00:01:38,510 This is not connected 37 00:01:38,510 --> 00:01:42,890 because we have this disconnected node here, b. 38 00:01:42,890 --> 00:01:46,730 It's a perfectly fine forest because a, c, d 39 00:01:46,730 --> 00:01:50,683 and h form a valid tree and b by itself, 40 00:01:51,590 --> 00:01:56,590 a single node I should say, is also a perfectly fine tree. 41 00:01:56,700 --> 00:01:59,390 So this is a forest, but not a tree. 42 00:01:59,390 --> 00:02:04,173 And this graph is directed and so not a tree. 43 00:02:05,150 --> 00:02:07,060 Some people might quibble with that last one 44 00:02:07,060 --> 00:02:09,393 but that's the way we're gonna roll. 45 00:02:10,300 --> 00:02:14,320 Another reminder here is that if we have a tree on n nodes, 46 00:02:14,320 --> 00:02:18,710 it's gonna have exactly n minus one edges. 47 00:02:18,710 --> 00:02:21,150 It's gotta have exactly n minus one edges. 48 00:02:21,150 --> 00:02:23,880 If it has fewer than n minus one edges, 49 00:02:23,880 --> 00:02:28,400 then it's not connected, some edge is missing. 50 00:02:28,400 --> 00:02:32,240 And if it has n or more edges, then it has to have a cycle. 51 00:02:32,240 --> 00:02:35,380 For example, if we look at this tree here, 52 00:02:35,380 --> 00:02:38,620 there is no way we can add another edge. 53 00:02:38,620 --> 00:02:40,940 We have one, two, three, four, five nodes 54 00:02:40,940 --> 00:02:45,810 and we have one, two, three, four, n minus one edges. 55 00:02:45,810 --> 00:02:49,280 If we add any edge, anywhere else in this graph, 56 00:02:49,280 --> 00:02:50,360 we're gonna create a cycle, 57 00:02:50,360 --> 00:02:55,360 we have to, ch, cb, bd, ah, dh, they'll all form cycles. 58 00:02:57,620 --> 00:03:01,550 So, if we have a tree on n nodes, 59 00:03:01,550 --> 00:03:04,143 it's gonna have exactly n minus one edges. 60 00:03:06,300 --> 00:03:08,440 So now we can move on to the topic 61 00:03:08,440 --> 00:03:11,470 of what is a spanning tree. 62 00:03:11,470 --> 00:03:14,410 We'll do that before we get to a minimum spanning tree. 63 00:03:14,410 --> 00:03:17,500 So, given some graph like we have here, 64 00:03:17,500 --> 00:03:22,500 we have this graph that is node set, V and an edge set, E. 65 00:03:23,140 --> 00:03:27,060 We say a spanning tree of the graph 66 00:03:27,060 --> 00:03:32,050 consists of the node set, the node set is the same. 67 00:03:32,050 --> 00:03:36,240 And some subset of the edge set, we'll call it E prime, 68 00:03:36,240 --> 00:03:40,310 such that we have a spanning tree. 69 00:03:40,310 --> 00:03:42,320 So, what does that look like? 70 00:03:42,320 --> 00:03:47,320 So here we have the starting graph here G, 71 00:03:47,550 --> 00:03:51,170 is the node set and the edge set. 72 00:03:51,170 --> 00:03:54,403 And we have this spanning tree we call G prime, 73 00:03:55,500 --> 00:03:58,500 which has exactly the same node set 74 00:03:58,500 --> 00:04:00,440 but it has a different edge set, 75 00:04:00,440 --> 00:04:05,440 but the edge set is a subset of the edges in this graph. 76 00:04:05,890 --> 00:04:10,840 And we wanna pick a subset of the edges, 77 00:04:10,840 --> 00:04:15,840 such that every node is incident to some edge 78 00:04:18,390 --> 00:04:22,100 and the edges themselves, you know, form a tree. 79 00:04:22,100 --> 00:04:25,683 So this is a spanning tree of this graph. 80 00:04:26,630 --> 00:04:29,960 The tree touches every node in the graph, 81 00:04:29,960 --> 00:04:32,600 that's what it means to span. 82 00:04:32,600 --> 00:04:36,100 There may be more than one spanning tree in a graph. 83 00:04:36,100 --> 00:04:37,610 As a matter of fact, there will be more 84 00:04:37,610 --> 00:04:39,820 than one spanning tree in a graph. 85 00:04:39,820 --> 00:04:43,120 So, here's another perfectly good spanning tree. 86 00:04:43,120 --> 00:04:47,510 Again, we have G prime, the spanning tree, 87 00:04:47,510 --> 00:04:52,410 which is has the same node set as the original graph 88 00:04:52,410 --> 00:04:56,010 but it has a subset of the edges that form a tree 89 00:04:56,010 --> 00:04:59,410 such that all of the nodes are connected. 90 00:04:59,410 --> 00:05:03,490 There's exactly one path between every pair of nodes. 91 00:05:03,490 --> 00:05:05,290 And so that's another spanning tree. 92 00:05:07,670 --> 00:05:08,860 Now you've probably figured out 93 00:05:08,860 --> 00:05:10,490 where we are heading with this. 94 00:05:10,490 --> 00:05:13,580 What if the graph G is weighted? 95 00:05:13,580 --> 00:05:16,750 Well, finding a minimum spanning tree 96 00:05:16,750 --> 00:05:19,870 is the problem of finding a spanning tree 97 00:05:19,870 --> 00:05:22,520 with the sum of the weights minimized. 98 00:05:22,520 --> 00:05:27,300 So given this graph with this node set and this edge set 99 00:05:27,300 --> 00:05:28,650 and the edges are weighted, 100 00:05:29,780 --> 00:05:34,780 we wanna find this spanning tree, G prime, 101 00:05:35,620 --> 00:05:39,070 with the same node set and this edge set, which is a subset 102 00:05:39,070 --> 00:05:42,760 of the original sets such that G prime is a tree. 103 00:05:42,760 --> 00:05:45,760 And we minimize, argmin just means we're just trying 104 00:05:45,760 --> 00:05:47,520 to minimize this big, old sum here. 105 00:05:47,520 --> 00:05:49,940 We've got a sum of all the weights 106 00:05:49,940 --> 00:05:54,940 for every u,v in this edge set we sum the weight 107 00:05:55,600 --> 00:05:57,430 that corresponds to that edge. 108 00:05:57,430 --> 00:06:02,430 And we wanna find the set of edges that minimizes this sum. 109 00:06:03,410 --> 00:06:06,890 So, that's a minimum spanning tree. 110 00:06:06,890 --> 00:06:10,617 Here's a minimum spanning tree, okay? 111 00:06:10,617 --> 00:06:15,617 And this, the sum here of all of these edge weights is 12. 112 00:06:16,620 --> 00:06:18,780 And that's the subset of edges 113 00:06:18,780 --> 00:06:21,740 that yields the smallest possible sum. 114 00:06:21,740 --> 00:06:24,800 Maybe we can't swap any edge, for example, 115 00:06:24,800 --> 00:06:27,340 here's this one with weight three. 116 00:06:27,340 --> 00:06:31,260 If we swap it for this one to connect b to h, 117 00:06:31,260 --> 00:06:35,953 we'll get a sum of 13, so we can't do that. 118 00:06:36,810 --> 00:06:39,760 There's no edge that we can substitute in 119 00:06:39,760 --> 00:06:41,500 that would give us a lower sum. 120 00:06:41,500 --> 00:06:43,523 So this is a minimum spanning tree. 121 00:06:45,485 --> 00:06:47,870 But what are some applications of minimum spanning trees? 122 00:06:47,870 --> 00:06:49,850 Well, there are lots of them. 123 00:06:49,850 --> 00:06:53,010 They're used in telecommunications, in taxonomy 124 00:06:53,010 --> 00:06:57,740 and phylogeny, computer networks, electronic circuit design, 125 00:06:57,740 --> 00:07:00,970 computer vision, process control, any situation 126 00:07:00,970 --> 00:07:04,700 where we have a network and we wanna find 127 00:07:04,700 --> 00:07:09,000 the smallest weight or smallest distance tree 128 00:07:09,000 --> 00:07:11,123 that touches every point in the network. 129 00:07:12,330 --> 00:07:14,250 I'm gonna start the discussion 130 00:07:14,250 --> 00:07:17,120 of Prim's algorithm with the pseudocode. 131 00:07:17,120 --> 00:07:19,140 So here we have this function, prims 132 00:07:19,140 --> 00:07:24,140 and it takes in this graph which we call G. 133 00:07:24,330 --> 00:07:27,980 And we start by initializing this subset of edges 134 00:07:27,980 --> 00:07:30,683 that we've called E prime to an empty set. 135 00:07:31,610 --> 00:07:36,273 And then we can pick any starting node, S, in the node set. 136 00:07:37,830 --> 00:07:42,830 And we have this node set here, V prime, which we will build 137 00:07:45,900 --> 00:07:50,650 until it is the same as the original V here 138 00:07:50,650 --> 00:07:55,180 but we'll start that off with this randomly chosen node 139 00:07:55,180 --> 00:07:56,363 as the starting node. 140 00:07:57,220 --> 00:07:59,143 It doesn't matter which node we pick, 141 00:08:01,130 --> 00:08:03,160 every node is gonna have to be touched by an edge 142 00:08:03,160 --> 00:08:04,723 so we can start at any point. 143 00:08:05,610 --> 00:08:10,610 But as long as the cardinality of this node set here 144 00:08:11,250 --> 00:08:13,420 for the graph that we're building, 145 00:08:13,420 --> 00:08:15,290 the minimum spanning tree that we're building 146 00:08:15,290 --> 00:08:19,670 is less than the cardinality of the node set 147 00:08:19,670 --> 00:08:21,960 of the underlying graph, we keep doing something. 148 00:08:21,960 --> 00:08:23,940 What is it that we keep doing? 149 00:08:23,940 --> 00:08:27,810 Well, we find the minimum weight edge 150 00:08:27,810 --> 00:08:32,810 with exactly one endpoint in this set, V prime. 151 00:08:34,020 --> 00:08:37,000 We add this edge to E prime. 152 00:08:37,000 --> 00:08:39,770 And then we add the endpoint of E 153 00:08:39,770 --> 00:08:43,770 that's not already in V prime to V prime. 154 00:08:43,770 --> 00:08:46,863 And we do that until these two numbers are equal. 155 00:08:48,000 --> 00:08:52,350 And then we return and we returned with the node set 156 00:08:53,890 --> 00:08:55,500 which is going to be identical 157 00:08:55,500 --> 00:08:59,160 to the input graph and this subset of edges. 158 00:08:59,160 --> 00:09:02,203 So, let's walk through that and see how that works. 159 00:09:03,160 --> 00:09:07,580 So, here is a graph and we're gonna perform Prim's algorithm 160 00:09:07,580 --> 00:09:08,940 on this graph. 161 00:09:08,940 --> 00:09:13,940 And we have the graph consists of this node set a, b, c, 162 00:09:14,660 --> 00:09:19,660 d, j and h, and this edge set ab, ac, ah, and so on. 163 00:09:20,520 --> 00:09:25,520 And we start with these sets initialized to the empty set. 164 00:09:26,680 --> 00:09:27,920 And the first thing we're gonna do 165 00:09:27,920 --> 00:09:30,790 is we're gonna pick a node at random 166 00:09:30,790 --> 00:09:33,630 and we're gonna add that to V prime. 167 00:09:33,630 --> 00:09:35,610 Okay, so we've added a to V prime. 168 00:09:35,610 --> 00:09:37,940 I could have chosen any node, it doesn't matter, 169 00:09:37,940 --> 00:09:38,993 but we just chose a. 170 00:09:40,560 --> 00:09:43,400 Then what we're gonna do is we're gonna find 171 00:09:43,400 --> 00:09:48,400 the minimum weight edge that has exactly one endpoint 172 00:09:50,414 --> 00:09:51,331 in V prime. 173 00:09:52,173 --> 00:09:54,756 So what's the minimum weight edge 174 00:09:54,756 --> 00:09:57,340 that has exactly one end point in V prime? 175 00:09:57,340 --> 00:09:58,630 Well, it's this one right here. 176 00:09:58,630 --> 00:10:00,080 This one, this weight is two. 177 00:10:01,380 --> 00:10:04,130 So what we're gonna do is we're gonna add this edge 178 00:10:04,130 --> 00:10:07,280 and this node, so let's see how that works. 179 00:10:07,280 --> 00:10:12,280 There's the edge and so we add the edge ac to E prime, 180 00:10:13,000 --> 00:10:17,480 that's our subset of edges that will form our spanning tree. 181 00:10:17,480 --> 00:10:20,840 And we add c two V prime, okay? 182 00:10:20,840 --> 00:10:22,470 That's our first step. 183 00:10:22,470 --> 00:10:23,770 Now we do this again. 184 00:10:23,770 --> 00:10:28,770 We ask ourselves, okay, here's the new V prime. 185 00:10:28,800 --> 00:10:31,820 What is the smallest weight edge 186 00:10:31,820 --> 00:10:36,690 that has exactly one end point in V prime? 187 00:10:36,690 --> 00:10:40,260 And again, here, we can find this one here is three, 188 00:10:40,260 --> 00:10:44,610 this one here is four, nine, seven, eight. 189 00:10:44,610 --> 00:10:46,490 It's gotta be this one, right? 190 00:10:46,490 --> 00:10:51,490 So, at the next step, we add the edge cj to E prime 191 00:10:53,260 --> 00:10:55,230 and we add j to V prime. 192 00:10:55,230 --> 00:10:59,340 And then we do it again, because, you notice the cardinality 193 00:10:59,340 --> 00:11:02,900 of V prime hasn't reached the cardinality of V yet. 194 00:11:02,900 --> 00:11:04,700 So, what now? 195 00:11:04,700 --> 00:11:07,160 If this is our new V prime, 196 00:11:07,160 --> 00:11:12,160 these three nodes here, what is the smallest weight edge 197 00:11:14,400 --> 00:11:17,810 that has exactly one end point in V prime? 198 00:11:17,810 --> 00:11:20,060 Well, this one here, okay? 199 00:11:20,060 --> 00:11:21,980 So we're gonna add that. 200 00:11:21,980 --> 00:11:26,980 So now b is added to V prime, the edge ab is added to E. 201 00:11:27,610 --> 00:11:32,480 Remember how I said that a tree on n nodes 202 00:11:34,780 --> 00:11:36,880 has exactly n minus one edges, 203 00:11:36,880 --> 00:11:38,550 it's should come as no surprise 204 00:11:38,550 --> 00:11:42,100 that as we're building this for whatever n we have 205 00:11:42,100 --> 00:11:45,530 in V prime, we're always gonna have n minus one edges here. 206 00:11:45,530 --> 00:11:47,740 So I just wanna make that observation. 207 00:11:47,740 --> 00:11:48,940 Then we iterate again, 208 00:11:48,940 --> 00:11:50,560 what's the next edge that we add? 209 00:11:50,560 --> 00:11:51,533 The smallest weight edge 210 00:11:51,533 --> 00:11:54,300 that has exactly one endpoint in V prime. 211 00:11:54,300 --> 00:11:57,810 It's this one here, this edge bd. 212 00:11:57,810 --> 00:12:01,280 And so we add that one, we add bd to E prime, 213 00:12:01,280 --> 00:12:06,280 we add d to V prime, and we have one more edge to find 214 00:12:06,500 --> 00:12:11,420 because we're missing one node in this node set. 215 00:12:11,420 --> 00:12:14,440 And so we find, again, this is gonna be 216 00:12:14,440 --> 00:12:16,210 the smallest weight edge 217 00:12:16,210 --> 00:12:19,400 that has exactly one endpoint in V prime. 218 00:12:19,400 --> 00:12:21,700 And so we add that to V prime, 219 00:12:21,700 --> 00:12:25,750 we add the edge to E prime and now the cardinality 220 00:12:25,750 --> 00:12:29,160 of these two sets is the same. 221 00:12:29,160 --> 00:12:32,950 And that's our condition for exiting that while loop. 222 00:12:32,950 --> 00:12:37,950 And so the algorithm terminates yielding this V prime 223 00:12:38,600 --> 00:12:41,180 which node is exactly the same set 224 00:12:41,180 --> 00:12:46,180 as the original V and this subset of edges. 225 00:12:46,540 --> 00:12:49,850 So that's finding a minimum spanning tree 226 00:12:49,850 --> 00:12:51,333 by Prim's algorithm. 227 00:12:54,250 --> 00:12:58,000 Now, it might be the case that we have more 228 00:12:58,000 --> 00:13:02,980 than one minimum spanning tree for a given graph. 229 00:13:02,980 --> 00:13:07,980 Here these two trees have exactly the same weight, 230 00:13:08,330 --> 00:13:10,700 so we're not guaranteed to find 231 00:13:10,700 --> 00:13:12,970 a particular minimum spanning tree, 232 00:13:12,970 --> 00:13:16,923 we're just guaranteed to find a minimum spanning tree. 233 00:13:20,430 --> 00:13:21,530 And how does that work? 234 00:13:21,530 --> 00:13:23,670 Well, if you take a look here 235 00:13:23,670 --> 00:13:28,670 and we say the green colored nodes are our V prime 236 00:13:29,410 --> 00:13:32,690 and we're looking for the minimum weight edge 237 00:13:32,690 --> 00:13:36,280 that has exactly one endpoint in V prime, 238 00:13:36,280 --> 00:13:37,750 we're gonna find these two edges. 239 00:13:37,750 --> 00:13:40,610 These both have a weight of three. 240 00:13:40,610 --> 00:13:43,930 And so we could add either one to our minimum spanning tree, 241 00:13:43,930 --> 00:13:44,900 it doesn't matter. 242 00:13:44,900 --> 00:13:47,200 And so in the case of the algorithm, 243 00:13:47,200 --> 00:13:51,530 there might be some order that's already present 244 00:13:51,530 --> 00:13:54,340 in the underlying data, or we could toss a coin, 245 00:13:54,340 --> 00:13:55,230 it doesn't matter. 246 00:13:55,230 --> 00:13:56,760 We're gonna pick one or the other. 247 00:13:56,760 --> 00:13:58,253 But if we pick this one, 248 00:13:59,180 --> 00:14:01,970 then we gonna get one minimum spanning tree. 249 00:14:01,970 --> 00:14:03,460 And if we pick this one, we're gonna get 250 00:14:03,460 --> 00:14:06,190 a different minimum spanning tree. 251 00:14:06,190 --> 00:14:09,650 So if we pick this one, we're gonna get one tree. 252 00:14:09,650 --> 00:14:11,320 If we pick this one, we're gonna get another. 253 00:14:11,320 --> 00:14:14,820 And that's why Prim's algorithm doesn't guarantee 254 00:14:14,820 --> 00:14:18,420 that it's gonna find a particular minimum standing tree, 255 00:14:18,420 --> 00:14:20,463 just a minimum spanning tree. 256 00:14:22,110 --> 00:14:25,130 So, let's get more into the details 257 00:14:25,130 --> 00:14:28,140 of how this algorithm works in practice. 258 00:14:28,140 --> 00:14:32,020 I've done a lot of hand wavy stuff about looking 259 00:14:32,020 --> 00:14:37,020 for the edge with exactly one end point in V prime 260 00:14:38,470 --> 00:14:40,270 that has the smallest weight, 261 00:14:40,270 --> 00:14:43,400 but how do we actually do that in practice? 262 00:14:43,400 --> 00:14:47,760 And so here, we've got this graph 263 00:14:47,760 --> 00:14:49,990 and we're gonna do Prim's algorithm 264 00:14:49,990 --> 00:14:53,920 with a little more detail looking under the hood. 265 00:14:53,920 --> 00:14:58,163 And here we have, does anybody remember what this is called? 266 00:15:00,010 --> 00:15:02,120 This is an adjacency matrix. 267 00:15:02,120 --> 00:15:05,330 And why haven't we included the lower left triangle? 268 00:15:05,330 --> 00:15:07,060 Because this is an undirected graph. 269 00:15:07,060 --> 00:15:10,210 And so this is just gonna be a mirror image over here. 270 00:15:10,210 --> 00:15:12,480 So the only information that we need to keep track of 271 00:15:12,480 --> 00:15:15,190 is what's in this upper triangle here. 272 00:15:15,190 --> 00:15:18,370 And we also have this auxiliary table. 273 00:15:18,370 --> 00:15:19,560 So what's going on here? 274 00:15:19,560 --> 00:15:21,520 Well, let me show you how this works. 275 00:15:21,520 --> 00:15:23,560 We're gonna run Prim's algorithm now. 276 00:15:23,560 --> 00:15:25,690 We're gonna pick b this time again, 277 00:15:25,690 --> 00:15:29,040 I could choose any node, it doesn't matter, 278 00:15:29,040 --> 00:15:32,250 but we'll pick b just for variety's sake. 279 00:15:32,250 --> 00:15:33,630 And let's see what happens. 280 00:15:33,630 --> 00:15:38,630 So we've chosen b and whenever we add a node to V prime, 281 00:15:40,620 --> 00:15:44,143 see b is in V prime now, we update this table. 282 00:15:44,990 --> 00:15:49,700 And for each node not in V prime, we keep track of the node 283 00:15:49,700 --> 00:15:52,810 in V prime connected by the lowest weight edge 284 00:15:52,810 --> 00:15:54,413 and we store that weight. 285 00:15:56,290 --> 00:15:59,670 So here, b is the only node in V prime 286 00:15:59,670 --> 00:16:02,870 and we have the lowest weight neighbor 287 00:16:02,870 --> 00:16:06,500 and the edge weight for all other nodes adjacent to b. 288 00:16:06,500 --> 00:16:11,500 So, for example, we have a, it has a weight of two, 289 00:16:13,740 --> 00:16:16,540 b, we don't include, there's no self loop to b, 290 00:16:16,540 --> 00:16:18,960 so that's off the table. 291 00:16:18,960 --> 00:16:22,880 We have, c, let's see, c the smallest 292 00:16:22,880 --> 00:16:24,840 weight edge here is seven. 293 00:16:24,840 --> 00:16:26,203 There's only one right now. 294 00:16:27,720 --> 00:16:29,990 For d, we have this connection to b, 295 00:16:29,990 --> 00:16:32,150 which has a weight of three. 296 00:16:32,150 --> 00:16:37,150 J we can't get to b yet, there is no connection 297 00:16:37,860 --> 00:16:40,850 from j to V prime yet. 298 00:16:40,850 --> 00:16:45,730 'Cause j is only connected to c, a, d and h. 299 00:16:45,730 --> 00:16:49,250 So one of those nodes would have to be in V prime 300 00:16:49,250 --> 00:16:51,070 for j to be connected to it. 301 00:16:51,070 --> 00:16:53,120 So we have no entry for j 302 00:16:53,120 --> 00:16:57,363 and then we have this entry for h, which is this entry. 303 00:16:59,160 --> 00:17:00,820 That's how this table works. 304 00:17:00,820 --> 00:17:05,820 And we update that every time we add a new node to V prime. 305 00:17:09,320 --> 00:17:11,800 We can see from this table here 306 00:17:11,800 --> 00:17:16,800 that we could choose either of two edges for our next step. 307 00:17:17,270 --> 00:17:22,270 We could add either this edge here or this edge here. 308 00:17:22,500 --> 00:17:24,560 And we just know that by looking in this table 309 00:17:24,560 --> 00:17:26,220 and finding the minimum weight, 310 00:17:26,220 --> 00:17:28,810 and we find two with the minimum weight. 311 00:17:28,810 --> 00:17:30,270 And it doesn't matter which we pick. 312 00:17:30,270 --> 00:17:32,090 So let's pick a, right? 313 00:17:32,090 --> 00:17:33,920 So we're gonna pick a. 314 00:17:33,920 --> 00:17:37,513 So now we've added this edge ab into E prime. 315 00:17:39,100 --> 00:17:44,100 Let's add a, and so now we need to update this table 316 00:17:44,340 --> 00:17:45,600 on the right. 317 00:17:45,600 --> 00:17:48,670 And now a and b are both in V prime. 318 00:17:48,670 --> 00:17:51,930 So we update the values that we need to update. 319 00:17:51,930 --> 00:17:53,640 And the only one that we need to update 320 00:17:53,640 --> 00:17:56,100 is this one here highlighted in yellow. 321 00:17:56,100 --> 00:18:00,570 Since we now have a lower weight edge into V prime, 322 00:18:00,570 --> 00:18:04,883 which is ac, which this one here. 323 00:18:06,660 --> 00:18:09,480 We had this one here, which was of weight seven, 324 00:18:09,480 --> 00:18:12,110 but now that we've added a to V prime, 325 00:18:12,110 --> 00:18:14,250 now we have this other lower weight edge, 326 00:18:14,250 --> 00:18:16,020 which is represented here. 327 00:18:16,020 --> 00:18:19,720 And so we update that table on the right. 328 00:18:19,720 --> 00:18:24,710 So now we have a four here where before we had c seven. 329 00:18:27,480 --> 00:18:31,663 So, next step, do the same thing again. 330 00:18:32,920 --> 00:18:37,380 What's the lowest weight edge into V prime? 331 00:18:37,380 --> 00:18:42,380 It's this one here with weight two, that's this edge here. 332 00:18:44,370 --> 00:18:46,950 So we're gonna add that edge. 333 00:18:46,950 --> 00:18:49,610 And now we add h to V prime 334 00:18:49,610 --> 00:18:51,563 and now we need to update that table. 335 00:18:52,630 --> 00:18:54,910 So we're gonna find that this needs 336 00:18:54,910 --> 00:18:57,860 to be updated now, all right? 337 00:18:57,860 --> 00:19:00,370 And so the entry for c doesn't change 338 00:19:00,370 --> 00:19:03,390 but the entry for d does change from b 339 00:19:03,390 --> 00:19:06,980 with weight three to h with weight two here. 340 00:19:06,980 --> 00:19:09,650 So we no longer need the entry for h, 341 00:19:09,650 --> 00:19:12,570 so we'll just erase that. 342 00:19:12,570 --> 00:19:16,100 You wouldn't erase it in practice but for the demonstration, 343 00:19:16,100 --> 00:19:19,500 it's easier to read table if we exclude values 344 00:19:19,500 --> 00:19:20,800 that are no longer needed. 345 00:19:22,250 --> 00:19:23,470 So what's next? 346 00:19:23,470 --> 00:19:26,760 The table tells us to add d. 347 00:19:26,760 --> 00:19:29,563 So, that's the minimum weight in the table. 348 00:19:31,040 --> 00:19:36,040 We add d, we add this edge dh to E prime. 349 00:19:37,600 --> 00:19:42,430 We add d to V prime, and now we need to update the table. 350 00:19:42,430 --> 00:19:44,860 Now the entry for c needs to change. 351 00:19:44,860 --> 00:19:47,027 It was a with a weight of four 352 00:19:47,027 --> 00:19:51,670 and now it becomes d with a weight of two, okay? 353 00:19:51,670 --> 00:19:53,773 So, we update the table. 354 00:19:55,930 --> 00:19:58,270 And we don't need the entry for d anymore, 355 00:19:58,270 --> 00:19:59,503 so we can kill that. 356 00:20:01,970 --> 00:20:03,580 The entry for j is unchanged, 357 00:20:03,580 --> 00:20:08,580 so we see now that the next choice is c 358 00:20:09,030 --> 00:20:13,060 that has the, this edge here. 359 00:20:13,060 --> 00:20:14,163 No, that's not right. 360 00:20:15,340 --> 00:20:18,790 That's this edge here, my mistake, okay? 361 00:20:18,790 --> 00:20:23,790 So this is the edge from c to d, has a weight of two. 362 00:20:24,110 --> 00:20:25,363 So we're gonna add that. 363 00:20:26,220 --> 00:20:30,550 We add the edge cd to E prime. 364 00:20:30,550 --> 00:20:35,550 We add c to V prime, and now we update the table. 365 00:20:35,780 --> 00:20:37,530 We no longer need this entry, 366 00:20:37,530 --> 00:20:40,893 so we can delete that or just strike it out. 367 00:20:42,140 --> 00:20:45,080 And the entry for j is unchanged, this doesn't change. 368 00:20:45,080 --> 00:20:47,100 There's no lower weight. 369 00:20:47,100 --> 00:20:49,570 So we're just gonna leave it as it is. 370 00:20:49,570 --> 00:20:51,310 And so now we only have one choice, 371 00:20:51,310 --> 00:20:52,663 it's easy to finish up. 372 00:20:53,810 --> 00:20:58,810 We choose this edge that is weight three, connecting j to a 373 00:21:01,570 --> 00:21:06,570 and we add the edge and we add j to V, and now we're done. 374 00:21:07,400 --> 00:21:09,950 And so there's our minimum spanning tree. 375 00:21:09,950 --> 00:21:14,740 And so this is one way of implementing Prim's algorithm 376 00:21:14,740 --> 00:21:15,940 in a little more detail. 377 00:21:17,780 --> 00:21:20,840 So, is Prim's algorithm greedy? 378 00:21:20,840 --> 00:21:23,850 Yes, it is greedy, okay? 379 00:21:23,850 --> 00:21:27,130 Because it's always finding the minimum weight edge 380 00:21:27,130 --> 00:21:29,940 and adding it and it never goes back 381 00:21:29,940 --> 00:21:31,640 and reconsiders that edge. 382 00:21:31,640 --> 00:21:35,090 Once it goes into the solution, it's there for good. 383 00:21:35,090 --> 00:21:36,540 So that's a greedy algorithm. 384 00:21:37,410 --> 00:21:39,450 What's the worst case complexity? 385 00:21:39,450 --> 00:21:43,490 Well, it's big O of the cardinality of V squared. 386 00:21:43,490 --> 00:21:46,520 We have V minus one edges that we need to add. 387 00:21:46,520 --> 00:21:48,710 And in the inner loop, we have to iterate 388 00:21:48,710 --> 00:21:52,040 through all the nodes not in V prime 389 00:21:52,040 --> 00:21:56,100 to recalculate the lowest weight edges to V prime. 390 00:21:56,100 --> 00:21:59,390 So yeah, that number gets smaller as we iterate 391 00:21:59,390 --> 00:22:03,040 but we're still talking on the order of big O 392 00:22:03,040 --> 00:22:04,713 of the cardinality of V squared. 393 00:22:06,250 --> 00:22:09,163 That is, of course, if we use the adjacency matrix. 394 00:22:10,520 --> 00:22:14,210 There is an implementation using min heap for fetching 395 00:22:14,210 --> 00:22:15,410 the lowest weight edges. 396 00:22:15,410 --> 00:22:17,570 And if we use min heap, 397 00:22:17,570 --> 00:22:22,570 then we get a runtime complexity of big O of E times log 398 00:22:23,890 --> 00:22:27,030 of the cardinality of V, and this is a mistake. 399 00:22:27,030 --> 00:22:29,703 This should say cardinality of E, forgive me. 400 00:22:31,860 --> 00:22:34,370 So, the adjacency matrix is best 401 00:22:34,370 --> 00:22:39,370 if the graph is dense, if there are a lot of edges. 402 00:22:41,970 --> 00:22:45,230 If there's a high ratio of the edges to the nodes. 403 00:22:45,230 --> 00:22:48,110 And the min heap is best if the graph is sparse, 404 00:22:48,110 --> 00:22:51,663 that's when there's a low ratio of edges to nodes. 405 00:22:52,650 --> 00:22:56,260 But either one will work and they produce similar results. 406 00:22:56,260 --> 00:22:58,820 So that's Prim's algorithm 407 00:22:58,820 --> 00:23:01,450 for finding the minimum spanning tree in a graph. 408 00:23:01,450 --> 00:23:06,450 And in the next video, we'll look at alternative approach 409 00:23:06,450 --> 00:23:08,100 called Kruskal's algorithm. 410 00:23:08,100 --> 00:23:09,050 That's all for now.