Cách tiếp cận khác Union Tìm

Question

Tôi đang nghiên cứu các thuật toán và tôi đã thực hiện thuật toán "Union Find Like" này.

Tôi có một mảng đối tượng với một tham chiếu và tôi tạo liên kết trỏ đến cùng một tham chiếu thay vì có hai int [] với số và trọng số.

• Nó không cần thiết để khởi tạo mảng.
• Bạn sẽ có tối đa N / 2 đối tượng bổ sung (nếu bạn kết hợp theo cặp), nhưng trong một mảng có nhiều kết hợp, bạn sẽ chỉ có một vài đối tượng (chỉ có gốc R) với chỉ các tham chiếu trỏ đến giống nhau vật.
• Đó là một thời gian tuyến tính.

Tôi có thể có một số phản hồi về ý tưởng này?

Cảm ơn.

public class UnionFind {
    
    public static class Pointer {
        Pointer pointerForJoin;
    }
    
    
    // number of elements in array
    private static final int N = 10;
    private static Pointer[] connection = new Pointer[N];
    
    private static void union(int a, int b) {
        if(connection[a] != null && connection[b] != null) {
            if(connection[a].pointerForJoin != connection[b].pointerForJoin )
                connection[a].pointerForJoin = connection[b].pointerForJoin = connection[a];    
        } else if(connection[a] != null) {
            connection[b] = connection[a];
        } else if(connection[b] != null) {
            connection[a] = connection[b];
        } else {
            connection[a] = connection[b] = new Pointer();
            connection[a].pointerForJoin = connection[b].pointerForJoin = connection[a];    
        }
    }
    
    private static boolean isConnected(int a, int b) {
        if (a == b) return true;
        if(connection[a] == null || connection[b] == null) return false;
        return connection[a].pointerForJoin == connection[b].pointerForJoin;
    }
    
    public static void main(String[] args) {        
        union(1,2);
        union(2,3);
        union(5,6);
        union(8,9);
        union(8,2);
        
        System.out.println(isConnected(8,3)); //true
        System.out.println(isConnected(8,2)); //true
        System.out.println(isConnected(9,1)); //true
        System.out.println(isConnected(1,6)); //false
        System.out.println(isConnected(1,7)); //false
        System.out.println(isConnected(0,0)); //true
    }
}
```

Answer 1

Trước hết, tôi thích ý tưởng và cách thực hiện.

Tôi đã cấu trúc lại nó một chút và nghĩ ra rằng:

isConnected : Trích xuất kết nối [a] và kết nối [b] trong các biến cục bộ và đơn giản hóa điều kiện. Eclipse có thể hỗ trợ bạn bước đầu tiên, bước thứ hai tôi đã làm thủ công.

    private static boolean isConnected(int a, int b) {
        if (a == b) {
            return true;
        } else {
            final var pa = connection[a];
            final var pb = connection[b];
            return pa != null && pb != null && pa.pointerForJoin == pb.pointerForJoin;
        }
    }

Trong liên kết, tôi đã làm tương tự với các biến cục bộ (hãy cẩn thận với các phép gán trong mảng. Sau đó, tôi sử dụng các IF lồng nhau, điều này làm cho luồng chương trình dễ đọc hơn.

Kết quả này trong:

private static void union(int a, int b) {
    final var pa = connection[a];
    final var pb = connection[b];
    if(pa != null) {
        if (pb != null) {
            if(pa.pointerForJoin != pb.pointerForJoin)
                pa.pointerForJoin = pb.pointerForJoin = pa;
        } else {
            connection[b] = pa;
        }
    } else {
        // pa == null
        if(pb != null) {
            connection[a] = pb;
        } else {
            connection[a] = connection[b] = new Pointer();
            connection[a].pointerForJoin = connection[a];
        }
    }
}

Bước tiếp theo là sử dụng một lớp trợ giúp thay vì các biến tĩnh, như sau:

public class UnionFind {
    
    public static class Pointer {
        Pointer pointerForJoin;
    }
    
    private final Pointer[] connection;
    
    public UnionFind(int n) {
        connection = new Pointer[n];
    }
    
    private void union(int a, int b) {
        final var pa = connection[a];
        final var pb = connection[b];
        if(pa != null) {
            if (pb != null) {
                if(pa.pointerForJoin != pb.pointerForJoin)
                    pa.pointerForJoin = pb.pointerForJoin = pa;
            } else {
                connection[b] = pa;
            }
        } else {
            // pa == null
            if(pb != null) {
                connection[a] = pb;
            } else {
                connection[a] = connection[b] = new Pointer();
                connection[a].pointerForJoin = connection[a];
            }
        }
    }
    
    private boolean isConnected(int a, int b) {
        if (a == b) {
            return true;
        } else {
            final var pa = connection[a];
            final var pb = connection[b];
            return pa != null && pb != null && pa.pointerForJoin == pb.pointerForJoin;
        }
    }
    
    public static void main(String[] args) {
        var uf = new UnionFind(10);
        uf.union(1,2);
        uf.union(2,3);
        uf.union(5,6);
        uf.union(8,9);
        uf.union(8,2);
        
        System.out.println(uf.isConnected(8,3)); //true
        System.out.println(uf.isConnected(8,2)); //true
        System.out.println(uf.isConnected(9,1)); //true
        System.out.println(uf.isConnected(1,6)); //false
        System.out.println(uf.isConnected(1,7)); //false
        System.out.println(uf.isConnected(0,0)); //true
    }
}

Bạn thấy cách bạn có thể tạo nhiều phiên bản UnionFind? Bạn thậm chí có thể đặt công suất trong thời gian chạy.

Tôi sẽ để lại phần bổ sung JavaDoc còn thiếu cho bạn.

Answer 2

Ngay khi bạn nói đó là thời gian tuyến tính, rõ ràng là có điều gì đó không ổn. Xem nhanh mã không có vòng lặp hoặc đệ quy, vì vậy rõ ràng rằng đó thực sự là thời gian tuyến tính và thuật toán của bạn không hoạt động.

Đây là một ví dụ bạn thất bại, bạn báo cáo falsemặc dù 3và 5phải được kết nối do union(3,1)và union(1,5):

    public static void main(String[] args) {        
        union(1,2);
        union(3,4);
        union(5,6);
        union(3,1);
        union(1,5);
        
        System.out.println(isConnected(3,5));
    }