Алгоритм BFS с использованием Lua, который находит кратчайший путь между 2 узлами

Question

Мне удалось написать код, который перебирает все узлы графа, используя алгоритм 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.

Answer 1

Вот как это можно сделать.

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.

bfs = требуется "bfs"

путь = BFS (захват, начало, цель)