使用Lua的BFS算法可找到2个节点之间的最短路径 [英] BFS algorithm using Lua that finds the shortest path between 2 nodes

问题描述

我设法编写了一个代码，该代码使用BFS算法遍历所有图形节点.这是容易的部分:)

I managed to write a code, that iterates over all graph nodes using the BFS algorithm. It was the easy part :)

不，我坚持要获得两个节点之间的最短路径.

No I am stuck with getting the shortest path between two nodes.

到目前为止，这是我的代码:

This is my code so far:

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的最短路径.

With the current example I would need to get the shortest path from 1 to 10.

推荐答案

这是可以完成的方法.

queue.lua

local queue = {}

function queue:init()
    local q = {}

    q.stack = {}

    function q:push(e)
        table.insert(self.stack, e)
    end

    function q:pull()
        local e = self.stack[1]

        table.remove(self.stack, 1)

        return e
    end

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

    return q
end

return queue

tbl.lua

function table.contains(tbl, e)
    for _, v in pairs(tbl) do
        if v == e then
            return true
        end
    end

    return false
end

function table.copy(tbl)
    local t = {}

    for _, v in pairs(tbl) do
        table.insert(t, v)
    end

    return t
end

bfs.lua

require "tbl" -- table.contains and table.copy
queue = require "queue"

local function bfs(graph, start, goal)
    if not graph[start] then
        return false
    end

    local visited = {}
    local queue = queue:init()

    queue:push({start})
    table.insert(visited, start)

    while queue:count() > 0 do
        local path = queue:pull()
        local node = path[#path]

        if node == goal then return path end

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

                if graph[exit] then
                    local new = table.copy(path)

                    table.insert(new, exit)
                    queue:push(new)
                end
            end
        end
    end

    return false
end

return bfs

用法:

将所有三个文件保存到lua路径.

Save all three files to your lua path.

bfs =需要"bfs"

bfs = require "bfs"

路径= bfs(结束，开始，目标)

path = bfs(grap, start, goal)

这篇关于使用Lua的BFS算法可找到2个节点之间的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！