广度首先遍历对象

我正在制作一个解决益智游戏的程序，它会在棋盘上找到所有可能的动作，并将所有可能产生的棋盘放在一个对象中。 然后它会找到所得到的电路板的所有可能移动，依此类推。 该对象看起来像这样：

{ "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":[{}] }] } 

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

Answer 1

递归。

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

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

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

Answer 2

尚未完全测试：

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

Answer 3

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

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

此外，维基百科页面上还有一些伪足，以及此处的一些解释

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