Go语言深度优先搜索（DFS）详解（从零开始掌握图的递归遍历算法）

为什么使用 Go 语言实现 DFS？

Go 语言语法简洁、并发能力强，且标准库支持良好，非常适合学习基础算法。通过 Go 实现 DFS算法，不仅能加深对算法的理解，还能提升 Go 编程能力。

Go 实现 DFS：递归版本

我们先用一个简单的无向图来演示。假设图的结构如下：

• A 连接 B 和 C
• B 连接 D 和 E
• C 连接 F

我们可以用 map[string][]string 来表示这个图。

// 定义图结构并实现 DFSpackage mainimport "fmt"// dfs 递归实现深度优先搜索func dfs(graph map[string][]string, node string, visited map[string]bool) {    // 如果节点已访问，直接返回    if visited[node] {        return    }    // 标记为已访问并打印    visited[node] = true    fmt.Println("访问节点:", node)    // 递归访问所有相邻节点    for _, neighbor := range graph[node] {        dfs(graph, neighbor, visited)    }}func main() {    // 构建图    graph := map[string][]string{        "A": {"B", "C"},        "B": {"A", "D", "E"},        "C": {"A", "F"},        "D": {"B"},        "E": {"B"},        "F": {"C"},    }    // 初始化访问记录    visited := make(map[string]bool)    // 从节点 A 开始 DFS    dfs(graph, "A", visited)}

运行这段代码，输出将是：

访问节点: A访问节点: B访问节点: D访问节点: E访问节点: C访问节点: F

关键点解析

• visited 映射：防止重复访问同一个节点，避免无限循环。
• 递归调用：每次进入新节点就立即递归，体现“深度优先”。
• 图的表示：使用邻接表（map + slice）是 Go 中常见的图存储方式。

应用场景

DFS 在实际开发中有广泛应用，例如：

• 迷宫求解
• 拓扑排序
• 检测图中是否存在环
• 连通分量分析

总结

通过本文，你已经掌握了如何在 Go语言 中实现 深度优先搜索（DFS）。无论是用于面试准备还是实际项目开发，理解 DFS 都是程序员必备的基础技能。记住：DFS 的核心是“深入+回溯”，而 Go 的简洁语法让这一过程变得清晰直观。

如果你正在学习 图的遍历Go 或 递归搜索Go，不妨动手敲一遍上面的代码，加深理解！

关键词回顾：Go语言深度优先搜索、DFS算法实现、图的遍历Go、递归搜索Go。