对象的广度优先遍历

Question

我正在制作一个解决谜题游戏的程序，它会在棋盘上找到所有可能的移动，并将所有可能的结果存储在一个对象中。然后，它会为这些结果寻找所有可能的移动，以此类推。该对象将类似于以下内容：

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

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

- Peter Olson

---

你可能想在这里和网络上搜索“递归”和“递归函数”，这些都是丰富的信息来源。 - prodigitalson

你熟悉递归吗？ - Mike Park

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

- Samir Talwar

---

重新考虑一下，难道这个程序不是先处理第一层，然后遍历第二层中的第一个板块，再处理它，然后遍历第三层中的第一个板块，以此类推吗？我希望它在处理任何第三层的内容之前，先处理第一个板块，并遍历第二层中所有的板块。 - Peter Olson

好的。在这种情况下，您需要实现一个队列。我向您展示的是深度优先遍历。您需要进行广度优先遍历。请查看http://en.wikipedia.org/wiki/Breadth-first_search以获取一个不错的算法。 - Samir Talwar

好的。我猜我没有很清楚地表达我想要的内容。我修改了问题。 - Peter Olson

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

- John Giotta

Answer 3

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

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

此外，维基百科页面上还有一些伪代码以及更多解释HERE

另外，快速的谷歌搜索结果显示了一个类似的算法，可以用于您的目的HERE

- Hugoagogo