并查集算法关于渗透模型中虚拟节点的使用问题

首先还是要描述一下我们所要解决的问题以及基本方法。该问题的来源是来自于普林斯顿算法课程第一讲的内容。为了通过这么课程的第一讲作业内容，本人搜集了一些网上资料以及亲自动手调试，才好不容易得到82分的成绩，勉强达到要求。具体不合格内容，后面有时间补上！

 

问题描述：渗流模型

模型如下图，由一个n*n的网格表示。

节点状态：网格中的每个节点有两种状态，即1）block封锁状态，2）open开放状态，图中黑色块为block状态，蓝色和白色块为open状态；3）full：某节点状态为open，且能找到一条路径，使得该节点与top（也就是第一行）相通，这个路径只能是四领域路径（也就是上下左右），这个节点状态就是full 。图中白色节点则为非full状态，蓝色节点为full状态。

系统状态：系统状态主要有两种，渗透（percolation）和非渗透状态。渗透状态为，能找到一条路径（当然是open状态的节点组成的！），使得top与bottom相通。如下右图，蓝色区域连通了top与bottom，所以使得系统为渗透状态！

                                       
                                                      
 

问题：

1）设计并实现一个算法，判断节点以及系统的状态

2）设计并实现一个算法，判断一个n*n的系统需要多少比例的open状态节点，能使得系统为渗透状态

更多有关问题和模型的描述请见渗流模型

 

并查集算法概述

更多并查集算法的内容请见并查集算法

1）quick-find算法

该算法使用的数据结构类似于线性表中的顺序表结构，利用数组存储每个节点的连接号，如下图，id[]为存储信息的数组，其索引p代表的就是节点的索引，其值id[p]代表的就是节点p的连接号，在下图所示示例中，节点0、5、6连接号相同，故相连通，节点1、2、7相连通，节点3、4、8、9相连通。                   

                    

若要进行新的连接操作，如将上图的0、1节点相连， 则将所有连接号为id[0]=0的节点的连接号置为id[1]=1

（当然你也可以规定将所有连接号为id[1]=1的节点的连接号置为id[0]=0），如下图所示。

               

优点：该算法使得确定两个节点是否有连通关系非常方便，算法复杂度仅仅为O(1)。

缺点：当新建一个新的节点连接关系时，需要遍历整个数组，于是该操作算法复杂度为O(n)。

2）quick-union算法

quick-union的方法类似于数据结构中数（tree）的方法。为了能将节点数与连接号关联起来，该算法仍以数组来存储节点的连接信息。每次建立新的连接，我们不是将所有相关的连接号全部进行调整，而是只调整树根（root）之间的连接关系即可。如下图所示，数组索引p表示节点索引，而数组值id[p]表示节点p的父节点。下例中，0、1、7、8均为孤立节点，而3的父节点为4，2、4的父节点和根节点都是9，所以3的根节点也为9，5的父节点和根节点为6。                                                  

                                       

现在要将3与5建立新的连接关系，则找到3和5的根节点，分别为9和6，所以将9的父节点置为6（当然你也可以将6的父节点置为9），得到

                                                

可以看到，当新建连接关系时，只有一个节点的连接号更新了！

优点：在新建连接关系时，只需要改变root的连接号

缺点：新建和查询均要找到root的连接号，这和树的高度有关系，如果树的瘦高的，那么效率就会明显降低！

3）weighted quick-union算法

quick-union的算法，在新建连接关系是，是按照约定的规则对root进行连接，这样难以避免产生一个瘦高的树。很自然的想法就是将小的树连接到大的树上。如下图所示，左为按规则连接，右为weighted方法，如此一来，找到root节点的效率将大大提高！

                

4）路径压缩的 weighted quick-union算法

若每个节点都直接连接到根节点上，那么查找的算法复杂度就接近O(1)

实际上，在使用find方法查找节点的root时，既可以调整树的大小。

 

模特卡罗随机模拟

通过大量的随机测验，得到近似答案！

 

路经压缩的weighted quick-union算法实现（源程序）

UF.java

 

/**
 * union-find类，使用的路径压缩的weighted quike-union方法
 * Created by lps on 2017/1/23.
 */
public class UF {

    private int[] id;//索引数组
    private int[] sz;//存储连接块的大小（带权重的union-find算法）
    private int count;//链接块的个数

