算法篇-union-find并查集

這個算法主要用來判斷2點是否連通

在部落格記錄下來，友善以後能用

public class WeightedQuickUnionUF {
    private int[] parent;   // parent[i] = parent of i
    private int[] size;     // size[i] = number of sites in subtree rooted at i
    private int count;      // number of components


    public WeightedQuickUnionUF(int n) {
        count = n;
        parent = new int[n];
        size = new int[n];
        for (int i = ; i < n; i++) {
            parent[i] = i;
            size[i] = ;
        }
    }


    public int count() {
        return count;
    }


    public int find(int p) {
        validate(p);
        while (p != parent[p])
            p = parent[p];
        return p;
    }

    // validate that p is a valid index
    private void validate(int p) {
        int n = parent.length;
        if (p <  || p >= n) {
            throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-));  
        }
    }


    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }


    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;

        // make smaller root point to larger one
        if (size[rootP] < size[rootQ]) {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        else {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }
        count--;
    }



    public static void main(String[] args) {
        int n = StdIn.readInt();
        WeightedQuickUnionUF uf = new WeightedQuickUnionUF(n);
        while (!StdIn.isEmpty()) {
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            if (uf.connected(p, q)) continue;
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
        StdOut.println(uf.count() + " components");
    }

}
           

使用執行個體Coursera大作業week1

Percolation .java

import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {

    private WeightedQuickUnionUF uf;  
    private WeightedQuickUnionUF uf_backwash;
    private int N;  
    private boolean[] arrayOpen; 
    private int openSiteNumber;

    public Percolation(int n)
    {
        if(n<||n==-)
        {
            throw new IllegalArgumentException();  
        }
        this.N=n;
        this.uf = new WeightedQuickUnionUF((N+)*(N+)); 
        this.uf_backwash = new WeightedQuickUnionUF(N*N+N+);  
        this.arrayOpen=new boolean[(N+)*(N+)];
        this.openSiteNumber=;

        for (int i=; i<=N; i++){  
            uf.union(*N+, *N+i);  
            uf_backwash.union(*N+, *N+i);  
            arrayOpen[*N+i] = true;  
            uf.union((N+)*N+, (N+)*N+i);  
            arrayOpen[(N+)*N+i] = true;  
        } 

    }
    public void open(int row, int col)
    {
        if (row <  || row > N){  
            throw new IndexOutOfBoundsException("row index " + row + " out of bounds");  
        }  
        if (col <  || col > N){  
            throw new IndexOutOfBoundsException("row index " + col+ " out of bounds");  
        }
        if (arrayOpen[row*N+col]){  
            return;  
        }
        openSiteNumber++;
        arrayOpen[row*N+col] = true; 

        if (arrayOpen[(row-)*N+col]){  
            uf.union(row*N+col, (row-)*N+col);  
            uf_backwash.union(row*N+col, (row-)*N+col);  
        }  
        if (arrayOpen[(row+)*N+col]){  
            uf.union(row*N+col, (row+)*N+col);  
            if (row!=N){  
                uf_backwash.union(row*N+col, (row+)*N+col);  
            }  
        }  
        if (col!= && arrayOpen[row*N+col-]){  
            uf.union(row*N+col, row*N+col-);  
            uf_backwash.union(row*N+col, row*N+col-);  
        }  
        if (col!=N && arrayOpen[row*N+col+]){  
            uf.union(row*N+col, row*N+col+);  
            uf_backwash.union(row*N+col, row*N+col+);  
        } 

    }
    public boolean isOpen(int row, int col)
    {
        if (row <  || row > N){  
            throw new IndexOutOfBoundsException("row index " + row + " out of bounds");  
        }  
        if (col <  || col > N){  
            throw new IndexOutOfBoundsException("row index " + col+ " out of bounds");  
        }
        return arrayOpen[row*N+col];
    }
    public boolean isFull(int row, int col)
    {
        if (row <  || row > N){  
            throw new IndexOutOfBoundsException("row index " + row + " out of bounds");  
        }  
        if (col <  || col > N){  
            throw new IndexOutOfBoundsException("row index " + col+ " out of bounds");  
        } 
        return uf_backwash.connected(row*N+col, *N+) && arrayOpen[row*N+col]; 
    }
    public int numberOfOpenSites()
    {
        return openSiteNumber;
    }
    public boolean percolates()
    {
        return uf.connected(*N+, (N+)*N+);
    }
    public static void main(String[] args)
    {

    }
}

           

PercolationStats.java

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class PercolationStats {

    private double recT[];  
    private double res_mean;  
    private double res_stddev;  
    private int N; 

    public PercolationStats(int n, int trials) 
    {
        this.recT = new double[trials];  
        this.N = n;  

        int times = ; 
       if (n <= ){  
            throw new IllegalArgumentException();  
        }  
        if (trials <= ){  
            throw new IllegalArgumentException();  
        }   
        this.recT = new double[trials];  
        while (times < trials){  
            Percolation percolation = new Percolation(N);  
            boolean[][] arrOpen = new boolean[N+][N+];  
            int count = ;  
            while(true){  
                count++;  
                while(true){  
                    int x = StdRandom.uniform(N) + ;  
                    int y = StdRandom.uniform(N) + ;  
                    if (arrOpen[x][y]){  
                        continue;  
                    }else{  
                        percolation.open(x, y);  
                        arrOpen[x][y] = true;  
                        break;  
                    }  
                }  
                if (percolation.percolates()){  
                    recT[times] = (double)count / ((double)N * (double)N);  
                    break;  
                }  
            }  
            times++;  
        }  
        this.res_mean = StdStats.mean(recT);  
        this.res_stddev = StdStats.stddev(recT);
    }
    public double mean()                        
    {
        return res_mean;
    }
    public double stddev()
    {
        return res_stddev;
    }
    public double confidenceLo()
    {
        return this.res_mean - *this.res_stddev / Math.sqrt(N);
    }
    public double confidenceHi() 
    {
        return this.res_mean + *this.res_stddev / Math.sqrt(N);
    }

    public static void main(String[] args)
    {
        int N = StdIn.readInt();  
        int T = StdIn.readInt();  
        PercolationStats percolationStats = new PercolationStats(N, T);  
        StdOut.println("mean = " + percolationStats.mean());  
        StdOut.println("stddev = " + percolationStats.stddev());  
        StdOut.println("95% confidence interval " + percolationStats.confidenceLo() + ", " + percolationStats.confidenceHi()); 
    }
}