Weighted Graphs and the Minimum Spanning Tree

Moving on from simple graphs, one of the things you can do to make things more interesting
is to associate numeric values with the edges, called the weights of those edges. This variation
of a graph is called a weighted graph.

Weighted graphs are extremely useful buggers: many real-world optimization problems ultimately
reduce to some kind of weighted graph problem. A few examples include:

• The traveling salesman problem (TSP): given a set of cities, and information about travel-times
  between pairs of cities, find the shortest route that visits all cities. This is actually an
  incredibly commonly used problem; for example, in large data centers which manage backups,
  a set of backup-restore requests is served by computing the seek time between pairs
  of requests (where seek time includes finding the correct tape, loading it into a drive, and
  scanning to the correct point on tape), and then finding the optimum order in which to fulfill
  the requests by using a TSP algorithm
• Shortest path problem: a subset of the TSP; given a set of cities and information about
  travel-time between cities with direct transportation routes, find the shortest path between
  two cities.
• The minimum spanning tree problem: given a weighted graph, find the spanning tree
  with minimum total edge-weight. Airlines use minimum spanning trees to work out their basic
  route system: flights between hubs are low-cost; other flights have varying prices depending on how many people fly them, what airplanes the airports can support, fuel transport costs, etc. The best
  set of routes is the minimum spanning tree.

Formally, a weighted graph is defined by a triple: (V, E, W), where:

• V is a set of vertices;
• E is a set of edges {v,w} where v,w∈V.
• W is a map from edges to numbers. (Depending on the specifics of a problem,
  the numbers might be restricted to positive numbers, natural numbers,
  integers, ...)

For today, we'll look at the last of those in a bit more detail: finding the minimum spanning tree. This is one of the problems that constantly comes up in infrastructure design - from building layouts, to
network structure to warehouse location. One great example of the use of this is in telecommunications. When AT&T and Sprint were laying fiber optic cable to replace their copper-wire backbone, they
took their primary routing stations, and arranged them in a graph. Then they worked out the cost of
connecting each pair of routing stations by fiber, and applied those costs as edge-weights. Then they
computed the minimum spanning tree of the resulting graph - and that defined the least-expensive
way to lay the fiber for a new backbone.

So let's start by making the definition of the minimum spanning tree problem more precise.

1. Suppose we have a simple graph, G=(V,E). A spanning tree S_G= (V,E') is a subtree (acyclic subgraph) of G, where E'⊆E.
2. If G is a weighted graph G=(V,E,W), then the weight of G = Σ_e∈EW(e) - that is, the sum of the weights of all of the edges in the graph.
3. If G is a weighted graph, then the minimum spanning tree Span(G) is the spanning tree over
   G with minimum weight.

Given that just about every interesting graph problem that we've seen has turned out to be NP-complete, you might expect finding a minimum spanning tree to be NP-complete as well. But graphs are often counterintuitive: things that seem like they should be simple turn out to be very difficult; things that look like they'll be difficult sometimes turn out to be simple. In fact, there's a very simple algorithm which is O(n lg n) where n is the number of edges.

It's called Kruskal's algorithm. And it's a really beautiful algorithm - an extraordinarily clear,
simple, easy way of solving the problem. It's based on what's known as a greedy approach. In a
greedy approach, you aggressively grab the thing that looks best, try it out, and see if it fits.

In Kruskal's algorithm, you greedily grab edges - you always grab the lowest weight edge, and see if it
helps build a spanning tree; if so, you add it, if not you discard it; and you keep doing that until
you have the spanning tree. (From that description, you might think that it's really O(N) in the number of edges - because you consider each edge once. But the edges have to be in sorted order, and sorting the edges is O(N lg N).)

So here's the algorithm more precisely:

FindMST(G=(V,E,W))
   let Result = a set of trees, each consisting of one node from G
   let SortedEdges = sort(E,W)
   for each MinEdge in SortedEdges:
      if MinEdge connects two disconnected trees in Result:
         merge the trees in Result by adding MinEdge
      else:
         discard MinEdge
     end if
   end for

Let's walk through an example. Here's a graph with weighted edges:

Now we'll go through Kruskal's algorithm to generate the MST:

So the final weight of the minimum spanning tree for this graph is 31.