Go语言图算法：DFS与BFS

Go语言图算法DFS与BFS1. 图的表示type Graph struct { vertices map[int][]int } func NewGraph() *Graph { return Graph{ vertices: make(map[int][]int), } } func (g *Graph) AddEdge(v1, v2 int) { g.vertices[v1] append(g.vertices[v1], v2) g.vertices[v2] append(g.vertices[v2], v1) }2. DFS实现func (g *Graph) DFS(start int) []int { visited : make(map[int]bool) result : []int{} g.dfsHelper(start, visited, result) return result } func (g *Graph) dfsHelper(v int, visited map[int]bool, result *[]int) { visited[v] true *result append(*result, v) for _, neighbor : range g.vertices[v] { if !visited[neighbor] { g.dfsHelper(neighbor, visited, result) } } }3. BFS实现func (g *Graph) BFS(start int) []int { visited : make(map[int]bool) queue : []int{start} result : []int{} visited[start] true for len(queue) 0 { v : queue[0] queue queue[1:] result append(result, v) for _, neighbor : range g.vertices[v] { if !visited[neighbor] { visited[neighbor] true queue append(queue, neighbor) } } } return result }4. 总结图算法是解决复杂问题的重要工具DFS和BFS是两种最基本的图遍历算法。