lua - 获取连接 ID 的“路径”

Question

我只是一遍又一遍地混淆自己......我有下表包含哪些id连接到其他id的信息。我需要找到从ID1到ID2的“最便宜”的连接

local ids = {
   [15] = {
      [18] = {
      },
      [23] = {
      },
      [24] = {
      },
   },
   [18] = {
      [15] = {
      },
      [21] = {
      },
      [50] = {
      },
      [248] = {
      },
      [330] = {
      },
      [378] = {
      },
      [914] = {

      },
      [1185] = {
      },
   },
   [21] = {
      [18] = {
      },
      [20] = {
      },
   },
   [248] = {
      [18] = {
      },
   },
}

预期结果是：

local table_path = {
   15,
   18,
   21,
}

标签： lua

Answer 1

我想最便宜的连接应该是最短的，所以你要做的是广度优先搜索。您需要另外保存每个节点的路径，因为这是您想要获得的。找到 ID2 后，您可以停下来走上这条路。由于这是广度优先，所以第一次找到 ID2 也保证是最短路径。

https://en.wikipedia.org/wiki/Breadth-first_search

我只是搜索了一下，发现：

使用 Lua 的 BFS 算法找到 2 个节点之间的最短路径

在这个问题的答案中，在 Lua 中实现了广度优先搜索。如果需要，您可以从这里开始并为您的用例进行更改。