Go语言图算法：DFS与BFS

Go语言图算法：DFS与BFS

1. 图的表示

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是两种最基本的图遍历算法。