Chapter 7
■
Greed Is Good? prove It!
151
the rest of the graph. In the following,
I expand on these ideas, turning them into two full-fledged greedy algorithms
for finding minimum spanning trees. The first (Kruskal’s) is close to the prototypical greedy algorithm, while the next
(Prim’s) uses the principles of traversal, with the greedy choice added on top.
What About the Rest?
Showing that the first greedy choice is OK isn’t enough. We need to show that the remaining problem is a smaller
instance of the same problem—that our reduction is safe to use inductively. In other words,
we need to establish
optimal substructure. This isn’t too hard (Exercise 7-12), but there’s another approach that’s perhaps even simpler
here: We prove the invariant that our solution is part (a subgraph) of a minimum spanning tree. We keep adding edges
as long as the solution isn’t a spanning tree (that is, as long as there are edges left that won’t form a cycle), so if this
invariant is true, the algorithm must terminate with a full, minimum spanning tree.
So, is the invariant true? Initially, our partial solution is empty,
which is clearly a partial, minimum spanning tree.
Now, assume inductively that we’ve built some partial, minimum spanning tree
T and that we add a safe edge (that is,
one that doesn’t create a cycle and that is the shortest one across some cut). Clearly, the new structure is still a forest
(because we meticulously avoid creating cycles). Also, the reasoning in the previous section still applies: Among the
spanning trees containing
T, the one(s) including this safe edge will be smaller than those that don’t. Because
(by assumption), at least
one of the trees containing T is a minimum spanning tree, at least one of those containing
T and the safe edge will
also be a minimum spanning tree.
Kruskal’s Algorithm
This algorithm is close to the general greedy approach outlined at the beginning of this chapter: Sort the edges and
start picking. Because we’re looking for
short edges, we sort them by increasing length (or weight). The only wrinkle
is how to detect edges that would lead to an invalid solution. The only way to invalidate our
solution would be to add
a cycle, but how can we check for that? A straightforward solution would be to use traversal; every time we consider
an edge (
u,
v), we traverse our tree from
u to see whether there is a path to
v. If there is, we discard it. This seems a bit
wasteful, though;
in the worst case, the traversal check would take linear time in the size of our partial solution.
What else could we do? We
could maintain a set of the nodes in our tree so far, and then for a prospective
edge (
u,
v), we’d see whether both were in the solution. This would mean that sorting the edges is what dominates;
checking each edge could be done in constant time. There’s just one crucial flaw in this plan: It won’t work. It
would
work if we could guarantee that the partial solution was
connected at every step (which is what we’ll be doing in
Prim’s algorithm), but we can’t. So even if two nodes are part of our solution so far,
they may be in different trees, and
connecting them would be perfectly valid. What we need to know is that they aren’t in the
same tree.
Let’s try to solve this by making each node in the solution know which component (tree) it belongs to. We can let
one of the nodes in a component act as a
representative, and then all the nodes in that component could point to that
representative. This leaves the problem of
combining components. If all nodes of the merged component had to point
to the same representative, this combination (or union) would be a linear operation. Can we do better? We could
try; for
example, we
could let each node point to some other node, and we’d follow that chain until we reached the representative
(which would point to itself). Joining would then just be a matter of having one representative point to the other (constant
time). There are no immediate guarantees on how long the chain of references would be, but it’s a first step, at least.
This is what I’ve done in Listing 7-3, using the map C to implement the “pointing.” As you can see, each node
is initially the representative of its own component, and then I repeatedly connect components with new edges,
in sorted order. Note that the way I’ve
implemented this, I’m expecting an undirected graph where each edge is
represented just once (that is, using one of its directions, chosen arbitrarily).
11
As always, I’m assuming that every
node is a key in the graph, though, possibly with an empty weight map (that is, G[u] = {} if u has no out-edges).
11
Going back and forth between this representation and one where you have edges both ways isn’t really hard, but I’ll leave the details
as an exercise for the reader.
