BitSet mémoire insuffisante Java

Question

J'utilise BitSet pour savoir si les nœuds d'un graphique ont été visités à l'aide de la méthode DFS. Pour ce faire, j'ai créé un tableau BitSet []. Les BitSets eux-mêmes peuvent être compris entre 100.000 et 500.000 entrées.

Ceci est le code que j'utilise.

public void tc() { 
//  if (scc_cache_valid) 
//   return; 
     marked2 = new BitSet[node_count]; 
     for (int v = 0; v < node_count; v++) { 
      //if (marked2[v] == null) 
       marked2[v] = new BitSet(edge_count); 
      System.out.println("aaa" + marked2[v].size()); 
      for (int w : children.get(v)) { 
       if (!marked2[v].get(w)) 
        dfs(v, w); 
      } 
     } 
    } 

    public void tc(int v) { 
//  if (scc_cache_valid && marked2[v] != null) 
//   return; 

//  marked2 = new BitSet[node_count]; 
//  for (int v = 0; v < node_count; v++) { 
     if (marked2[v] == null) 
      marked2[v] = new BitSet(node_count); 
     System.out.println(marked2[v].size()); 

     for (int w : children.get(v)) { 
       if (!marked2[v].get(w)) 
        dfs(v, w); 
      } 
//  } 
    } 

    public boolean reachable(int v, int w) { 
     return marked2[v].get(w); 
    } 

    private void dfs(int v, int w) { 
     marked2[v].set(w, true); 
     System.out.println(marked2[v].length()); 

     for (int z : children.get(w)) { 
      if (!marked2[v].get(z)) 
       dfs(v, z); 
     } 
    } 

Malheureusement, je suis à court de tas. Y at-il une meilleure solution (plus de mémoire efficace) à ce problème?

Merci. Je pense que votre algorithme DFS est incorrect.

Answer 1

Un algorithme DFS classique pour un arbre ne nécessite pas de bitmap du tout.

Un algorithme DFS classique pour un DAG ou un graphe complet nécessite un seul bitmap avec un bit pour chaque noeud dans le graphe. Cela suppose qu'il existe un mappage un-à-un (dense) des nœuds aux entiers; par exemple. numéros de noeud. Si non, alors il est conventionnel d'utiliser un HashSet<Node>. Dans les deux cas, l'espace requis est O(N) plutôt que O(N^2).

Un algorithme pseudo-code pour le cas DAG/graphique est:

dfs(root) = dfs0(root, new Set()); 
dfs0(node, visited) = 
     if !visited.contains(node): 
      visited.add(node) 
      // do stuff for node 
      foreach n in node.children: 
       dfs0(n, visited) 

Note: il n'y a qu'un seul ensemble objet utilisé dans le traversal.