介绍

Kruskal 演算法是一种用来寻找最小生成树的演算法。最小生成树是一副连通加权无向图中一棵权值最小的生成树，参考最小生成树 (opens new window)。用来解决同样问题的还有 Prim 演算法和 Boruvka 演算法（英语：Borůvka's algorithm）等。三种演算法都是贪心算法的应用。和 Boruvka 演算法不同的地方是，Kruskal 演算法在图中存在相同权值的边时也有效。

平均时间复杂度为${\displaystyle \mathrm {O} (|E|\log |V|)}$，其中 E 和 V 分别是图的边集和点集。

贪心算法

贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

参考：贪心算法 - Wikiwand (opens new window)

步骤

• 新建图 G，G 中拥有原图中相同的节点，但没有边
• 将原图中所有的边按权值从小到大排序
• 从权值最小的边开始，如果这条边连接的两个节点于图 G 中不在同一个连通分量中，则添加这条边到图 G 中
• 重复 3，直至图 G 中所有的节点都在同一个连通分量中

并查集

数学中的并查集：

并查集（Disjoint Set）是指集合彼此相交的的子集结果是一个空集。在集合理论中，有时我们会注意到两个集合中没有共同的元素，这两个集合的交集是一个空集。这种类型的集合被称为并查集。例如，如果我们有 X={a，b，c} 和 Y={d，e，f}，那么我们可以说给定的两个集合是不相交的，因为在这两个集合 X 和 Y 中没有共同的元素。更多关于什么是不相交集，并查集联合（disjoint set union），维恩图 (opens new window)，互为并查集（pairwise disjoint set）详细的例子，参见：Disjoint Set - Definition & Examples | Pairwise Disjoint Set (opens new window)。

在计算机科学中，并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：

• 查询：查询某个元素属于哪个集合，通常是返回集合内的一个 “代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
• 合并：将两个集合合并为一个。
• 添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。

由于支持查询和合并这两种操作，并查集在英文中也被称为联合 - 查找数据结构（Union-find data structure）或者合并 - 查找集合（Merge-find set）。

“并查集” 可以用来指代任何支持上述操作的数据结构，但是一般来说，“并查集” 特指其中最常见的一种实现：不交集森林（Disjoint-set forest）。经过优化的不交集森林有线性的空间复杂度（O (n)，n 为元素数目，下同），以及接近常数的单次操作平均时间复杂度（${\displaystyle \mathrm {O} \left(\alpha \left(n\right)\right)}$，$\alpha$ 为反阿克曼函数），是效率最高的常见数据结构之一。

并查集是用于计算最小生成树的克鲁斯克尔算法中的关键。由于最小生成树在网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分配等方面也有应用。

不交集森林

• 表示：不交集森林把每一个集合以一棵树表示，每一个节点即是一个元素。节点保存着到它的父节点的引用，树的根节点则保存一个空引用或者到自身的引用或者其他无效值，以表示自身为根节点。

• 添加：添加操作 MakeSet (x) 添加一个元素 x，这个元素单独属于一个仅有它自己的集合。在不交集森林中，添加操作仅需将元素标记为根节点。在经过优化的不交集森林中，添加操作还会初始化一些有关节点的信息，例如集合的大小或者秩。

• 查询：在不交集森林中，每个集合的代表即是集合的根节点。查询操作 Find (x) 从 x 开始，根据节点到父节点的引用向根行进，直到找到根节点。

• 路径压缩优化：在集合很大或者树很不平衡时，上述代码的效率很差，最坏情况下（树退化成一条链时），单次查询的时间复杂度高达${\displaystyle \mathrm {O} \left(n\right)}$。一个常见的优化是路径压缩：在查询时，把被查询的节点到根节点的路径上的所有节点的父节点设置为根结点，从而减小树的高度。也就是说，在向上查询的同时，把在路径上的每个节点都直接连接到根上，以后查询时就能直接查询到根节点。

• 合并：合并操作 Union (x, y) 把元素 x 所在的集合与元素 y 所在的集合合并为一个。合并操作首先找出节点 x 与节点 y 对应的两个根节点，如果两个根节点其实是同一个，则说明元素 x 与元素 y 已经位于同一个集合中，否则，则使其中一个根节点成为另一个的父节点。

