2

这是我存储在 JSON 中的数据结构示例：

{
    “α”： {
        “节点1”：“回声”，
        “node2”：“好极了”
    },
    “好极了”：{
        “节点1”：“阿尔法”，
        “node2”：“好极了”，
        “node3”：“查理”
    },
    “查理”：{
        “node1”：“好极了”，
        “node2”：“狐步舞”
    },
    “三角洲”：{
        “节点1”：“阿尔法”，
        “节点2”：“酒店”
    },
    “回声”：{
        “node1”：“高尔夫”，
        “节点2”：“三角洲”
    },
    “狐步舞”：{
        “节点1”：“回声”，
        “node2”：“印度”，
        “节点3”：“三角洲”
    },
    “高尔夫”：{
        "node1": "酒店",
        “节点2”：“查理”
    },
    “酒店”： {
        “node1”：“狐步舞”，
        “node2”：“印度”
    },
    “印度”： {
        “node1”：“查理”，
        “节点2”：“酒店”
    }
}

我正在寻找任何两个节点之间的最短路径。例如，从echoto的最短路径hotel是：echo-> golf->hotel

如您所见，这些节点是循环的，并且可以无休止地遍历它们。我还应该注意，节点路径都是一种方式。所以使用上面相同的例子，从hotel返回到的最短路径echo是：hotel-> foxtrot->echo

这样的数据结构有名字吗？我知道循环打破了“树”的规则。这会是图遍历吗？

4

2 回答 2

1

你所拥有的是一个邻接列表。虽然有这样的东西更干净（删除 node1，node2 使其成为一个简单的数组）：

{
    "alpha": [
        "echo",
        "bravo"
    ],
    "bravo": [
        "alpha",
        "bravo",
        "charlie"
    ],
    ...
    "india": [
        "charlie",
        "hotel"
    ]
}

没有给出权重/距离，因此您可以使用 BFS 找到最短路径。这是一个实现。

于 2013-06-04T05:16:32.623 回答
0

您正在寻找的是通过图表的最短路径。看一下这个：

http://networkx.github.io/documentation/latest/reference/algorithms.shortest_paths.html

于 2013-05-29T09:56:40.277 回答