概述

开篇直接讲 Union-Find，然后以它为例，讲解如何使用科学方法研究算法性能。

编程作业是使用加权快速合并（Weighted Quick Union）解决渗滤（Percolation）问题。

建议阅读《算法 4th》的 1.4、1.5 两节。

开发高效算法的流程

建立问题模型
找出解决该问题大体上所需要的基本操作，据此找出算法解决该问题
算法是否足够快？是否满足对存储空间的要求？
如果不满足，我们就需要搞清楚为什么会这样
想办法找出造成这些问题的源头，然后提出新的算法
如此循环直到满意为止

Quick-find

Union-Find - 图1

class QuickFindUF
{
    private int[] _id;
    public QuickFindUF(int n)
    {
        _id = new int[n];
        for (var i = 0; i < n; i++)
        {
            _id[i] = i;
        }
    }
    public bool Connected(int p, int q)
    {
        return _id[p] == _id[q];
    }
    public void Union(int p, int q)
    {
        var pId = _id[p];
        var qId = _id[q];
        for (var i = 0; i < _id.Length; i++)
        {
            if (_id[i] == pId)
            {
                _id[i] = qId;
            }
        }
    }
}

Union-Find - 图2

合并操作代价太大，特别是如果你需要在 N 个对象上进行 N 次合并操作时，单是判断它们是否连通就需要正比于 N^2 的时间。

Union-Find - 图3

对于大型问题，我们不能接受需要平方时间的算法，因为它们无法成比例适应大规模问题。

Quick-union

Union-Find - 图4

public class QuickUnionUF
{
    private int[] _id;
    public QuickUnionUF(int n)
    {
        _id = new int[n];
        for (var i = 0; i < n; i++)
        {
            _id[i] = i;
        }
    }
    private int Root(int i)
    {
        while (i!=_id[i])
        {
            i = _id[i];
        }
        return i;
    }
    public bool Connected(int p, int q)
    {
        return Root(p) == Root(q);
    }
    public void Union(int p, int q)
    {
        var i = Root(p);
        var j = Root(q);
        _id[i] = j;
    }
}