Anderer Ansatz Union Find

Question

Ich studiere Algorithmen und habe diesen "Union Find Like" -Algorithmus gemacht.

Ich habe ein Array von Objekten mit einer Referenz und ich mache die Vereinigung, die auf dieselbe Referenz zeigt, anstatt zwei int [] mit Zahlen und Gewichten.

• Das Array muss nicht initialisiert werden.
• Sie haben maximal N / 2 zusätzliche Objekte (wenn Sie eine Vereinigung paarweise durchführen), aber in einem Array mit vielen Vereinigungen haben Sie nur wenige Objekte (nur die R-Wurzeln), wobei nur Verweise auf dasselbe verweisen Objekt.
• Es ist eine lineare Zeit.

Kann ich Feedback zu dieser Idee haben?

Vielen Dank.

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

Zunächst gefällt mir die Idee und die Umsetzung.

Ich habe es ein bisschen überarbeitet und mir das ausgedacht:

isConnected : Extrahieren Sie die Verbindung [a] und die Verbindung [b] in lokalen Variablen und vereinfachen Sie die Bedingung. Eclipse kann Sie beim ersten Schritt unterstützen, dem zweiten, den ich manuell ausgeführt habe.

    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;
        }
    }

In union habe ich dasselbe mit den lokalen Variablen gemacht (Vorsicht vor den Zuweisungen im Array. Dann habe ich verschachtelte IFs verwendet, die den Programmablauf leichter lesbar machen.

Das führt zu:

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];
        }
    }
}

Der nächste Schritt besteht darin, eine Hilfsklasse anstelle der folgenden statischen Variablen zu verwenden:

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
    }
}

Sie sehen, wie Sie mehrere Instanzen von erstellen können UnionFind? Sie können sogar zur Laufzeit eine Kapazität festlegen.

Ich überlasse Ihnen das Hinzufügen des fehlenden JavaDoc.

Answer 2

Sobald Sie sagten, es sei lineare Zeit, war klar, dass etwas nicht stimmt. Ein kurzer Blick auf den Code zeigte keine Schleifen oder Rekursionen, daher war klar, dass es sich tatsächlich um eine lineare Zeit handelt und Ihr Algorithmus nicht funktioniert.

Hier ist ein Beispiel Sie scheitern, berichten Sie , falseobwohl 3und 5sollte aufgrund angeschlossen werden union(3,1)und 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));
    }