• 按秩合并优化：上述代码的问题在于，可能会使得树不平衡，增大树的深度，从而增加查询的耗时。一个控制树的深度的办法是，在合并时，比较两棵树的大小，较大的一棵树的根节点成为合并后的树的根节点，较小的一棵树的根节点则成为前者的子节点。判断树的大小有两种常用的方法，一个是以树中元素的数量作为树的大小，这被称为按大小合并。另一种做法则是使用 “秩” 来比较树的大小。” 秩 “的定义如下：

  • 只有根节点的树（即只有一个元素的集合），秩为 0；
  • 当两棵秩不同的树合并后，新的树的秩为原来两棵树的秩的较大者；
  • 当两棵秩相同的树合并后，新的树的秩为原来的树的秩加一。

图论并查集详解：

参见：

• 并查集 - Wikiwand (opens new window)
• Disjoint–Set Data Structure (Union–Find Algorithm) | Techie Delight (opens new window)

演示

实现

JavaScript

class DisjointSetTreeNode {
  // Disjoint Set Node to store the parent and rank
  constructor (key) {
    this.key = key
    this.parent = this
    this.rank = 0
  }
}

class DisjointSetTree {
  // Disjoint Set DataStructure
  constructor () {
    // map to from node name to the node object
    this.map = {}
  }

  makeSet (x) {
    // Function to create a new set with x as its member
    this.map[x] = new DisjointSetTreeNode(x)
  }

  findSet (x) {
    // Function to find the set x belongs to (with path-compression)
    if (this.map[x] !== this.map[x].parent) {
      this.map[x].parent = this.findSet(this.map[x].parent.key)
    }
    return this.map[x].parent
  }

  union (x, y) {
    // Function to merge 2 disjoint sets
    this.link(this.findSet(x), this.findSet(y))
  }

  link (x, y) {
    // Helper function for union operation
    if (x.rank > y.rank) {
      y.parent = x
    } else {
      x.parent = y
      if (x.rank === y.rank) {
        y.rank += 1
      }
    }
  }
}

class GraphWeightedUndirectedAdjacencyList {
  // Weighted Undirected Graph class
  constructor () {
    this.connections = {}
    this.nodes = 0
  }

  addNode (node) {
    // Function to add a node to the graph (connection represented by set)
    this.connections[node] = {}
    this.nodes += 1
  }

  addEdge (node1, node2, weight) {
    // Function to add an edge (adds the node too if they are not present in the graph)
    if (!(node1 in this.connections)) { this.addNode(node1) }
    if (!(node2 in this.connections)) { this.addNode(node2) }
    this.connections[node1][node2] = weight
    this.connections[node2][node1] = weight
  }

  KruskalMST () {
    // Kruskal's Algorithm to generate a Minimum Spanning Tree (MST) of a graph
    // Details: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
    // getting the edges in ascending order of weights
    const edges = []
    const seen = new Set()
    for (const start of Object.keys(this.connections)) {
      for (const end of Object.keys(this.connections[start])) {
        if (!seen.has(`${start} ${end}`)) {
          seen.add(`${end} ${start}`)
          edges.push([start, end, this.connections[start][end]])
        }
      }
    }
    edges.sort((a, b) => a[2] - b[2])
    // creating the disjoint set
    const disjointSet = new DisjointSetTree()
    Object.keys(this.connections).forEach(node => disjointSet.makeSet(node))
    // MST generation
    const graph = new GraphWeightedUndirectedAdjacencyList()
    let numEdges = 0
    let index = 0
    while (numEdges < this.nodes - 1) {
      const [u, v, w] = edges[index]
      index += 1
      if (disjointSet.findSet(u) !== disjointSet.findSet(v)) {
        numEdges += 1
        graph.addEdge(u, v, w)
        disjointSet.union(u, v)
      }
    }
    return graph
  }
}
// const graph = new GraphWeightedUndirectedAdjacencyList()
// graph.addEdge(1, 2, 1)
// graph.addEdge(2, 3, 2)
// graph.addEdge(3, 4, 1)
// graph.addEdge(3, 5, 100) // Removed in MST
// graph.addEdge(4, 5, 5)
// graph.KruskalMST()

参考

• Kruskal's algorithm - Wikiwand (opens new window)
• 克鲁斯克尔演算法 - Wikiwand (opens new window)