bitset优化dfs

bitset是一种在计算机科学中用于存储二进制数据的数据结构，通常表现为一个固定大小的数组，每个元素代表一位状态。在深度优先搜索(DFS)算法中，可以利用bitset来高效地表示和跟踪已经访问过的节点。以下是几种-bitset优化DFS的方法：

1. **空间效率**：bitset相比列表存储节省空间，因为只需要对每个节点是否访问过用一个比特位表示，而不是为每个节点分配单独的空间。

2. **快速判断**：通过位操作（如按位与运算），我们可以迅速检查某个节点是否已经被访问过，无需遍历整个列表查找。

3. **减少开销**：由于bitset的操作速度非常快，可以在常数时间内完成，所以可以减少频繁的内存访问次数，提高性能。

4. **一次性处理**：如果需要对所有节点进行搜索，bitset可以在一次操作中设置或清除多个状态，而无需多次循环。

例如，在使用Python的`numpy`库中的`bitwise_and`函数来进行逐位与操作，可以帮助我们在DFS过程中跟踪路径。下面是一个简单的例子：

import numpy as np

def dfs(graph, start, visited = [False] * len(graph)):
    # 初始化bitset with all nodes unvisited
    bitset = np.uint8(np.zeros(len(graph), dtype=np.bool))
    
    stack = [start]
    while stack:
        node = stack.pop()
        if not visited[node]:
            visited[node] = True
            stack.extend([neighbor for neighbor in graph[node] if not bitset[neighbor]])
            # 更新bitset，标记已访问邻居
            bitset |= 1 << node
    
    return visited