1

我正在用 Javascript 构建图形编辑器，我需要一种算法来识别两个“节点”对象之间的所有可能路径。

给定以下 JSON 对象：

{
    "failureNode": {
        "failureNode": {
            "failureNode": {
                "failureNode": {
                    "failureNode": null,
                    "successNode": null,
                    "id": "node-endpointfailure",}
                },
                "successNode": {
                    "failureNode": null,
                    "successNode": null,
                    "id": "node-endpointsuccess",
                },
                "id": "node-1",
            },
            "successNode": {
                "failureNode": null,
                "successNode": null,
                "id": "node-endpointsuccess",
            },
            "id": "node-2",
        },
        "successNode": {
            "failureNode": {
                "failureNode": {
                    "failureNode": null,
                    "successNode": null,
                    "id": "node-endpointfailure",
                },
                "successNode": {
                    "failureNode": null,
                    "successNode": null,
                    "id": "node-endpointsuccess",
                },
                "id": "node-1",
            },
            "successNode": {
                "failureNode": null,
                "successNode": null,
                "id": "node-endpointsuccess",
            },
            "id": "node-3",
        },
        "id": "node-4",
    },
    "successNode": {
        "failureNode": null,
        "successNode": null,
        "id": "node-endpointsuccess",
    },
    "id": "node-root",
}

我需要 ID = 'node-root' &'node-endpointfailure' 的节点之间的所有可能路由。在此示例中，有两种可能的方式从“开始”（数据结构中的节点根）开始和结束和“失败”（节点端点故障）开始：

  1. 开始 -> node1 -> node2 -> node4 -> 失败
  2. 开始 -> node1 -> node3 -> node4 -> 失败

对于此示例，输出将是 JSON 路径数组。像这样的东西...

[
    failureNode.failureNode.failureNode.failureNode,
    failureNode.successNode.failureNode.failureNode
]

大多数应用程序都使用 jQuery，因此纯 Javascript 或 jQuery 解决方案都可以使用。

4

2 回答 2

1

这应该完成任务：

function recurse(from, to, node) {
    var result = [],
        choices = ["sucessNode", "failureNode"];
    if (!from && to == node.id)
        return [[]];
    if (from == node.id)
        return recurse(null, to, node);
    for (var i=0; i<choices.length; i++) {
        var choice = choices[i];
        if (node[choice] != null) {
            var res = recurse(from, to, node[choice]);
            for (var j=0; j<res.length; j++) {
                res[j].unshift(choice);
                result.push(res[j]);
            }
        }
    }
    return result;
}
recurse('node-root', 'node-endpointfailure', data);
于 2013-01-30T19:13:25.250 回答
1

我发现您选择的代表有点奇怪和混乱。树不是表示这一点的最佳方式。您所描述的本质上是一个 DAG（有向无环图）。递归表示最终会复制对象。虽然我确信还有其他方法可以表示这一点，但简单的表示方法就是列出每个节点及其由 id 标识的成功和失败节点。停止节点的成功节点和失败节点将具有空值（或零长度字符串，以两者为准）。或者你可以有一本包含所有这些的字典。

例如，您的图表可以（按列表方式）描述为：

[
  {
    id: "Start",
    successNode: "success",
    failureNode: "node-1"
  },
  {
    id: "node-1",
    successNode: "node-3",
    failureNode: "node-2"
  },
  {
    id: "node-2",
    successNode: "success",
    failureNode: "node-4"
  },
  {
    id: "node-3",
    successNode: "success",
    failureNode: "node-4"
  },
  {
    id: "node-4",
    successNode: "success",
    failureNode: "failure"
  },
  {
    id: "success",
    successNode: "",
    failureNode: ""
  },
  {
    id: "failure",
    successNode: "",
    failureNode: ""
  }
]

使编辑图表变得非常容易。只需根据需要添加或删除节点及其值。我可能会使用另一个对象作为字典，以使其更快/更容易找到每个节点。假设我确实有这样的字典dict，那么从一个节点导航到另一个节点以查看您的最终位置并不难。

于 2013-01-30T19:42:50.033 回答