BitSet 内存不足 Java

Question

我正在使用 BitSet 来跟踪是否使用 DFS 方法访问了图中的节点。为此，我创建了一个 BitSet[] 数组。 BitSet 本身可以在 100.000-500.000 个条目之间。

这是我正在使用的代码。

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

不幸的是我运行没空了。有没有更好的（更有效的内存）解决这个问题的方法？

谢谢。

Answer 1

我认为你的DFS算法不正确。

树的经典 DFS 算法根本不需要位图。
用于 DAG 或完整图的经典 DFS 算法需要单个位图，其中每个节点对应一个位图。这假设存在从节点到整数的（密集）一对一映射；例如节点号。如果不是，那么通常使用 HashSet<Node>.

无论哪种情况，space 要求都是 O(N) 而不是 O(N^2)。

DAG/图案例的伪代码算法是：

 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)

注意：遍历只使用了一个Set对象

BitSet 内存不足 Java

BitSet out of memory Java

java

bitset