1 00:00:02,490 --> 00:00:03,323 - Wow. 2 00:00:03,323 --> 00:00:06,650 The penultimate week of the semester, 3 00:00:06,650 --> 00:00:10,570 week 14 of CS 124 Online, 4 00:00:10,570 --> 00:00:13,623 Data Structures and Algorithms. 5 00:00:14,480 --> 00:00:18,200 Last week, we saw how to find the shortest paths 6 00:00:18,200 --> 00:00:20,880 through a graph between some starting node 7 00:00:20,880 --> 00:00:22,760 and all other nodes in the graph. 8 00:00:22,760 --> 00:00:25,030 And we looked at two algorithms for doing this, 9 00:00:25,030 --> 00:00:27,303 Dijkstra's algorithm and Bellman-Ford. 10 00:00:28,690 --> 00:00:30,500 We also learned about network flows 11 00:00:30,500 --> 00:00:33,610 and how to find the maximum flow supported by a network 12 00:00:33,610 --> 00:00:35,640 from some source to some sync. 13 00:00:35,640 --> 00:00:38,530 And for this, we saw the Ford-Fulkerson algorithm 14 00:00:38,530 --> 00:00:41,010 and we briefly mentioned the Edmonds-Karp algorithm 15 00:00:41,010 --> 00:00:43,670 which is a more specifically defined implementation 16 00:00:43,670 --> 00:00:44,723 of Ford-Fulkerson. 17 00:00:46,280 --> 00:00:48,880 This week, we've got some more really cool stuff. 18 00:00:48,880 --> 00:00:52,160 We'll see how to find what's called a minimum spanning tree 19 00:00:52,160 --> 00:00:52,993 in a graph. 20 00:00:54,050 --> 00:00:55,990 Now, what is a minimum spanning tree? 21 00:00:55,990 --> 00:01:00,730 Well, in a trivial case of a graph which is a tree, 22 00:01:00,730 --> 00:01:03,630 such a tree is a minimum spanning tree of itself, 23 00:01:03,630 --> 00:01:05,370 but that's kind of silly. 24 00:01:05,370 --> 00:01:08,980 What we're interested in is a graph that's not a tree. 25 00:01:08,980 --> 00:01:11,200 That is, a graph that contains cycles. 26 00:01:11,200 --> 00:01:13,650 And when a graph contains cycles, 27 00:01:13,650 --> 00:01:15,980 that means that for at least some pairs of nodes 28 00:01:15,980 --> 00:01:19,430 in the graph, there's more than one path between them. 29 00:01:19,430 --> 00:01:23,350 And let's say we wanted to find a structure within the graph 30 00:01:23,350 --> 00:01:25,530 that connected all the nodes in the graph 31 00:01:25,530 --> 00:01:27,190 without forming any cycles. 32 00:01:27,190 --> 00:01:30,373 So between any pair of nodes, there's exactly one path. 33 00:01:31,270 --> 00:01:33,030 That's what we call a spanning tree. 34 00:01:33,030 --> 00:01:35,710 Since it spans all the nodes in the graph, 35 00:01:35,710 --> 00:01:37,423 and well, it's a tree. 36 00:01:39,650 --> 00:01:42,570 Now the problem of finding a minimum spanning tree 37 00:01:42,570 --> 00:01:45,130 arises when we have a weighted graph 38 00:01:45,130 --> 00:01:48,300 and we want to find the spanning tree for which the sum 39 00:01:48,300 --> 00:01:52,200 of all the weights of all of its edges is minimal. 40 00:01:52,200 --> 00:01:53,710 And there are a lot of applications 41 00:01:53,710 --> 00:01:55,320 for minimum spanning trees. 42 00:01:55,320 --> 00:01:59,270 And we'll go into that a little bit in the video lectures. 43 00:01:59,270 --> 00:02:01,820 So being able to find them effectively 44 00:02:01,820 --> 00:02:03,173 is kind of a big deal. 45 00:02:04,520 --> 00:02:08,150 I think I'm not sure, but I think the first application 46 00:02:08,150 --> 00:02:09,760 of minimum spanning trees 47 00:02:09,760 --> 00:02:13,253 arose from the need for electric power distribution. 48 00:02:14,210 --> 00:02:16,270 You know, we hear about electric grids in the news 49 00:02:16,270 --> 00:02:17,300 when there's a blackout, 50 00:02:17,300 --> 00:02:20,270 notably in the power failures in Texas 51 00:02:20,270 --> 00:02:23,070 that we just saw after the severe winter storm 52 00:02:23,070 --> 00:02:24,313 of February, 2021. 53 00:02:26,040 --> 00:02:29,080 Now back when the first power grids were being designed, 54 00:02:29,080 --> 00:02:32,400 engineers wanted to know how best to connect cities, towns 55 00:02:32,400 --> 00:02:35,420 and villages with the power generation plants 56 00:02:35,420 --> 00:02:37,010 and distribution facilities 57 00:02:37,010 --> 00:02:39,610 with the shortest amount of cable 58 00:02:39,610 --> 00:02:42,200 thus reducing the construction costs 59 00:02:42,200 --> 00:02:43,963 and the transmission loss. 60 00:02:44,890 --> 00:02:48,170 So given some network of cities, towns and villages 61 00:02:48,170 --> 00:02:50,520 and power plants and distribution centers, 62 00:02:50,520 --> 00:02:51,940 they had this graph 63 00:02:51,940 --> 00:02:54,350 and they wanted to find the minimum weight tree 64 00:02:54,350 --> 00:02:56,940 that spanned all of these locations 65 00:02:56,940 --> 00:02:59,763 providing electric service to each point. 66 00:03:01,420 --> 00:03:04,930 So here this week, we'll look at two algorithms 67 00:03:04,930 --> 00:03:07,670 for finding minimal spanning trees in a graph. 68 00:03:07,670 --> 00:03:11,430 We'll see Prim's algorithm and Kruskal's algorithm. 69 00:03:11,430 --> 00:03:13,060 Both of these solve the problem 70 00:03:13,060 --> 00:03:15,170 of finding a minimum spanning tree 71 00:03:15,170 --> 00:03:17,063 but they do so in different ways. 72 00:03:18,230 --> 00:03:19,860 And what's also of interest here 73 00:03:19,860 --> 00:03:22,010 is that we'll see that, 74 00:03:22,010 --> 00:03:26,410 we'll see this combination of methods and data structures. 75 00:03:26,410 --> 00:03:29,240 Data structures that we've seen earlier in the course 76 00:03:29,240 --> 00:03:32,730 to facilitate an efficient implementation. 77 00:03:32,730 --> 00:03:35,670 For example, Kruskal's algorithm can be implemented 78 00:03:35,670 --> 00:03:38,580 using a min-heap to order the edges 79 00:03:38,580 --> 00:03:40,300 and the union find approach 80 00:03:40,300 --> 00:03:43,793 of disjoint sets to detect cycles and combine edges. 81 00:03:44,800 --> 00:03:47,230 So now we've got all these pieces 82 00:03:47,230 --> 00:03:49,410 and we're starting to put them together 83 00:03:49,410 --> 00:03:50,943 in interesting ways. 84 00:03:51,900 --> 00:03:53,250 And at the end of the week, 85 00:03:54,610 --> 00:03:55,840 we're gonna have another quiz. 86 00:03:55,840 --> 00:03:57,310 It'll cover this week's material 87 00:03:57,310 --> 00:04:00,210 and some additional material we covered from last week. 88 00:04:00,210 --> 00:04:03,760 So this week's quiz will cover shortest paths, 89 00:04:03,760 --> 00:04:07,150 Dijkstra's algorithm, the Bellman-Ford algorithm, 90 00:04:07,150 --> 00:04:09,700 network flows and the Ford-Fulkerson algorithm, 91 00:04:09,700 --> 00:04:12,820 and this week's material which is minimum spanning trees 92 00:04:12,820 --> 00:04:14,970 and the algorithms due to Prim and Kruskal. 93 00:04:16,130 --> 00:04:17,900 So that's all for now 94 00:04:17,900 --> 00:04:20,620 and I'll see you on our Yellowdig discussion board. 95 00:04:20,620 --> 00:04:21,763 Have fun, thanks.