Go语言实现图的邻接表结构与BFS/DFS算法
本文介绍在Go语言中使用邻接表实现无向图的方法，并通过递归还原代码实现了广度优先搜索（BFS）和深度优先搜索（DFS）。针对地图搜索场景下的遍历去重与节点标记问题提供了具体的编码解决方案。
图的Go语言实现
图（Graph）是由一组顶点和连接这些顶点的边所构成的数据结构。相较于使用二维数组表示稠密图的邻接矩阵，在Go语言中更常采用“邻接表”的方式来处理稀疏图，从而节省内存空间。
package main
import "fmt"
type Node struct {
value int
}
type Graph struct {
nodes []*Node
edges map[Node][]*Node // 无向图的邻接链表
}
在上述定义中，nodes是一个存放节点对象的指针切片，而 edges 是Map类型的字典，以节点为键，值为与该节点直接相连的其他节点的指针数组。红字标识的节点序号代表顶点，例如节点1与节点2、5存在物理连接关系。
接下来定义图的初始化逻辑与核心辅助函数：包括添加顶点、在无向图中双向追加边（u->v 同时记录 v->u）、打印当前图结构的状态等。
// 增加节点
func (g *Graph) AddNode(n *Node) {
g.nodes = append(g.nodes, n)
}
// 增加边（注意是无向图，需双向赋值）
func (g *Graph) AddEdge(u, v *Node) {
g.edges[*u] = append(g.edges[*u], v)
g.edges[*v] = append(g.edges[*v], u)
}
第1步：初始化图及生成测试数据
通过一个示例演示如何初始化包含多个节点与边的实例对象：
func initGraph() Graph {
g := Graph{edges: make(map[Node][]*Node)}
for i := 1; i <= 5; i++ {
g.AddNode(&Node{i})
}
// 建立连通关系，例如 1-2, 2-3 等
A := [...]int{1, 1, 2, 2, 2, 3, 4}
B := [...]int{2, 5, 3, 4, 5, 4, 5}
for i := 0; i < len(A); i++ {
g.AddEdge(g.nodes[A[i]-1], g.nodes[B[i]-1])
}
return g
}
图的广度优先搜索（BFS）
广度优先搜索是一种分层遍历策略，它首先访问起始节点的所有相邻节点，再进一步访问这些邻居的未访问过的前层节点。这种逐层向外扩散的特性使其非常适合用于计算最短路径问题。
/* func BFS(n *Node) */
func (g *Graph) BFS(start *Node) {
var queue []*Node
start.searched = true
queue = append(queue, start)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:] // 出队
fmt.Printf("%d -> ", node.value)
for _, neighbor := range g.edges[node] {
if !neighbor.searched {
neighbor.searched = true
queue = append(queue, neighbor)
}
}
}
fmt.Println()
}
为避免重复访问陷入死循环，必须在节点加入队列时立即将其状态标记为已访问（searched = true）。由于BFS属于广度探索，需要依赖先进先出队列来维持层级顺序。
图的深度优先搜索（DFS）
深度优先搜索则遵循“一条路走到黑”的逻辑：从某个起点出发，每次只沿着某条分支深入直到无法继续或达到目标节点，然后回溯到上一个决策点，选择另一条尚未探索的路径。
// 递归入口函数
func (g *Graph) DFS(start *Node) {
if start.searched { return }
start.searched = true
fmt.Printf("%d -> ", start.value)
for _, next := range g.edges[start] {
g.DFS(next)
}
}
第2步：全局连通性与完整遍历执行
如果图本身不连通（即并非所有节点都能由初始节点到达），上述单入口递归只能覆盖其中一个连通分量。因此我们需要在主程序中确保对所有节点进行检查：
func main() {
g := initGraph()
for _, node := range g.nodes {
if !node.searched {
g.DFS(node)
}
}
}
第3步：结果验证与注意事项
- 当图中的某一节点被设置为不可达状态时，必须依靠外层的
for循环再次触发递归。 - 在实际工程实践中，对于极其庞大的递归层次可能会遇到调用栈溢出风险；这种情况下建议将递归模式改写为显式的Stack迭代模式。
- 本示例侧重于算法原理表达，实际开发中还可以结合并发安全库增强复杂应用环境下的稳健性表现。
以上就是Go语言编程学习实现图的广度与深度优先搜索的详细内容，更多关于Go语言基础图遍历资料请关注本站其它相关文章！
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
