Approche différente Union Find
J'étudie les algorithmes et j'ai fait cet algorithme "Union Find Like".
J'ai un tableau d'objets avec une référence et je fais l'union pointant vers la même référence au lieu d'avoir deux int [] avec des nombres et des poids.
- Il n'est pas nécessaire d'initialiser le tableau.
- Vous aurez un maximum de N / 2 objets supplémentaires (si vous faites une union par paires), mais dans un tableau avec beaucoup d'unions, vous n'aurez que quelques objets (uniquement les racines R) avec seulement des références pointant vers le même objet.
- C'est un temps linéaire.
Puis-je avoir des commentaires sur cette idée?
Merci.
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
}
}
```
Réponses
Tout d'abord, j'aime l'idée et la mise en œuvre.
Je l'ai un peu remanié et j'ai trouvé ça:
isConnected : Extraire la connexion [a] et la connexion [b] dans les variables locales et simplifier la condition. Eclipse peut vous aider dans la première étape, la deuxième que j'ai faite manuellement.
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;
}
}
En union, j'ai fait la même chose avec les variables locales (attention aux affectations dans le tableau. Ensuite, j'ai utilisé des IF imbriqués, qui facilitent la lecture du déroulement du programme.
Cela se traduit par:
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];
}
}
}
L'étape suivante consiste à utiliser une classe d'assistance au lieu de variables statiques, comme ça:
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
}
}
Vous voyez comment vous pouvez créer plusieurs instances de UnionFind? Vous pouvez même définir une capacité au moment de l'exécution.
Je vous laisse l'ajout du JavaDoc manquant.
Dès que vous avez dit que c'était le temps linéaire, il était clair que quelque chose ne va pas. Un rapide coup d'œil au code n'a montré aucune boucle ni récursivité, il était donc clair qu'il s'agissait bien d'un temps linéaire et que votre algorithme ne fonctionnait pas.
Voici un exemple de votre échec, vous signalez falsemême si 3et 5devrait être connecté en raison de union(3,1)et 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));
}