admin

0 收听	1 听众	10 主题

使用lua实现各种算法，先从深度优先搜索算法开始

IP属地：浙江省杭州市

发表于 2024-7-5 16:22:48 | 查看: 286| 回复: 1

接下来我们可以实现深度优先搜索（DFS）算法。深度优先搜索是一种图搜索算法，它从一个起始节点开始，沿着一个分支尽可能深入地搜索，直到不能再深入为止，然后回溯并继续搜索其他分支。

以下是用 Lua 实现的深度优先搜索算法：

-- 深度优先搜索函数（递归实现）
function dfs(graph, startNode, visited, result)
    visited[startNode] = true
    table.insert(result, startNode)

    for _, neighbor in ipairs(graph[startNode]) do
        if not visited[neighbor] then
            dfs(graph, neighbor, visited, result)
        end
    end
end

-- 测试深度优先搜索函数
local graph = {
    A = {"B", "C"},
    B = {"A", "D", "E"},
    C = {"A", "F"},
    D = {"B"},
    E = {"B", "F"},
    F = {"C", "E"}
}

local startNode = "A"
local visited = {}
local result = {}

dfs(graph, startNode, visited, result)

print("深度优先搜索遍历顺序:")
for _, node in ipairs(result) do
    print(node)
end

在这个实现中：

dfs 函数接受一个图 graph、一个起始节点 startNode、一个记录已访问节点的表 visited 和一个存储遍历顺序的表 result。
将起始节点标记为已访问，并加入遍历顺序表 result。
对于每个邻居节点，如果尚未访问，则递归调用 dfs 函数。
最后，测试代码对一个图进行深度优先搜索，并输出遍历顺序。

图 graph 使用邻接表表示，其中每个节点对应一个包含其邻居节点的表。

深度优先搜索也可以用非递归方式实现，使用栈来模拟递归调用。以下是非递归实现的示例：

-- 深度优先搜索函数（非递归实现）
function dfsIterative(graph, startNode)
    local visited = {}
    local stack = {startNode}
    local result = {}

    while #stack > 0 do
        local currentNode = table.remove(stack)

        if not visited[currentNode] then
            visited[currentNode] = true
            table.insert(result, currentNode)

            for i = #graph[currentNode], 1, -1 do
                local neighbor = graph[currentNode][i]
                if not visited[neighbor] then
                    table.insert(stack, neighbor)
                end
            end
        end
    end

    return result
end

-- 测试深度优先搜索函数（非递归实现）
local resultIterative = dfsIterative(graph, startNode)

print("深度优先搜索遍历顺序（非递归）:")
for _, node in ipairs(resultIterative) do
    print(node)
end

在这个非递归实现中：

深度优先搜索在许多实际应用中非常有用，例如拓扑排序、连通分量查找和迷宫求解等。