The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).
Correctness of Kruskal's Algorithm
Loading...
From the course by Stanford University
Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
686 ratings
From the lesson
Week 2
Kruskal's MST algorithm and applications to clustering; advanced union-find (optional).
Meet the Instructors
Tim RoughgardenProfessor
Computer Science
So this algorithm will prove the correctness of Kruskal's minimum cost
spanning tree algorithm. So to prove this correctness theorem,
let's fix an arbitrary connected input graph G.
And let's let T star denote the output of Kruskal's algorithm when we invoke it on
this input graph. So, just like with our high level proof
plan for Prim's algorithm, we're going to proceed in three steps.
We're first going to just establish the more modest goal, the Kruskal's algorithm
outputs a spanning tree. We're not going to make any initial
claims about optimality. So those are the first two steps, one to
argue there's no cycles, one to argue that the output's connected.
And then, in the third step, relying on the cut property.
We'll say, it's not just a spanning tree, it's actually the minimum cost spanning
tree. For this proof, I am going to assume
you're familiar with the machinery we developed to, to prove Prim's algorithm
is correct. So the first step of the proof is going
to be very easy. So one important property of a Spanish
[INAUDIBLE] there's no cycles and it's quite obvious looking at the pseudocode
of Kruskal's algorithm that its not going to produce any cycles.
Every edge that creates a cycle is explicitly excluded from the output.
What's a little less obvious is that as long as the, input graph is connected,
then Kruskal's algorithm will output a connected sub-graph.
And therefore a spanning tree. So to argue the output's connected, we're
going to have two sub-parts of the proof. The first thing I want you to do is
recall what we call the empty cut lemma. So this was a way of talking about when a
graph is disconnected or equivalently when a graph is connected.
And you'll recall a graph is connected if and only if for every cut there's at
least one crossing edge. So to prove this second step of this
proof that T star is connected we just have to prove that for every single cut
it had at least one edge crossing that cut.
So, that's what we're going to show. To get started let's fix an arbitrary cut
A, B. Using the assumption the input graph is
connected, it certainly contains at least one edge that crosses this cut.
The question is whether or not T star contains a crossing edge but certainly
the original graph G contains a crossing edge.
So, here's the key point of the argument. Kruskal's algorithm, by definition, it
makes a single scan through all of the edges.
That is, it considers every edge of the original input graph exactly once.
So, what I want you to do is, I want you to think about this cut A, B which has at
least one edge of G crossing. And I want you to fast forward Kruskals
algorithm until the moment that it first considers an edge crossing this cut AB.
The key claim is that this first edge seen by Kruskal's algorithm, is
definitely be, going to be included in the final output, T star.
So why is this true? Well, let me remind you of the lonely cut
corollary. The lonely cut corollary says that if an
edge is the sole edge crossing a cut, if it's lonely in a cut, then it cannot
participate in any cycle, right?
If it was in a cycle, that cycle would loop back around and cross the cut a
second time. Now, what does that have to do with the
picture here? Well, if this is the first edge that
Kruskal sees crossing this cut, then certainly the tree so far T star contains
nothing crossing this cut, right? It hasn't even seen anything crossing
this cut yet. So at the moment it encounters the first
edge, there's no way including that first edge will create a cycle because that
first edge is going to be lonely in this cut AB.
So again summarising, the first edge crossing a cut is guaranteed to be chosen
by a cross because the algorithmic cannot create a cycle.
That's why there's at least one edge of Kruskal's output crossing this particular
cut AB. Since AB was arbitrary, all edges,
all cuts have some edge of T star crossing them, that's why T star is
connected. So this completes the part of the proof
where we argue that Kruskal's algorithm outputs a spanning tree.
Now we have to move on and argue that it's actually a minimum cost spanning
tree. We're going to argue this in the same way
as we did for Prim's algorithm. We're going to argue that every edge ever
selected by Kruskal's algorithm is justified by the cut property.
Satisfies the hypotheses of the cut property.
Recall from our correctness proof for Prim's Algorithm,
this is enough to argue correctness. That the output is a minimum cost
spanning tree, right?
An edge justified by the cut properties, not a mistake.
It's got to belong to the minimum cost spanning tree.
If you have an algorithm that outputs a spanning tree, and it never made a
mistake, that's got to be the minimum cost spanning tree.
And that's going to be the case for Kruskal.
Now this statement was easy to prove for Prim's algorithm and that's because the
definition of Prim's algorithm, it selects edges based on being the cheapest
in some cut. So it's tailor made for the application
of the cut property. Not so for Kruskal's algorithm.
If you look at the pseudocode, nowhere does the pseudocode discuss taking cheap
edges across cuts. So we have to show that Kruskal's
algorithm in effect is inadvertently at every edge picking the cheapest edge
crossing some cut. And we actually have to exhibit what that
cut is in our proof of correctness. So, that's what we have to do here.
So to argue that, let's just sort of freeze Kruskal's algorithm at some
arbitrary iteration, where it adds a new edge.
We need to show that this edge is justified by the cut property.
So, maybe this edge has end points U and V, and let's let capital T denote the
current value of the edges selected by the algorithm so far.
So let's think about what this state of the world looks like, at a, sort of,
intermediate iteration of Kruskal's algorithm.
So Kruskal's algorithm maintains the invariant there's no cycles but remember
it doesn't maintain any invariant of the current edges forming a connected set so
in general in an intermediate iteration of Kruskal's algorithm, you've got a
bunch of pieces, a bunch of little mini trees floating around the graph.
Connect the components if you like, with respect to the current edge shed, capital
T. And there can be some, you know, isolated
vertices floating around as well. What more can we say?
Well, if the current edge has endpoints U and V and Kruskal is deciding to add this
edge UV to the current set capital T, we certainly know that capital T has no path
between U and V, right?
If it did have a path, then this new edge would create a cycle, then Kruskal would
skip the edge. Since it isn't skipping the edge, U and V
are currently in different pieces. They're in different components with
respect to the current edge set. Now remember, ultimately, if we're going
to apply the cut property, we have to somehow exhibit some cut from somewhere,
justifying this particular edge. So here's where we get the cut from, and
it's going to be a very similar argument to when we proved the empty cut limit
characterizing disconnectedness in terms of empty cuts.
We're going to say look, with respect to the tree edges we have so far, with
respect to the green edges, there's no path from U to V.
That means we can find a cut such that U is on one side, V is on the other side,
and there's no edges crossing the cut. So, here's the cool part of the proof.
And this is also the part where we actually use the fact that Kruskal was a
greedy algorithm. That it considers the edges from cheapest
to most expensive. Notice that we haven't actually used that
fact up to this point and we better use that fact.
So, the claim is that not only is this edge we're adding UV, not only does it
cross this cut AB, but actually it's the cheapest edge crossing the cut.
Nothing from the original input graph G that crosses it can be cheaper.
So why is that true? Well, let's remember how we wrapped up
the previous slide when we were arguing that the output of Kruskal's algorithm is
connected. What did we argue?
We said, well, fix any cut you like. Any cut of the graph.
And freeze Kruskal's algorithm the very first time it considers some edge
crossing that cut. We noticed that Kruskal's algorithm is
guaranteed to include that first edge crossing the cut in its final solution.
There's no way that, that first edge considered can create a cycle with
respect to the edges already chosen. So, it's not going to trigger the
exclusion criterion in Kruskal's algorithm.
And that edge is going to get picked. So what's the significance about being
the first edge crossing a cut well because of the gradient criterian because
Kruskal considers edges from cheapest and most expensive.
The first edge it encounters crossing a cut is also necessarily the cheapest edge
that's crossing the cut. So here's how we weave these different
strands together to complete the correctness proof.
Alright, so let's remember where we are. We're focusing on a single iteration of
Kruskal's algorithm. It's about to add this edge U, V to the
edges, capital T, that it's chosen in the past.
We've exhibited a cut. A, B with a property that no previously
chosen edges, no edges of capital T cross this cut, and UV is going to be the first
chosen edge crossing this cut. We just argued, that Kruskal's algorithm
is guaranteed to pick the first edge crossing a cut.
So by virtue of their not yet being any chosen edges, crossing the cut AB, it
must be the case that this current edge UV is the first one that's ever been seen
by Kruskal's algorithm that crosses this cut AB.
Now, in being the first edge it's ever seen crossing this cut. It must also be
the cheapest edge of the input graph that crosses this cut.
That is the hypothesis of the cut property.
That is why this edge UV and this current arbitrary iteration is justified by the
cut property.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
