c++ - 最小化广度优先搜索的内存使用

Question

在下面的代码中，我通过广度优先搜索 遍历一个图。代码在遍历时构建图形。这是一个非常大的图，扇形为 12。因此，每当 广度优先搜索 的深度增加时，我想破坏它上面的层以尽量减少内存用法。我该如何设计算法来做到这一点？

string Node::bfs(Node * rootNode) {
QQueue<Cube *> q;
q.enqueue(rootNode);

while (!(q.empty())) {
    Node * currNode = q.dequeue();
    currNode->constructChildren();
    foreach (Node * child, currNode->getListOfChildren()) {
        q.enqueue(child);
    }
    if (currNode->isGoalNode()) {
        return currNode->path;
    }
}

Answer 1

在恒定扇出和假设树状图的情况下，BFS 访问过的节点数几乎与边缘节点数相同。 (例如，在扇出为 K 的树中，每层 n 有 K^n 个节点，深度小于 n 的节点数也是 Theta(K^n))。

因此，存储边缘已经占用了大量内存。因此，如果内存是一个非常大的问题，迭代加深 DFS 等“等效”技术可能会好得多。

但是如果你想销毁“访问过”的节点，那么可以通过某种方式来跟踪访问过的内容(在一般图的情况下；如果它是一棵树那么就没有问题)需要设计。在这种情况下，需要有关图表的更多信息。

编辑为什么迭代加深 DFS 更好。

BFS 中的边缘(与已访问节点相邻的未访问节点)的大小为 O(K^n)，n 是当前深度。 DFS 的边缘大小为 O(n)。

迭代加深 DFS 具有与 DFS 相同的边缘大小，并给出与 BFS 相同的结果，因为它“模拟”了 BFS。