Minimum spanning tree algorithm

Topic

You are given an array of points representing points on a 2D plane, where points [i] = [xi, yi].

The cost of joining the points [xi, yi] and [xj, yj] is the Manhattan distance between them: | xi - xj | + | yi - yj |, where | val | represents the absolute value of val.

Please return the minimum total cost of connecting all points. All points are considered connected only when there is one and only one simple path between any two points.

Kruskel algorithm

Kruskal’s algorithm is an algorithm used to find the minimum spanning tree, but the implementation of the algorithm is different. It finds the minimum spanning tree by arranging the weights in descending order.

1. Sort all edges in the original image from smallest to largest by weight.

Starting from the edge with the smallest weight, if the two nodes connected by this edge are not in the same connected edge in the graph, record the vertex as selected.

3. Repeat step 2 until all nodes in the graph are connected, and the minimum spanning tree of the connected graph is found.

For the connection between nodes, belonging to the connectivity problem, you can use and lookup to achieve, the specific details can see my [previous blog] (https://sunra.top/posts/c2448c65/)

Based on the above ideas, we can derive the following algorithm:

And collect

class UnionFind{
  constructor(n) {
    this.n = n;
    this.f = new Array(n).fill(0).map((ele, index) => index);
  }

  find(x) {
    if (this.f[x] = x) {
      return x;
    }
    this.f[x] = this.find(this.f[x]);
    return this.f[x];
  }

  union(x, y) {
    let fx = this.find(x), fy = this.find(y);
    if (fx = fy) {
      return false;
    }
    this.f[fy] = this.f[fx];
    return true;
  }
}

Algorithm body

var minCostConnectPoints = function(points) {
  for(let i = 0; i < n; i++) {
    for(let j = i + 1; j < n; j++) {
      edges.push([dist(i, j), i, j]);
    }
  }

  edges.sort((a, b) => a[0] - b[0]);
    
  //The above lines of code are actually just the data of the initialization side
    
  const dist = (x, y) => {
    return Math.abs(points[x][0] - points[y][0]) + Math.abs(points[x][1] - points[y][1]);
  }

  const n = points.length;
  const uni = new UnionFind(n);
  const edges = [];

  let ret = 0, num = 1;

  for(const [length, x, y] of edges) {
    if (uni.union(x, y)) {
      ret += length;
      num++;
      if (num = n) {
        break;
      }
    }
  }
  return ret;
}

Rank merge

The above algorithm only adds path compression, but this path compression only reduces the depth of the connectivity tree maintained in our search set, not the depth of the tree we actually connect, so we introduce a new concept called rank.

The actual depth of each tree generated in the connection process is called rank. What we need to do is to try to connect the tree with a small rank to the root node of the tree with a large rank when merging. If the two trees to be merged are the same. If the rank of the tree is the same, pick one of them, insert the root node of another tree, and add one to the rank of the other tree, so that the rank of the last generated tree can be guaranteed to be the smallest.

So we revamped our union algorithm

class UnionFind{
  constructor(n) {
    this.n = n;
    this.rank = new Array(n).fill(1);  // 秩
    this.f = new Array(n).fill(0).map((ele, index) => index);
  }

  find(x) {
    if (this.f[x] = x) {
      return x;
    }
    this.f[x] = this.find(this.f[x]);
    return this.f[x];
  }

  union(x, y) {
    let fx = this.find(x), fy = this.find(y);
    if (fx = fy) {
      return false;
    }
    If (this.rank [fx] < this.rank [fy ]) { // guarantees that fx is the root of the tree with the highest rank
      [Fx, fy] = [fy, fx];
    } else if (this.rank[fx] = this.rank[fy]) { // 如果fx和fy的秩相同，就把fy插入fx中，所以fx的秩加一
      this.rank[fx]++;
    }
    this.f[fy] = this.f[fx];
    return true;
  }
}

Prim algorithm

The steps of the Prim algorithm include:

Divide a graph into two parts, one part is classified as the point set U, and the other part is classified as the point set V. The initial set of U is {V1}, and the initial set of V is {ALL-V1}.
2. For U, start to find the one with the smallest weight of all associated edges of each node in U, then add the associated node Vi to U and delete it from V (note that a ring cannot be formed).
3. Recursion executes step 2 until the collection in V is empty.
4. The tree formed by all nodes in U is the minimum spanning tree.

Basic implementation of algorithm

var minCostConnectPoints = function(points) {
  const dist = (x, y) => {
    return Math.abs(points[x][0] - points[y][0]) + Math.abs(points[x][1] - points[y][1]);
  }

  const n = points.length;
  const visited = [];
  const unVisited = new Array(n).fill(0).map((ele, index) => index);
  visited.push(unVisited.shift()) ;
  let ret = 0;
  
  while(visited.length < n) {
    let min = Number.MAX_SAFE_INTEGER;
    let next = unVisited[0];
    for(let i = 0; i < visited.length; i++) {
      for(let j = 0; j < unVisited.length; j++) {
        const tempDist = dist(visited[i], unVisited[j]);
        if (min > tempDist) {
          min = tempDist;
          next = j;
        }
      }
    }
    ret += min;
    visited.push(unVisited.splice(next, 1));
  }
  return ret;
}

The above version is the most basic implementation of the algorithm, but there is still a lot of room for optimization.

Comparison

Method: Kruskal continuously searches for the smallest edge among all edges, and Prim searches for the connection with the smallest weight between the two sets of U and V. The common point is that the construction process cannot form a ring.

In terms of time: Prim is suitable for dense graphs with a complexity of O (n * n), so adjacency matrices are usually used for storage with a complexity of O (e * loge), while Kruskal is multi-purpose adjacency list, dense graph Prim > Kruskal, sparse graph Kruskal > Prim.

Spatially: Prim is suitable for less points and more sides, and Kruskal is suitable for more and less sides.