- Wow.
The penultimate week of the semester,
week 14 of CS 124 Online,
Data Structures and Algorithms.
Last week, we saw how to find the shortest paths
through a graph between some starting node
and all other nodes in the graph.
And we looked at two algorithms for doing this,
Dijkstra's algorithm and Bellman-Ford.
We also learned about network flows
and how to find the maximum flow supported by a network
from some source to some sync.
And for this, we saw the Ford-Fulkerson algorithm
and we briefly mentioned the Edmonds-Karp algorithm
which is a more specifically defined implementation
of Ford-Fulkerson.
This week, we've got some more really cool stuff.
We'll see how to find what's called a minimum spanning tree
in a graph.
Now, what is a minimum spanning tree?
Well, in a trivial case of a graph which is a tree,
such a tree is a minimum spanning tree of itself,
but that's kind of silly.
What we're interested in is a graph that's not a tree.
That is, a graph that contains cycles.
And when a graph contains cycles,
that means that for at least some pairs of nodes
in the graph, there's more than one path between them.
And let's say we wanted to find a structure within the graph
that connected all the nodes in the graph
without forming any cycles.
So between any pair of nodes, there's exactly one path.
That's what we call a spanning tree.
Since it spans all the nodes in the graph,
and well, it's a tree.
Now the problem of finding a minimum spanning tree
arises when we have a weighted graph
and we want to find the spanning tree for which the sum
of all the weights of all of its edges is minimal.
And there are a lot of applications
for minimum spanning trees.
And we'll go into that a little bit in the video lectures.
So being able to find them effectively
is kind of a big deal.
I think I'm not sure, but I think the first application
of minimum spanning trees
arose from the need for electric power distribution.
You know, we hear about electric grids in the news
when there's a blackout,
notably in the power failures in Texas
that we just saw after the severe winter storm
of February, 2021.
Now back when the first power grids were being designed,
engineers wanted to know how best to connect cities, towns
and villages with the power generation plants
and distribution facilities
with the shortest amount of cable
thus reducing the construction costs
and the transmission loss.
So given some network of cities, towns and villages
and power plants and distribution centers,
they had this graph
and they wanted to find the minimum weight tree
that spanned all of these locations
providing electric service to each point.
So here this week, we'll look at two algorithms
for finding minimal spanning trees in a graph.
We'll see Prim's algorithm and Kruskal's algorithm.
Both of these solve the problem
of finding a minimum spanning tree
but they do so in different ways.
And what's also of interest here
is that we'll see that,
we'll see this combination of methods and data structures.
Data structures that we've seen earlier in the course
to facilitate an efficient implementation.
For example, Kruskal's algorithm can be implemented
using a min-heap to order the edges
and the union find approach
of disjoint sets to detect cycles and combine edges.
So now we've got all these pieces
and we're starting to put them together
in interesting ways.
And at the end of the week,
we're gonna have another quiz.
It'll cover this week's material
and some additional material we covered from last week.
So this week's quiz will cover shortest paths,
Dijkstra's algorithm, the Bellman-Ford algorithm,
network flows and the Ford-Fulkerson algorithm,
and this week's material which is minimum spanning trees
and the algorithms due to Prim and Kruskal.
So that's all for now
and I'll see you on our Yellowdig discussion board.
Have fun, thanks.