Algorithms, Part I快速查找算法

蔚落 2022-03-11 01:59 197阅读 0赞

更新，删掉了之前的  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDI2Nzky_size_16_color_FFFFFF_t_70]  
以上是我画的  
下面附上代码

//快速查找算法
    interface a{
    boolean connected(int p,int q);
    void union(int p,int q);
    }
    
    class Main implements a {
        private int [] id;
        public Main(int n){
            id=new int[n];
            for(int i=0;i<n;i++){
                id[i]=i;
            }
        }
        public boolean connected(int p,int q){
            if(id[p]==id[q]){
                return true;
            }
            else return false;
        }
        public void union(int p,int q){
            int pid=id[p];
            int qid=id[q];
            for(int i=0;i<id.length;i++){
                if(id[i]==pid){
                    id[i]=qid;
                }
            }
        }
        public static void main(String[] args) {
            Main m=new Main(10);
            m.union(4,3);
            m.union(3,8);
            m.union(6,5);
            m.union(9,4);
            m.union(2,1);
            m.union(5,0);
            m.union(7,2);
            m.union(6,1);
           // m.union(7,8);
            System.out.println(m.connected(0,6));
            System.out.println(m.connected(3,7));
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDI2Nzky_size_16_color_FFFFFF_t_70 1]  
对于连通性的快速查找算法来说，是将连接的两头想象成自己，即自己连接自己，一条线即对称轴，对称轴上连接的值是一样的  
也就是说：在迷宫里，快速查找到出口的办法就是他们的标置是一样的，也就是值是一样的

附上一篇不一样的思路的文章：https://blog.csdn.net/qq\_36654136/article/details/85270776

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDI2Nzky_size_16_color_FFFFFF_t_70]: /images/20220311/77255ce9e4594f47af882c76505d2565.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDI2Nzky_size_16_color_FFFFFF_t_70 1]: /images/20220311/f597c8d8d5cc4da78922e82c062e2c13.png