《算法》笔记 2 - 动态连通性问题

短命女 2023-06-04 10:54 15阅读 0赞

*  动态连通性问题
 *  实现
    
     *  通用代码
     *  Quick-Find算法
     *  Quick-Union算法
     *  加权Quick-Union算法

### 动态连通性问题 ###

在基础部分的最后一节，作者用一个现实中应用非常广泛的案例，说明以下几点：

*  优秀的算法因为能解决实际问题而变得更为重要；
 *  高效算法的代码也可以很简单；
 *  理解某个实现的性能特点是一项有趣的挑战；
 *  在解决同一个问题的多种算法之间进行选择时，科学方法是一种重要的工具；
 *  迭代式改进能够让算法的效率越来越高。

动态连通性问题的输入是一列整数对，其中的每个整数都表示一个某种类型的对象，一对整数对p q可以理解为“p和q是相连的”。相连是一种等价关系，其具有：

*  自反性，p和p也是相连的；
 *  对称性，p和q相连，则q和p也是相连的；
 *  传递性，p和q相连，q和r相连，则p和r也是相连的。

程序的目标是过滤掉序列中无意义的整数对，当程序从输入中读取了整数对pq时，如果已知的所有整数对都不能说明p和q是相连的，那么则将这一对整数写入到输出中。如果已知的数据可以说明p和q是相连的，那么程序应该忽略pq这对整数并继续处理输入中的下一对整数。

动态连通性问题的实际应用很多，比如：检查通信网络中计算机之间是否连通、电子电路中的触点是否连接或者社交网络中的人是否相识等等。

### 实现 ###

接下来会统一使用网络方面的术语，将整数称为*触点*、整数对称为*连接*、等价类称为*连通分量*或*分量*。  
明确需要解决的问题后，就可以抽象出算法的API了，包括

void union(int p,int q)  //在p q之间添加一条连接，将两个分量归并
    int find(int p)  //返回p所在分量的标识符
    boolean connected(int p int q) //判断两个触点是否在同一分量
    int count() //连通分量的数量

#### 通用代码 ####

算法的基本代码如下，其中find()、union()方法在各种算法中有不同的实现。

public class UF {
    
        private int[] id;  //分量id(以触点作为索引)
        private int count; // 连通分量的数量
    
        public UFquickFind(int n) {
            id = new int[n];
            count=n;
            for (int i = 0; i < n; i++) {
                id[i] = i;
            }
        }
    
        public int find(int p) {
            //待实现
        }
    
        public int count() {
            return count;
        }
    
        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }
    
        public void union(int p, int q) {
            //待实现
        }
    
        public static void main(String[] args) {
            int n = StdIn.readInt();  //读取触点数量
            StdOut.println(n);
            UF uf = new UF(n);  //初始化N个分量
            while (!StdIn.isEmpty()) {
                int p = StdIn.readInt();
                int q = StdIn.readInt();  //读取整数对
                if (uf.connected(p, q))  //是否连通,如果已经连通则忽略
                    continue;
                uf.union(p, q);  //归并分量
            }
            StdOut.println(uf.count() + " components");
        }
    }

#### Quick-Find算法 ####

##### 实现 #####

最直接的方法是当p和q连通时，让id\[p\]=id\[q\]，所以同一连通分量中的所有触点在id\[\]中的值是全部相同的。find(p)只需返回id\[p\]，但union()方法在将p和q设置为同一连通分量时比较麻烦，需要改变p或q所在分量中所有元素的值。

public int find(int p) {
            return id[p];
    }
    
    public void union(int p, int q) {
            int vp = find(p); //一次数组访问
            int vq = find(q); //一次数组访问
    
            if(vp==vq){
                return;
            }
            for(int i=0;i<id.length;i++){
                if(id[i]==vq){ //N次数组访问
                    id[i]=vp;  //最好情况只执行一次，最坏情况执行N-1次
                }
            }
            count--;
    }

这种方法得到的find操作的速度很快，只需要访问id\[\]数组一次，但union操作由于每次都要扫描整个数组而变得很慢。这里代码中是刷新q所在的分量，也可以改为刷新p所在的分量。

##### 分析 #####

