遍历搜索算法

图遍历是图算法的基础，主要有两种遍历方式：广度优先搜索（BFS）和深度优先搜索（DFS）。这两种算法在树、图的遍历、路径查找、连通性判断等问题中都有广泛应用。

---

广度优先搜索（BFS）

基本概念

广度优先搜索（Breadth-First Search，BFS）是一种按层次遍历的算法，从起始节点开始，先访问所有距离为 1 的节点，再访问距离为 2 的节点，以此类推。

核心特点

• 使用队列：先进先出（FIFO）的数据结构
• 层次遍历：按距离起始节点的远近逐层访问
• 最短路径：在无权图中，BFS 能找到从起点到终点的最短路径
• 空间复杂度较高：需要存储每一层的所有节点

算法流程

1. 将起始节点加入队列并标记为已访问
2. 当队列不为空时：
   • 取出队首节点
   • 访问该节点的所有未访问邻居节点
   • 将邻居节点加入队列并标记为已访问
3. 重复步骤 2 直到队列为空

Golang 实现

基础 BFS 实现

package main

import (
    "fmt"
)

// 图的邻接表表示
type Graph struct {
    nodes map[int][]int
}

// 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 {
        // 取出队首节点
        node := queue[0]
        queue = queue[1:]
        result = append(result, node)
        
        // 访问所有邻居节点
        for _, neighbor := range g.nodes[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }
    
    return result
}

// BFS 返回层数信息
func (g *Graph) BFSWithLevel(start int) map[int]int {
    visited := make(map[int]bool)
    queue := []int{start}
    level := make(map[int]int)
    
    visited[start] = true
    level[start] = 0
    
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        
        for _, neighbor := range g.nodes[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                level[neighbor] = level[node] + 1
                queue = append(queue, neighbor)
            }
        }
    }
    
    return level
}

// BFS 查找最短路径
func (g *Graph) BFSPath(start, end int) []int {
    if start == end {
        return []int{start}
    }
    
    visited := make(map[int]bool)
    queue := []int{start}
    parent := make(map[int]int)
    
    visited[start] = true
    
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        
        for _, neighbor := range g.nodes[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                parent[neighbor] = node
                
                if neighbor == end {
                    // 回溯路径
                    path := []int{end}
                    curr := end
                    for curr != start {
                        curr = parent[curr]
                        path = append([]int{curr}, path...)
                    }
                    return path
                }
                
                queue = append(queue, neighbor)
            }
        }
    }
    
    return nil // 未找到路径
}

func main() {
    graph := &Graph{
        nodes: map[int][]int{
            0: {1, 2},
            1: {0, 3, 4},
            2: {0, 5},
            3: {1},
            4: {1},
            5: {2},
        },
    }
    
    fmt.Println("BFS 遍历结果:", graph.BFS(0))
    fmt.Println("节点层数:", graph.BFSWithLevel(0))
    fmt.Println("从 0 到 5 的最短路径:", graph.BFSPath(0, 5))
    
    // 输出:
    // BFS 遍历结果: [0 1 2 3 4 5]
    // 节点层数: map[0:0 1:1 2:1 3:2 4:2 5:2]
    // 从 0 到 5 的最短路径: [0 2 5]
}

二维网格 BFS（LeetCode 常见题型）

// LeetCode 200. 岛屿数量（BFS 版本）
func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }
    
    m, n := len(grid), len(grid[0])
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    
    count := 0
    directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == '1' && !visited[i][j] {
                count++
                // BFS 遍历整个岛屿
                queue := [][]int{{i, j}}
                visited[i][j] = true
                
                for len(queue) > 0 {
                    curr := queue[0]
                    queue = queue[1:]
                    
                    for _, dir := range directions {
                        x, y := curr[0]+dir[0], curr[1]+dir[1]
                        if x >= 0 && x < m && y >= 0 && y < n && 
                           grid[x][y] == '1' && !visited[x][y] {
                            visited[x][y] = true
                            queue = append(queue, []int{x, y})
                        }
                    }
                }
            }
        }
    }
    
    return count
}

