Minimum Spanning Trees in JavaScript

Now that we’ve explored graphs and their basic algorithms, we’re going to add aonther dimension to the vertices: weight. We’ve already programmed them into our Vertex class, but now we’re going to explore how our algorithms must change when weight becomes a factor when traveling on an edge from one vertex to the next.

This article is part of the Data Structures and Algorithms Series following the course The Analysis of Algorithms. If you missed the previous article, check that out first as well as a copy of The Algorithm Design Manual.

Answers to the previous Daily Problem

Your job is to arrange n ill-behaved children in a straight line, facing front. You are given a list of m statements of the form “i hates j”. If i hates j, then you do not want put i somewhere behind j, because then i is capable of throwing something at j.

We need to order kids in a line such that they don’t rip each other to shreds. Seems reasonable.

(a) Give an algorithm that orders the line, (or says that it is not possible) in O(m + n) time.

So what we want is a valid list out of a graph relationship where all of the students are facing forward (hint, hint: a directed acyclic graph). Solving a DAG to produce a valid list? This sounds exactly what a topological sort would provide.

Recall that topological sort on top of DFS is just including an extra stack, and that runtime is O(V+E). Here we mention n as the vertices and m as the edge relationships between any two children, so we can indeed say that our DFS topological sort will run in O(m + n) time.

(b) Suppose instead you want to arrange the children in rows such that if i hates j, then i must be in a lower numbered row than j. Give an efficient algorithm to find the minimum number of rows needed, if it is possible.

Since we’re dealing with rows (or going across), this lends itself to being solved with BFS instead of DFS. Tracking the depth within the tree as you traverse it, and once you find the last tree node, you now know the maximum height of the tree, which therefore indicates the number of rows that are needed.

Definition of a minimum spanning tree

A spanning tree for a graph is the set of edges that connect to all vertices in the graph. In other words, it’s the edges that make the graph fully connected. So you might think the minimum spanning tree is the minimum set of edges that connect a graph completely. In actuality, the minimum spanning tree (MST) is the set of edges that connect all vertices in a graph with the smallest weight possible.

When are MSTs useful? Any time you need to find the minimum-weighted path on a route, such as the shortest path on a road trip (we’ll learn more about shortest path problems in the next article).

Variants

There are a few variations of spanning trees that are similar to MSTs that are also worth noting:

1. Maximum spanning trees. As you can imagine, this looks for the path with the heaviest edges to connect the graph instead of the lightest (I’d imagine this would be great for something like Settlers of Catan). You’ll see Prim’s algorithm ahead for MSTs; to handle maximum spanning trees, just negate the weights to find the heaviest/longest path.
2. Minimum product spanning trees. Instead of finding the edge weights with the lowest sum, you want to find the lowest product. To do this, you just add up the logarithms of the weights of the edges instead of just the weights. Why would we do this? Likely for alternative routes that have lower absolute values, sort of like how you can choose the shortest route in time as opposed tot he shortest route in distance.
3. Minimum bottleneck spanning trees. This just is another condition of MSTs that we ensure the maximum edge weight is minimized. We can take care of this with Kruskal’s algorithm a bit later.
4. Steiner trees. A minimum spanning tree with intermediate midpoints. Wiring routing and circuits deal with this, so if you do any hardware engineering, you might encounter a Steiner tree.
5. Low-degree spanning tree. If you’re visiting all vertices using a Hamiltonian path you might construct a low-degree spanning tree, but you can’t solve it with the algorithms we’re about to show you. The low-degree part just ensures that we aren’t visiting hub nodes with a lot of outbound routes, like when you reach a rotary with a lot of exits.

Prim’s Algorithm for MSTs

Prim’s algorithm is one way to find a minimum spanning tree by starting with a vertex and progressively choosing the best neighboring vertex without regard to the entire structure of the graph. When you do something like choosing the minimum edge weight for a local set of edges without regard to finding the absolute minimum to the whole structure, that is called a greedy algorithm.

class Graph {
  // rest of structure from previous articles
  let ADDED, DISTANCES, PARENTS;

  prim(startVertex) {
    ADDED = new Array(this.vertices.length).fill(false);
    DISTANCES = new Array(this.vertices.length).fill(Number.POSITIVE_INFINITY);
    PARENTS = new Array(this.vertices.length).fill(-1);

    DISTANCES[startVertex] = 0;
    let currentVertex = startVertex, currentEdge;

    while (!ADDED[currentVertex]) {
      ADDED[currentVertex] = true;
      currentEdge = this.connections[currentVertex];

      while (currentEdge) {
        let nextVertex = currentEdge.adjacencyInfo;
        let weight = currentEdge.weight;

        if (DISTANCES[nextVertex] > weight && !ADDED[nextVertex]) {
          DISTANCES[nextVertex] = weight;
          PARENTS[nextVertex] = currentVertex;
        }

        currentEdge = currentEdge.nextVertex;
      }

      currentVertex = 1;
      let bestCurrentDistance = Number.POSITIVE_INFINITY;

      for (let i = 0; i < this.vertices.length; i++) {
        if (!ADDED[i] && bestCurrentDistance > DISTANCES[i]) {
          bestCurrentDistance = DISTANCES[i];
          currentVertex = i;
        }
      }
    }
  }
}

