计算最小生成树MST的两种算法

发表于 |

MST(minimum-spanning-tree)算法，用于计算在加权无向连通图中，生成最小权重的树。

MIT

使用邻接矩阵表示上图：

1
2
3
4
5
6
7
8
var graph = [
  [0, 2, 4, 0, 0, 0],
  [2, 0, 2, 4, 2, 0],
  [4, 2, 0, 0, 3, 0],
  [0, 4, 0, 0, 3, 2],
  [0, 2, 3, 3, 0, 2],
  [0, 0, 0, 2, 2, 0],
];

主要有两种算法：

  • Prim（普里姆） 算法
  • Kruskal（克鲁斯卡尔） 算法

Prim（普里姆）算法：每次从未遍历的节点中选择最小权重点连线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
function prim() {
  var parent = [],
    key = [],
    visited = [],
    length = graph.length,
    i;

  // 把所有顶点 key 设置为无限大，未访问
  for (i = 0; i < length; i++) {
    key[i] = Number.MAX_SAFE_INTEGER;
    visited[i] = false;
  }
  
  // 选择第一个 key 作为第一个顶点
  key[0] = 0;
  // 第一个顶点为 MST 根结点，所以 parent 为 -1
  parent[0] = -1;

  // 对所有顶点求 MST
  for (i = 0; i < length - 1; i++) {
    // 从未处理集合中选出最小的key
    var u = minKey(key, visited);
    // 设置未true，避免重复计算
    visited[u] = true;
    
    // 遍历所有点，如果得出更小的权重，则在 parent 中 保存路径
    // 并且更新顶点权重值 key
    for (var v = 0; v < length; v++) {
      if (graph[u][v] &&
          visited[v] === false &&
          graph[u][v] < key[v]) {
        parent[v] = u;
        key[v] = graph[u][v];
      }
    }
  }
  return parent;
}

function minKey(key, visited) {
  var min = Number.MAX_SAFE_INTEGER,
    minIndex = -1;

  for (var v = 0; v < key.length; v++) {
    if (visited[v] == false && key[v] <= min) {
      min = key[v];
      minIndex = v;
    }
  }
 
   return minIndex;
}

Kruskal（克鲁斯卡尔） 算法: 每次从未遍历的边中选择最小权重的边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
function kruskal() {
  const INF = Number.MAX_SAFE_INTEGER;
  var length = graph.length;
  var parent = [];
  var ne = 0,
    a,
    b,
    u,
    v,
    i,
    j,
    min;
  
  // 拷贝 graph 到 cost 中，方便修改和保留原始值
  var cost = initializeCost(graph);

  // 当 MST 的边数小于顶点总数 - 1 时
  while (ne < length - 1) {
    // 选出权重最小边
    for (i = 0, min = INF; i < length; i++) {
      for (j = 0; j < length; j++) {
        if (cost[i][j] < min) {
          min = cost[i][j];
          u = i;
          v = j;
        }
      }
    }
    
    // 分别找出 u，v 的祖先节点，看是否为同一节点，如果是，则跳过
    // 避免环路
    if (union(find(u, parent), find(v, parent), parent)) {
      console.log("edge", u, v, graph[u][v]);
      ne++;
    }
    
    // 避免重复计算
    cost[u][v] = cost[v][u] = INF;
  }
}

var find = function (i, parent) {
  while (parent[i] !== undefined) {
    i = parent[i];
  }
  return i;
};

var union = function (i, j, parent) {
  if (i != j) {
    parent[j] = i;
    return true;
  }

  return false;
};

var initializeCost = function(graph) {
  const cost = [];
  const { length } = graph;
  for (let i = 0; i < length; i++) {
    cost[i] = [];
    for (let j = 0; j < length; j++) {
      if (graph[i][j] === 0) {
        cost[i][j] = INF;
      } else {
        cost[i][j] = graph[i][j];
      }
    }
  }
  return cost;
};