// LeetCode 1091. 二进制矩阵中的最短路径
func shortestPathBinaryMatrix(grid [][]int) int {
    if grid[0][0] == 1 {
        return -1
    }
    
    n := len(grid)
    if n == 1 {
        return 1
    }
    
    queue := [][]int{{0, 0}}
    grid[0][0] = 1 // 标记为已访问
    directions := [][]int{
        {-1, -1}, {-1, 0}, {-1, 1},
        {0, -1}, {0, 1},
        {1, -1}, {1, 0}, {1, 1},
    }
    
    pathLength := 1
    
    for len(queue) > 0 {
        size := len(queue)
        pathLength++
        
        for i := 0; i < size; i++ {
            curr := queue[0]
            queue = queue[1:]
            
            for _, dir := range directions {
                x, y := curr[0]+dir[0], curr[1]+dir[1]
                
                if x == n-1 && y == n-1 {
                    return pathLength
                }
                
                if x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0 {
                    grid[x][y] = 1
                    queue = append(queue, []int{x, y})
                }
            }
        }
    }
    
    return -1
}

BFS 应用场景

1. 最短路径问题：无权图中的最短路径
2. 层次遍历：树的层序遍历、图的层次遍历
3. 连通性判断：判断图中节点是否连通
4. 最小生成树：Prim 算法的实现
5. 拓扑排序：有向无环图的拓扑排序

---

深度优先搜索（DFS）

基本概念

深度优先搜索（Depth-First Search，DFS）是一种沿着树的深度遍历的算法，尽可能深地搜索树的分支。当节点 v 的所有边都已被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。

核心特点

• 使用栈：后进先出（LIFO）的数据结构，或递归实现
• 深度遍历：尽可能深地搜索，直到无法继续再回溯
• 空间复杂度较低：只需要存储当前路径上的节点
• 可能不是最短路径：DFS 找到的路径不一定是最短的

算法流程

1. 从起始节点开始，标记为已访问
2. 访问该节点的第一个未访问邻居节点
3. 递归访问该邻居节点
4. 当没有未访问的邻居时，回溯到上一个节点
5. 重复步骤 2-4 直到所有节点都被访问

Golang 实现

递归实现（推荐）

package main

import "fmt"

// DFS 递归实现
func (g *Graph) DFS(start int) []int {
    visited := make(map[int]bool)
    result := []int{}
    
    var dfs func(int)
    dfs = func(node int) {
        visited[node] = true
        result = append(result, node)
        
        for _, neighbor := range g.nodes[node] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }
    
    dfs(start)
    return result
}

// DFS 迭代实现（使用栈）
func (g *Graph) DFSIterative(start int) []int {
    visited := make(map[int]bool)
    stack := []int{start}
    result := []int{}
    
    for len(stack) > 0 {
        // 取出栈顶节点
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        
        if visited[node] {
            continue
        }
        
        visited[node] = true
        result = append(result, node)
        
        // 将邻居节点压入栈（注意顺序，要逆序压入）
        for i := len(g.nodes[node]) - 1; i >= 0; i-- {
            neighbor := g.nodes[node][i]
            if !visited[neighbor] {
                stack = append(stack, neighbor)
            }
        }
    }
    
    return result
}

// DFS 查找路径
func (g *Graph) DFSPath(start, end int) []int {
    visited := make(map[int]bool)
    path := []int{}
    
    var dfs func(int) bool
    dfs = func(node int) bool {
        if node == end {
            path = append(path, node)
            return true
        }
        
        visited[node] = true
        path = append(path, node)
        
        for _, neighbor := range g.nodes[node] {
            if !visited[neighbor] {
                if dfs(neighbor) {
                    return true
                }
            }
        }
        
        // 回溯
        path = path[:len(path)-1]
        return false
    }
    
    if dfs(start) {
        return path
    }
    return nil
}

func main() {
    graph := &Graph{
        nodes: map[int][]int{
            0: {1, 2},
            1: {0, 3, 4},
            2: {0, 5},
            3: {1},
            4: {1},
            5: {2},
        },
    }
    
    fmt.Println("DFS 递归遍历:", graph.DFS(0))
    fmt.Println("DFS 迭代遍历:", graph.DFSIterative(0))
    fmt.Println("DFS 路径查找:", graph.DFSPath(0, 5))
    
    // 输出:
    // DFS 递归遍历: [0 1 3 4 2 5]
    // DFS 迭代遍历: [0 1 3 4 2 5]
    // DFS 路径查找: [0 1 3]
}

二维网格 DFS

// LeetCode 200. 岛屿数量（DFS 版本）
func numIslandsDFS(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }
    
    m, n := len(grid), len(grid[0])
    count := 0
    
    var dfs func(int, int)
    dfs = func(i, j int) {
        if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0' {
            return
        }
        
        grid[i][j] = '0' // 标记为已访问
        
        // 四个方向
        dfs(i-1, j)
        dfs(i+1, j)
        dfs(i, j-1)
        dfs(i, j+1)
    }
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == '1' {
                count++
                dfs(i, j)
            }
        }
    }
    
    return count
}