Using our Big O notation tricks for calculating the runtime, we can see that we need to iterate n times for all vertices which sweep across only the minimum m edges (which is less than or equal to n) to connect the whole graph, which leaves our runtime for Prim’s to be O(n^2). Using a priority queue can drop this time down even further to O(m + (n log n)) (note: can you figure out why?).

Kruskal’s Algorithm for MSTs

An alternative greedy algorithm to Prim’s is called Kruskal’s Algorithm, which just doesn’t have a starting vertex. It instead builds up connections via components of vertices and, for sparse graphs, can run faster than Prim’s, provided it uses the right data structure.

class Graph {
  let EDGE_PAIRS = new Array(MAX_VERTICES);

  kruskal() {
    let counter;
    let set = new SetUnion(this.vertices);

    this.toEdgeArray(); // using EDGE_PAIRS
    // sort by weight rather than a standard array value
    quicksort(this.EDGE_PAIRS, this.connections.length, this.EDGE_PAIRS.length);

    for (let i = 0; i <= this.connections; i++) {
      if (!sameComponent(set, EDGE_PAIRS[i].startVertex, EDGE_PAIRS[i].endVertex)) {
        console.log(`edge ${EDGE_PAIRS[i].startVertex},${EDGE_PAIRS[i].endVertex} in MST`);
        set.union(EDGE_PAIRS[i].startVertex, EDGE_PAIRS[i].endVertex);
      }
    }
  }
}

To summarize the two:

1. Are you trying to find an MST in a sparse graph? Use Kruskal’s Algorithm.
2. Are you trying to find an MST in a dense graph? Use Prim’s Algorithm.

As you can see, the data structure for fast search of a sparse graph requires something called the Union-Finding data structure, which we will discuss next.

Union Finding

When we’re dealing with MSTs, we’re thinking about navigating the graph in the shortest/quickest path possible. But to find the best way around our graph, we can’t just look at our immediate neighbors to determine the best way forward. It’s often helpful to cluster whole “neighborhoods” of nodes together to form a better picture about where we should move next.

As we say with Kruskal’s Algorithm, one way to do that is by partitioning the graph into distinct sets and sorting against that. To make that happen efficiently, we utilized a SetUnion data structure which we will outline below. Set unions have two primary functions:

1. areSame() to determine if two vertices are in the same partition
2. merge() to merge two partitions together

Whereas traditional nodes in a tree focus on moving down the tree and keeping track of children, set unions have nodes who focus on moving up by keeping a close watch on their parents. So if you have a graph of 3 groups like so:

0    3    6
|   / \
1  2   4
        \
         5

You could represent the array of parents as [0, 0, 3, 3, 3, 4, 6]. A more complete example in JavaScript follows:

class SetUnion {
  constructor(length) {
    this.length = length;
    this.parents = [...Array(length).keys()];
    this.elements = Array(length).fill(1);
  }

  find(element) {
    if (this.elements[element] === element) return element;
    return this.find(this.parents[element]);
  }

  areSame(set1, set2) {
    return this.find(set1) == this.find(set2);
  }

  merge(set1, set2) {
    const root1 = this.find(set1);
    const root2 = this.find(set2);

    if (root1 === root2) return "already same set";
    if (this.elements[root1] >= this.elements[root2]) {
      this.elements[root1] += this.elements[root2];
      this.parents[root2] = root1;
    } else {
      this.elements[root2] += this.elements[root1];
      this.parents[root1] = root2;
    }
  }
}

As you can see from above, areSame() and merge() rely on find() to recursively traverse the relavent subtree in the graph for the parent that matches. We know from earlier that recursive partitioning takes O(log n) time and so we can conclude that in the worst-case any set union operation will take logarithmic time, which is a great guarantee for Kruskal’s Algorithm.

Now that we’ve explored a few algorithms for route finding, let’s put some of this knowledge into practice with the Daily Problem.

Onto the next Daily Problem

Suppose we are given the minimum spanning tree T of a given graph G (with n vertices and m edges) and a new edge e = (u, v) of weight w that we will add to G. Give an efficient algorithm to find the minimum spanning tree of the graph G + e. Your algorithm should run in O(n) time to receive full credit.

More problems to practice on

To get even more practice with graph searching and path finding, here are the other homework problems to go along with this article:

1. Implement an algorithm to print out the connected components in an undirected graph.
2. Problem 6-4.
3. Problem 6-5.
4. Problem 6-9.