Go语言如何做BFS和DFS_Go语言广度优先深度优先搜索教程【全面】

BFS必须用队列实现，Go中用切片模拟：queue=queue[1:]出队、append入队；需先记len(queue)再循环处理当前层；图需visited防重复，树可省；DFS递归简洁但慎用于深图，邻接表是Go图表示首选；距离数组用-1或map初始化以区分未访问与不可达。 用 做 BFS，别用递归 BFS 的本质是“一层层推”，必须靠队列（FIFO）保序；递归天然带栈行为，强行套用只会绕晕自己、写成伪BFS。Go 没有内置队列类型，直接用切片模拟最实际—— 出队， 入队即可。 常见错误：把 当作“当前层遍历”，结果边遍历边扩容，导致无限循环或漏层 正确做法：每次进入 for 循环前先记下 ，只处理这 个节点 图场景下必须配 ，否则无向图会反复横跳（比如 A→B→A→B…） 树结构可省略 ，但一旦转成图表示（如邻接表），就必须加，不加必死循环 用递归还是手写栈？看场景 递归写法简洁，适合树或深度可控的图；但真实图数据可能含长链或环，递归过深会触发 ，尤其在默认 go routine 栈仅 2KB 的 Go 中更敏感。 推荐默认用递归：代码短、语义清，比如遍历二叉树、做路径回溯（ 切片传指针 + 回退操作） 必须用手写栈：当图节点数 > 1000 或明确存在超长链（如链状图），用 + 无论哪种， 都不能少；DFS 不像 BFS 那样天然防重入，漏标一个节点就可能重复访问甚至死循环 表示选邻接矩阵还是邻接表？ 邻接矩阵（二维 ）查边快 ，但空间爆炸；邻接表（ 或 ）省内存、遍历邻居自然，是 Go 中事实标准。 go语言参考手册 中文CHM版 Go 是一个开源的编程语言，它能让构造简单、可靠且高效的软件变得容易。本文给大家带来Go参考手册，需要的可以来下载！ Go是从2007年末由Robert Griesemer, Rob Pike, Ken Thompson主持开发，后来还加入了Ian Lance Taylor, Russ Cox等人，并最终于2009年11月开源，在2012年早些时候发布了Go 1稳定版本。现在Go的开发已经是完全开放的，并且拥有一个活跃的社区。 Go 语言特色 简洁、快速、安全 并行、有趣、开源 内存管理、v数组安全、编译 下载 稀疏图（边数 ≪ 节点数²）一律用邻接表，比如社交网络、网页链接图 邻接矩阵只在节点数固定且极小（≤ 100）、频繁查任意两点是否连通时才值得考虑 Go 中用 更灵活（支持非连续 ID），但若节点 ID 是 0~n-1，用 性能更好、无哈希开销 无向图记得双向加边： 和 ，漏一边就是半张图 求最短路径时，距离数组怎么初始化？ 不是所有节点都能从起点到达， 必须区分“未访问”和“不可达”；用 初始化时，别设默认值 0，否则无法判断节点 0 是“距离为 0”还是“根本没访问到”。 立即学习 “ go语言免费学习笔记（深入） ”； 安全做法：用 空初始化，再显式赋 ；查距离时用 如果坚持用切片 ，初始全填 -1（ ），表示未访问/不可达；更新时只覆盖 -1 值 别用 类似值初始化——Go int 大小依赖平台，且语义不清；-1 或 map 查存在性更直白 BFS 和 DFS 的边界处理、状态标记、数据结构选择，每个点都卡在“差一行就 panic”上；真正写的时候，宁可多写两行 ，也别赌它“应该不会重复”。