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

我成功编写了一段代码，使用 BFS 算法迭代了所有图节点。这是简单的一部分 :)

现在我卡在了获取两个节点之间的最短路径上。

这是我目前的代码：

function table.contains(table, element)
  for _, value in pairs(table) do
    if value == element then
      return true
    end
  end
  return false
end

queue = {stack={}}

function queue:en(e)
    table.insert(self.stack, e)
end

function queue:de()
    local e = self.stack[1]
    self.stack[1] = nil

    local new_stack = {}

    for _, v in pairs(self.stack) do
        table.insert(new_stack, v)
    end

    self.stack = new_stack

    return e
end

function queue:count()
    return #self.stack
end

function bfs()
    start = 1
    goal  = 10
    visited = {}
    path = {}

    graph = {}
    graph[1] = {2,3,4}
    graph[2] = {6,5,1}
    graph[3] = {1}
    graph[4] = {7,8}
    graph[5] = {9,10,2}
    graph[6] = {2}
    graph[7] = {4,11,12}
    graph[8] = {4}
    graph[9] = {5}
    graph[10] = {5}
    graph[11] = {7}
    graph[12] = {7}

    queue:en(start)
    table.insert(visited, start)
    depth = 1

    while queue:count() > 0 do
        node = queue:de()

        for _, exit in pairs(graph[node]) do
            if not table.contains(visited, exit) then
                table.insert(visited, exit)

                if exit == goal then
                    print("GOAL : " .. exit)

                    do return end
                end

                if graph[exit] then
                    print("Node: " .. exit .. ", Depth: " .. depth)

                    queue:en(exit)
                end
            end
        end

        depth = depth + 1
    end
end

bfs()

运行后输出：

Node: 2, Depth: 1
Node: 3, Depth: 1
Node: 4, Depth: 1
Node: 6, Depth: 2
Node: 5, Depth: 2
Node: 7, Depth: 4
Node: 8, Depth: 4
Node: 9, Depth: 6
GOAL : 10

在当前示例中，我需要从 1 到 10 获取最短路径。