// LeetCode 79. 单词搜索
func exist(board [][]byte, word string) bool {
    m, n := len(board), len(board[0])
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    
    var dfs func(int, int, int) bool
    dfs = func(i, j, index int) bool {
        if index == len(word) {
            return true
        }
        
        if i < 0 || i >= m || j < 0 || j >= n || 
           visited[i][j] || board[i][j] != word[index] {
            return false
        }
        
        visited[i][j] = true
        
        // 四个方向搜索
        found := dfs(i-1, j, index+1) ||
                dfs(i+1, j, index+1) ||
                dfs(i, j-1, index+1) ||
                dfs(i, j+1, index+1)
        
        visited[i][j] = false // 回溯
        return found
    }
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if dfs(i, j, 0) {
                return true
            }
        }
    }
    
    return false
}

DFS 应用场景

1. 连通性判断：判断图中节点是否连通
2. 拓扑排序：有向无环图的拓扑排序
3. 强连通分量：Tarjan 算法、Kosaraju 算法
4. 回溯算法：八皇后、数独、全排列等
5. 路径查找：查找所有可能的路径
6. 树的遍历：前序、中序、后序遍历

---

BFS vs DFS 对比

核心区别

特性	BFS（广度优先）	DFS（深度优先）
数据结构	队列（Queue）	栈（Stack）或递归
遍历方式	层次遍历，逐层访问	深度遍历，尽可能深入
最短路径	在无权图中能找到最短路径	不一定是最短路径
空间复杂度	O(b^d)，b 是分支因子，d 是深度	O(b×d)
时间复杂度	O(V + E)	O(V + E)
实现方式	通常用迭代	通常用递归
适用场景	最短路径、层次遍历	回溯、连通性判断

选择建议

• 使用 BFS：

  • 需要找最短路径
  • 需要层次遍历
  • 图的深度很大但宽度较小

• 使用 DFS：

  • 需要回溯（如排列组合问题）
  • 需要遍历所有路径
  • 图的宽度很大但深度较小
  • 内存有限时（DFS 空间复杂度更低）

时间复杂度分析

• 时间复杂度：O(V + E)，其中 V 是节点数，E 是边数

  • 每个节点访问一次：O(V)
  • 每条边检查一次：O(E)

• 空间复杂度：

  • BFS：O(V)，最坏情况需要存储所有节点
  • DFS：O(h)，其中 h 是最大深度，递归栈的深度

---

实际应用示例

1. 树的层序遍历（BFS）

// LeetCode 102. 二叉树的层序遍历
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    
    result := [][]int{}
    queue := []*TreeNode{root}
    
    for len(queue) > 0 {
        levelSize := len(queue)
        level := []int{}
        
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)
            
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        
        result = append(result, level)
    }
    
    return result
}

2. 回溯算法（DFS）

// LeetCode 46. 全排列（DFS 回溯）
func permute(nums []int) [][]int {
    result := [][]int{}
    used := make([]bool, len(nums))
    path := []int{}
    
    var backtrack func()
    backtrack = func() {
        if len(path) == len(nums) {
            temp := make([]int, len(path))
            copy(temp, path)
            result = append(result, temp)
            return
        }
        
        for i := 0; i < len(nums); i++ {
            if used[i] {
                continue
            }
            
            // 做选择
            path = append(path, nums[i])
            used[i] = true
            
            // 递归
            backtrack()
            
            // 撤销选择（回溯）
            path = path[:len(path)-1]
            used[i] = false
        }
    }
    
    backtrack()
    return result
}

3. 图的连通分量（DFS）

// 计算无向图中的连通分量数量
func countComponents(n int, edges [][]int) int {
    graph := make(map[int][]int)
    for _, edge := range edges {
        graph[edge[0]] = append(graph[edge[0]], edge[1])
        graph[edge[1]] = append(graph[edge[1]], edge[0])
    }
    
    visited := make([]bool, n)
    count := 0
    
    var dfs func(int)
    dfs = func(node int) {
        visited[node] = true
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }
    
    for i := 0; i < n; i++ {
        if !visited[i] {
            count++
            dfs(i)
        }
    }
    
    return count
}

---

总结

BFS 和 DFS 是图遍历的两种基本方法，各有优缺点：

• BFS 适合找最短路径、层次遍历等问题
• DFS 适合回溯、连通性判断、遍历所有路径等问题

在实际应用中，要根据具体问题选择合适的算法。有时也可以结合使用，如双向 BFS 可以更快地找到最短路径。

---

参考文献

• LeetCode 图遍历专题
• 《算法导论》第 22 章
• 《数据结构与算法分析》