Approccio diverso Union Find

Sep 08 2020

Sto studiando algoritmi e ho fatto questo algoritmo "Union Find Like".

Ho un array di oggetti con un riferimento e faccio l'unione che punta allo stesso riferimento invece di avere due int [] con numeri e pesi.

  • Non è necessario inizializzare l'array.
  • Avrai un massimo di N / 2 oggetti extra (se fai un'unione a coppie), ma in un array con molte unioni avrai solo pochi oggetti (solo le radici R) con solo riferimenti che puntano allo stesso oggetto.
  • È un tempo lineare.

Posso avere un feedback su questa idea?

Grazie.

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

Risposte

2 DorianGray Sep 09 2020 at 01:51

Innanzitutto mi piace l'idea e la realizzazione.

L'ho refactoring un po 'e mi è venuto in mente:

isConnected : Estrai connessione [a] e connessione [b] nelle variabili locali e semplifica la condizione. Eclipse può aiutarti con il primo passaggio, il secondo che ho fatto manualmente.

    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 unione ho fatto lo stesso con le variabili locali (attenzione alle assegnazioni nell'array. Poi ho usato IF annidati, che rendono il flusso del programma più facile da leggere.

Questo risulta in:

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

Il passaggio successivo consiste nell'usare una classe helper invece di variabili statiche, in questo modo:

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

Vedi come puoi creare più istanze di UnionFind? È anche possibile impostare una capacità in fase di esecuzione.

Lascio a te l'aggiunta del JavaDoc mancante.

1 superbrain Sep 09 2020 at 04:43

Non appena hai detto che è tempo lineare, è stato chiaro che qualcosa non andava. Una rapida occhiata al codice non mostrava loop o ricorsività, quindi era chiaro che è davvero tempo lineare e che il tuo algoritmo non funziona.

Ecco un esempio in cui fallisci, segnali falseanche se 3e 5dovresti essere connesso a causa di union(3,1)e 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));
    }