    /**
     * 构造函数，初始化id数组
     * @param N 数组长度
     */
    public UF(int N)
    {
        id = new int[N];
        sz = new int[N];
        for(int i = 0;i < N;i ++)
        {
            id[i] = i;//每个元素的初始根节点是它自己
            sz[i] = 1;//初始情况，每个连接块大小均为1
        }
        count = N;//每一块暂时都是独立的
    }



    /**
     * 添加连接关系
     * @param p 某节点p
     * @param q 某节点q
     */
    public void union(int p, int q)
    {
        int pRoot = find(p);//找到根节点
        int qRoot = find(q);
        if(pRoot == qRoot)//已经连接则直接返回
            return;
        if(sz[pRoot] < sz[qRoot])
        {
            id[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }
        else
        {
            id[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
        count --;//连接后少一个连接块
    }

    /**
     * 找到p的根节点
     * @param p 某节点p
     * @return 节点p的根节点
     */
    public int find(int p)
    {
        while(p != id[p])
        {
            id[p] = id[id[p]];//路径压缩
            p = id[p];
        }
        return p;
    }

    /**
     * 判断是否两节点是否是连接的
     * @param p 节点p
     * @param q 节点q
     * @return true 连接 false 不连接
     */
    public boolean connected(int p, int q)
    {
        return find(p) == find(q);
    }

    /**
     * 得到连接块个数
     * @return count 连接块个数
     */
    public int count()
    {
        return count;
    }

    public void display()
    {
        System.out.print("id:");
        for(int i = 0;i < id.length;i ++)
        {
            System.out.print(id[i]);
            System.out.print(" ");
        }
        System.out.println("end");
    }

    public static void main(String[] args)
    {
        UF uf = new UF(10);
        uf.union(1,2);
        uf.union(1,3);
        uf.union(1,4);
        uf.union(0,9);
        uf.union(0,5);
        uf.union(0,1);
        //uf.display();
        //System.out.println(uf.find(5));
    }
}

 percolation.java

 

 

/**
 * 这是渗透模型类，生成一个n*n的棋盘模型
 * Created by lps on 2017/1/21.
 */
public class Percolation {

    private int count;//open site的个数
    private int rows, cols;//渗透模型的行列数
    private boolean[] isopen;//这是判断是否是开状态的数组
    private UF uf,uf2;

    /**
     * 渗透模型的构造函数
     * @param n 渗透模型棋盘大小为n*n 1 <= n <= n
     */
    public Percolation(int n)
    {
        if(n <= 0)//抛出异常
            throw new java.lang.IllegalArgumentException("n must be >= 1");
        count = 0;//初始情况是相互独立的
        rows = n;//保存行列值
        cols = n;
        isopen = new boolean[n*n + 2];
        uf = new UF(n*n + 2);//新建一个UF类，使用该类函数进行并查集算法
                                //注意：第一个为top(0)，最后一个为bottom(n*n-1)
                                //top与bottom连接，则为percolation
        uf2 = new UF(n*n + 1);//不加虚拟节点，为什么要这个数组请见后文
    }

    private int index(int row, int col)
    {
        return (1 + (row - 1) * cols + (col - 1));
    }


    /**
     * 对像素点进行开操作
     * @param row 行号
     * @param col 列号
     */
    public void open(int row, int col)
    {
        if(row < 0 || row > rows || col < 0 || col > cols)//越界
            throw new IndexOutOfBoundsException("row or col must be [1,n]");
        //当前元素在数组中的索引：1 + (row - 1) * cols + (col - 1)
        //如果已经开，则返回
        if(isOpen(row, col))
            return;
        //该位置置为开状态
        isopen[index(row,col)] = true;
        //如果是顶部元素，则与顶点union
        if(row == 1)
        {
            isopen[0] = true;//顶部置为开状态
            uf.union(index(row,col), 0);
            uf2.union(index(row,col), 0);
        }
        //如果是底部元素，则与底部点union
        if(row == rows)
        {
            isopen[rows * cols + 1] = true;//底部置为开状态
            uf.union(index(row,col), rows * cols + 1);
        }
        //up
        if(row > 1 && isOpen(row-1,col))
        {
            //System.out.print("up");
            uf.union(index(row,col), index(row-1,col));
            uf2.union(index(row,col), index(row-1,col));
        }
        //down
        if(row < rows && isOpen(row+1,col))
        {
            //System.out.print("down");
            uf.union(index(row,col), index(row+1,col));
            uf2.union(index(row,col), index(row+1,col));
        }
        //left
        if(col > 1 && isOpen(row,col-1))
        {
            //System.out.print("left");
            uf.union(index(row,col), index(row,col-1));
            uf2.union(index(row,col), index(row,col-1));
        }
        //right
        if(col < cols && isOpen(row,col+1))
        {
            //System.out.print("right");
            uf.union(index(row,col), index(row,col+1));
            uf2.union(index(row,col), index(row,col+1));
        }
        count ++;
    }

    /**
     * 判断像素点是否开状态
     * @param row 行号
     * @param col 列号
     * @return
     */
    public boolean isOpen(int row, int col)
    {
        if(row < 0 || row > rows || col < 0 || col > cols)//越界
            throw new IndexOutOfBoundsException("row or col must be [1,n]");
        return isopen[index(row, col)];
    }

    public boolean isFull(int row, int col)  // is site (row, col) full?
    {
        if(row < 0 || row > rows || col < 0 || col > cols)//越界
            throw new IndexOutOfBoundsException("row or col must be [1,n]");
        if(isOpen(row,col))
            return false;
        return uf2.connected(index(row,col), 0);
    }


    /**
     * 开状态的数量
     * @return 开状态数量
     */
    public int numberOfOpenSites()
    {
        return count;
    }

    /**
     * 判断系统是否渗透
     * @return
     */
    public boolean percolates()
    {
        return uf.connected(0,rows * cols + 1);
    }




    /**
     * 主函数
     */
    public static void main(String[] args) {
        Percolation p = new Percolation(6);
        p.open(1, 6);
        //p.open(2, 3);
        //p.open(3, 3);
        //p.open(3, 1);
        System.out.println(p.isFull(1,6));
        //System.out.println(p.myfind(3,1));
    }
}

percolationStats.java

 

 

import java.util.ArrayList;
import java.util.OptionalDouble;

/**
 * Created by lps on 2017/1/25.
 */
public class PercolationStats {

    private ArrayList<Double> result;//结果数据数组

    public PercolationStats(int n, int trials)    // perform trials independent experiments on an n-by-n grid
    {
        if(n <= 0 || trials <= 0)//抛出异常
            throw new java.lang.IllegalArgumentException("n and trials must be >= 1");
        result = new ArrayList<>(100);
        double size = n*n;
        //开始进行trials次实验
        for(int i = 0;i < trials;i ++)
        {
            //初始化一个渗流模型
            Percolation p = new Percolation(n);
            //随机增加open site，直到系统达到渗流状态
            while (!p.percolates())
            {
                int index_row = (int)(1+Math.random()*(n));
                int index_col = (int)(1+Math.random()*(n));
                p.open(index_row,index_col);
            }
            double x = (double)p.numberOfOpenSites()/size;
            result.add(x);
        }
    }
    public double mean()                          // sample mean of percolation threshold
    {
        OptionalDouble avrg = result.stream().mapToDouble(r->r).average();
        return avrg.getAsDouble();
    }
    public double stddev()                        // sample standard deviation of percolation threshold
    {
        double sum = result.stream().mapToDouble(r->(r-this.mean())*(r-this.mean())).sum();
        double avrg = sum / (double)(result.size()-1);
        return Math.sqrt(avrg);
    }
    public double confidenceLo()                  // low  endpoint of 95% confidence interval
    {
        return (this.mean()-(1.96*this.stddev()/Math.sqrt((double)result.size())));
    }
    public double confidenceHi()                  // high endpoint of 95% confidence interval
    {
        return (this.mean()+(1.96*this.stddev()/Math.sqrt((double)result.size())));
    }
    public static void main(String[] args)        // test client (described below)
    {
        int n = 100, T = 200;
        if(args.length == 2)
        {
            n = Integer.parseInt(args[0]);
            T = Integer.parseInt(args[1]);
        }

        PercolationStats ps = new PercolationStats(n,T);
        System.out.println(ps.mean());
        System.out.println(ps.stddev());
        System.out.println(ps.confidenceLo());
        System.out.println(ps.confidenceHi());
    }
}

 

 程序中注意事项

 并查集算法关于渗透模型中虚拟节点的使用问题

说了这么大半天，终于要说到重点了。在上述代码实现中，为了获得网格内节点与top和bottom的关系，这里引入了虚拟节点，如下图所示，在n*n的网格顶部和底部引入顶部虚拟节点和底部虚拟节点，这样，判断系统是否是percolates的，实际上就是判断顶部虚拟节点和底部虚拟节点是否相连通即可。于是就有了代码段中的

UF uf = new UF(n*n+2)，这就是因为加入了顶部和底部两个虚拟节点，也就是多加了两个节点。

然而，仅仅这样是会带来问题。不如考虑一个3*3的系统，我们先后open(1,3)(2,3)(3,3)(3,1)，此时我们考虑(3,1)节点的状态。isOpen - true；isFull - true。对于open状态毋庸置疑，但是为什么(3,1)节点是full状态的呢，不难想到，该节点的full状态应该是false的！这就是仅用uf数组带来的问题。当open(3,3)后，(3,3)节点位于底层，所以底部虚拟节点将并入(3,3)，而再open(3,1)，该节点也是位于底层，所以该节点并入底部虚拟节点，也就是并入了(3,3)，而实际上，(3,1)和(3,3)是毫无关系的！

实际上，这样处理就有悖于虚拟节点的“虚拟”二字，而成了实节点！

要想解决这个bug，很容易想到的一个方法就是在建立一个渗透模型，只因入顶部虚拟节点，而不引入底部节点，那么久阻断了因底部虚拟节点而造成了底层节点“假”连接！那么有人会问，顶部虚拟节点呢？的确，顶部也会存在相同的问题，但是它并不影响我们对节点状态(open,full)和系统状态(percolation)，所以，我们可以不用管！
                                                          

 

树大小计算（weighted方法实现）

树的大小即由树中的节点数来衡量，伴随着id数组，另外创建个树大小量数组sz（见程序），当新建两个节点的连接关系时，只需比较这两个节点根节点的sz大小即可。换句话说，每次更新sz数组，仅更新该树根节点root的sz大小，比较的时候，也用树的根节点的sz来代替该树的大小！如下述程序所示，

public void union(int p, int q)
    {
        int pRoot = find(p);//找到根节点
        int qRoot = find(q);
        if(pRoot == qRoot)//已经连接则直接返回
            return;
        if(sz[pRoot] < sz[qRoot])
        {
            id[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }
        else
        {
            id[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
        count --;//连接后少一个连接块
    }

 

路径压缩实现

路径压缩实际上就是在weighted quick-union方法的基础上，利用find的方法查询的同时，改变树的连接方式-----尽量将节点都直接连接到根节点上。那么如何实现呢？从程序上来看，很简单，如下所示：

 public int find(int p)
    {
        while(p != id[p])
        {
            id[p] = id[id[p]];//路径压缩
            p = id[p];
        }
        return p;
    }

 

 即在普通的方法上，添加了注释代码部分，不断地将p的爷爷节点赋给p的父节点，那么在找到p的根的同时，已经将根节点赋给了p的父节点（可以判断，在找到根节点的前一个循环，父节点和爷爷节点是同一个节点）。

 

关于程序中使用的数据结构 

并查集程序中，选择的数据结构是顺序表----数组结构，而不是链表结构。理由有下：

1.模型规模固定：一旦模型初始化完成，那么该模型的节点个数就是不变的，所以使用数组可以避开不灵活的弊端；

2.find频繁：并查集算法需要通过find函数来找寻根节点，从而完成各个功能，而顺序表的查找效率为O(1)，聊表的查找效率为O(n)，顺序表更胜一筹；

 

该代码结果分析

该代码实现了基于并查集算法的渗透模型解算，但是实现得并不是很完美！在普林斯顿课程作业提交系统中也仅仅获得了82分（80分过关。。。对不起各位），详细评价见下：

                                                               
 

 

可以看到，该代码正确性也并非100%对，而时间和空间效率还有很大的提升空间！希望后面能进一步加强！

 

并查集的应用

更多并查集应用的例子，见并查集(Union-Find) 应用举例 --- 基础篇

 

评论

1 楼 13227819390 2017-10-22  

请问在博主的percolation代码块里的isFull函数，即112,113行，在判断该节点是open节点之后，return false，，full site不是一定是open site么，这里是不是写反了，还是我自己哪里没有看过来，，希望博主回复一下，十分感谢