javascript 对象的广度优先遍历

Breadth first traversal of object

提问by Peter Olson

I am making a program that solves a puzzle game, and it finds all the possible moves on a board and puts all the possible resulting boards in an object. Then it finds all the possible moves for the resulting boards, and so on. The object will look something like this:

我正在制作一个解决益智游戏的程序，它会在棋盘上找到所有可能的移动，并将所有可能的棋盘放在一个对象中。然后它为结果板找到所有可能的移动，依此类推。该对象将如下所示：

{
  "board": {
      "starts": [[0,0],[0,3]],
      "blocks": [[3,0],[3,3]],
      "ends":   [[2,4]]
  },
  "possibleMoves": [
    {
      "board": {
        "starts": [[0,0],[2,3]],
        "blocks": [[3,0],[3,3]],
        "ends":   [[2,4]]
      },
      "possibleMoves":[
        {
          "board": {},
          "possibleMoves": [{}]
        }
      ]
    },
    {
      "board": {
        "starts": [[0,3]],
        "blocks": [[3,0],[3,3]],
        "ends":   [[2,4]]
      },
      "possibleMoves":[{}]
    }]
}

I can figure out how to add the possible moves from the top-level board, but I cannot figure out how to loop through all the resulting boards in the second level and figure out their possible moves, and then loop through all the third level boards and so on. How can I add the possible moves and traverse the object using a breadth-first search?

我可以弄清楚如何从顶级板添加可能的移动，但我无法弄清楚如何遍历第二级中的所有结果板并找出它们可能的移动，然后遍历所有第三级板等等。如何使用广度优先搜索添加可能的移动并遍历对象？

回答by Samir Talwar

Recursion.

递归。

function traverse(state) {
    handle(state.board);
    if (state.possibleMoves) {
        $.each(state.possibleMoves, function(i, possibleMove) {
             traverse(possibleMove);
        });
    }
}

EDIT:For a breadth-first search, try something like this. It doesn't use recursion, but instead iterates over a growing queue.

编辑：对于广度优先搜索，尝试这样的事情。它不使用递归，而是遍历不断增长的队列。

function traverse(state) {
    var queue = [],
        next = state;
    while (next) {
        if (next.possibleMoves) {
            $.each(next.possibleMoves, function(i, possibleMove) {
                queue.push(possibleMove);
            });
        }
        next = queue.shift();
    }
}

回答by John Giotta

Not completely tested:

未完全测试：

var oo = {
    board: {
        starts: [[0,0],[0,3]],
        blocks: [[3,0],[3,3]],
        ends:   [[2,4]]
    },
    possibleMoves: [{
        board: {
            starts: [[0,0],[2,3]],
            blocks: [[3,0],[3,3]],
            ends:   [[2,4]]
        },
    }],
};


function traverseObject (o) {
    for (var prop in o) {
        if (typeof o[prop] == "array" || typeof o[prop] == "object") {
            traverseObject(o[prop]);
            console.log(prop);
        } else {
            console.log(prop, "=", o[prop]);
        }
    }
}

traverseObject(oo);

回答by Hugoagogo

I don't have a JavaScript description but i would generally do it by keeping a queue of unexplored nodes.

我没有 JavaScript 描述，但我通常会通过保留未探索节点的队列来实现。

1. Start with only the root node in the queue.
2. Pop an item from the front of the queue
3. Explore it add all of the nodes found during exploration to the back of the queue
4. Check if there are any nodes in the queue if there are go back to step 2
5. Your done

1. 仅从队列中的根节点开始。
2. 从队列的前面弹出一个项目
3. 探索它将探索过程中找到的所有节点添加到队列的后面
4. 检查队列中是否有节点，如果有则返回步骤2
5. 你完成了

Also there is some pseudopod on the Wikipedia page as well as some more explanations HERE

维基百科页面上还有一些伪足以及更多解释在 这里

Also a quick Google search turned up a similar algorithm that could be bent to your purpose HERE

此外，快速的谷歌搜索出现了一个类似的算法，可以在这里满足你的目的