在分析算法的成本时，主要考虑的是数组的访问次数（包括读、写）。  
那么Quick-Find算法的成本如何呢？假设问题的规模为N，则数组的长度为N，那么每次find()只访问数组一次，union()访问数组的次数在(N+3)到(2N+1)之间。  
开头的两次find调用访问数组2次，for循环会访问数组N次，然后：  
a.在最好的情况下，q所在的连通分量中，只有q一个成员，内层的if判断只会成立一次。所以总次数=2+N+1=N+3次。

b.在最坏的情况下，除了元素p，其余成员都与q在同一个连通分量中，那么内层的if判断会成立N-1次，总次数=2+N+N-1=2N+1。

假设最后只得到一个连通分量，则至少需要调用union方法N-1次，所以最好情况下，union方法的调用总次数为(N-1)\*(N+3)，用~N^2来近似表示，可见在最终得到少数连通分量的场景下，Quick-Find算法的运行时间随问题规模的增长是平方级别的。平方级别、立方级别、指数级别的算法等都无法用来解决大型问题。

#### Quick-Union算法 ####

接下来的Quick-Union算法相比Quick-Find算法，其Union的速度较快。它也采用相同的数据结构——以触点作为索引的id\[\]数组，但这次让每个数组元素都代表同一连通分量中另一个分量的名称，实际上同一连通分量的节点构成了一棵树，但数组元素的值等于其索引时，它就是这棵树的根节点。find()操作返回的就是一棵树的根节点，如果两个分量有相同的根节点则表示它们互相连通，否则调用union()方法将其中的一棵树合并到另一颗树上，就完成了两个连通分量的归并。

##### 实现 #####

public int find(int p) {
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }
    
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        id[pRoot] = qRoot;
        count--;
    }

##### 分析 #####

quick-union算法的成本依赖输入的特点，在最好的情况下，一棵树只有根节点自己，find()只需访问数组一次；而在最坏的情况下，树的结构为一颗深度为节点数-1，每一层都只有一个节点，设数的深度为N，这时如果需要查找最底层节点的根节点，find()方法需要访问数组N+(N+1)=2N+1次。

while (p != id[p]) { //N+1次
        p = id[p];  //N次
    }

在这种最坏的情况下，为了让树的深度最大，每次新的节点都会连接到树的最底层，输入整数对是有序的0-1，0-2，0-3等，其中0链接接到1,1链接到2，2链接到3，可见union的访问次数为：(2N+1)+1+1=2N+3次

public void union(int p, int q) {
        int pRoot = find(p); //2N+1次
        int qRoot = find(q); //1次，另一个节点的根节点为它自己
        if (pRoot == qRoot) {
            return;
        }
        id[pRoot] = qRoot; //1次
        count--;
    }

所以忽略常数3，处理N个节点的访问次数为2*(1+2+...+N)=2*n(n-1)/2，用~N^2来近似表示，则最坏情况为平方级别。

#### 加权Quick-Union算法 ####

Quick-Union算法的速度取决于生成的树的深度，深度越大速度越慢。union操作时，避免将较大的树链接到较小的树可以有效控制树的深度，从而大大改进算法的效率，这便是加权Quick-Union算法。加权Quick-Union算法是在Quick-Union算法的基础上，增加一个数组来记录每颗树的权重（树包含的节点数量），然后在union操作时将权重小的树链接到权重大的树。

##### 实现 #####

public void union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        if (aRoot == bRoot) {
            return;
        }
    
        if (size[aRoot] < size[bRoot]) {  //size[]记录树的权重
            parent[aRoot] = bRoot;
            size[bRoot] += size[aRoot];  //树归并时，权重也会发生变化
        } else {
            parent[bRoot] = aRoot;
            size[aRoot] += size[bRoot];
        }
        count--;
    }

##### 分析 #####

关于加权Quick-Union算法的最坏情况，既较要被归并的两棵树的大小总数相等的，且大小都是2的幂（满二叉树），此时N个节点的树的深度为Lg(N)，结合对Quick-Union算法的分析可知加权Quick-Union算法的成本增长数量级为对数级别。

综上，动态连通性问题的求解过程便是一个定义问题、给出初级算法的实现、当算法能解决问题的规模达不到期望时逐步改进算法的过程。并且用经验性的分析（和数学分析）验证改进后的效果，尽量为算法在最快情况下的性能提供保证，但在处理普通数据时也要有良好的性能。

转载于:https://www.cnblogs.com/zhixin9001/p/11380223.html