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.