面试题：JavaScript 数据结构优化之图的遍历

Question

假设有一个用邻接表表示的图结构，示例数据如下：`const graph = { A: ['B', 'C'], B: ['A', 'D', 'E'], C: ['A', 'F'], D: ['B'], E: ['B', 'F'], F: ['C', 'E'] };`。要求实现深度优先搜索（DFS）和广度优先搜索（BFS）两种遍历方式，并阐述如何优化这两种遍历算法在内存使用和时间复杂度方面的性能，特别是在处理大规模图数据时。

Answer 1

深度优先搜索（DFS）实现

function dfs(graph, start) {
    const visited = new Set();
    const result = [];

    function dfsHelper(node) {
        visited.add(node);
        result.push(node);
        const neighbors = graph[node];
        for (const neighbor of neighbors) {
            if (!visited.has(neighbor)) {
                dfsHelper(neighbor);
            }
        }
    }

    dfsHelper(start);
    return result;
}

广度优先搜索（BFS）实现

function bfs(graph, start) {
    const visited = new Set();
    const result = [];
    const queue = [start];
    visited.add(start);

    while (queue.length > 0) {
        const current = queue.shift();
        result.push(current);
        const neighbors = graph[current];
        for (const neighbor of neighbors) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return result;
}

性能优化

内存使用优化

• DFS：
  • 使用迭代实现（借助栈）代替递归，递归可能会导致栈溢出问题，特别是在处理大规模图时。迭代实现可以更好地控制内存使用。
  • 合理管理visited集合，确保其占用的内存空间在可接受范围内。可以考虑使用更高效的数据结构，例如布隆过滤器（Bloom Filter），在允许一定误判率的情况下大大减少内存占用。
• BFS：
  • 同样合理管理visited集合。
  • 对于队列，及时释放已处理节点的内存。在大规模图中，队列可能会变得非常大，所以要注意内存回收。可以考虑采用循环队列等数据结构来优化内存使用。

时间复杂度优化

• DFS：
  • 避免重复访问节点，确保visited集合的操作高效。
  • 如果图有特定的结构信息（如分层结构），可以利用这些信息优化搜索路径，减少不必要的搜索。
• BFS：
  • 优化队列操作，使用高效的队列实现，如双端队列（Deque），在某些情况下可以提高操作效率。
  • 对于大规模图，可以采用并行BFS算法，利用多核CPU的优势加快搜索速度。但要注意处理好线程同步和资源竞争问题。